# Set Theory

**Introduction**

A set is an *unordered collection* of *distinct *elements. Typically, we represent a set using capital alphabets A, B, C, etc. and curly braces.

The number of elements in a set is known as the **Cardinality** of a set.

Example: A = {1, 2, 3, 4, 5} , B = {2, 1, 4, 3, 5}

Note that A = B, because any set is an *unordered* collection of items.

Here, the *cardinality *of both A and B is 5, formally |A| = |B| = 5.

Another Intutive way to represent sets is using * Venn Diagrams*.

**Types of Sets**

**1. Finite Set**

A set that contains a finite number of elements. The cardinality of finite sets is always finite.

Note that any finite set with cardinality = 0, is called an **Empty Set**.

Whereas a finite set with only one element is called a **Singleton Set**.

Example: A = {Φ} *Empty Set*

B = {8} *Singleton Set*

C = {1, 2, 5, 9, 4} *Finite Set*

**2. Infinite Set**

Any set which is not finite is called an infinite set. An infinite set can be *countable* or *uncountable*.

**Countable**: Any set of elements that can be mapped *one-to-one* with a set of integers, can be termed as *Countable*.

Example: Set of rational numbers.**Uncountable**: Any set of elements that can’t be mapped *one-to-one* with a set of integers is *Uncountable*.

Example: Set of all real numbers.

**3. Subset & Superset**

Given two sets A and B, If every element of B is also present in A, but not necessarily vice versa, then B is a *subset *of A.

Similarly, we can say that A is a *superset *of B in the above case.

Example:

A = {1, 2, 3, 4, 5} , B = {1, 2, 3} then, we can say B is a subset of A. More formally, B ⊆ A.

From another perspective, we can say A is a superset of B. Formally, A** ⊇ **B.

Any subset can further be categorized into two types:

1. **Trivial Subset**: If two sets A and B are not *equivalent*, where either A or B have at least one element extra.

2. **Proper Subset**: A non-trivial subset is called a Proper subset. It is denoted as B **⊂** A.

**4. Universal Set**

It is a set of all elements that we care about in a given context. The universal set is represented by ‘**U**‘. The universal set changes with the context of the problem, or the situation we are working in.

Example: Let’s say **A **is a set of people living in India born after 01/01/2000. Then **U **here will be the set of people living in India.

In the following Venn Diagram, the outer rectangle represents the Universal Set ‘**U**‘.

**5. Power Set**

If A = {1, 2, 3}, The Power set **P(A) **is the set of all possible subsets of A.

P(A) = { {Φ}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }.

If |A| = n, then |P(A)| = 2^{n}.

**Operations on sets**

**1. Union**

The union of two sets A and B is the set of elements in A, in B, or in A and B.

Union of two sets A, B is denoted as A ∪ B.

Example: If A = {1, 2, 3} , B = {3, 4, 5} then A ∪ B = {1, 2, 3, 4, 5}

**2. Intersection**

The intersection of two sets A and B is the set of common elements present in both A and B.

The intersection of two sets A, B is denoted as A ∩ B.

Example: If A = {1, 2, 3} , B = {3, 4, 5} then A ∩ B = {3}.

**3. Complement**

The complement of a set A is the set of all elements not in A. The complement of a set A is denoted as A’

Two sets if they have no element in common are called **Disjoint Sets**.

Example: If U = {1, 2, 3, 4, 5} , A = {1, 2, 3} then A’ = {4, 5}

**4. Relative Difference**

The relative difference between two sets A and B is denoted as (A – B). It is the set of all elements in A, that are not in B.

We can calculate it as (A – B) = A – (A ∩ B).

**Laws in Set Theory**

**1. Commutative Law**

- The Commutative law states that the
*union*of two sets is equal, independent of the order of the sets in the operation.

Formally, (A ∪ B) = (B ∪ A).

This means both the Venn diagrams below shown are the same.

- The Commutative law states that the
*intersection*of two sets is equal, independent of the order of the sets in the operation.

Formally, (A ∩ B) = (B ∩ A).

**2. Associative Law**

Associative property for union and intersection says that result of an operation is independent of how the sets are grouped.

Such that,

(A ∪ B) ∪ C = A ∪ (B ∪ C)

(A ∩ B) ∩ C = A ∩ (B ∩ C)

**3. Distributive Law**

Distributive laws in sets play an essential role. They can be proven by a bit of explanation along with good examples, proving one is enough to get an idea of the other.

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

**4. De Morgan’s Law**

It states that the complement of the union of two sets is equal to the intersection of their complements.

Whereas the complement of the intersection of two sets is equal to the union of their complements.

(A ∪ B)’ = A’ ∩ B’

(A ∩ B)’ = A’ ∪ B’