Set Theory is a branch of Maths where we learn about sets and their properties. What is a set? It is **a well-defined collection of things or objects, such as animals, plants, vowels** (a, e, i, o, u), swearwords, etc. Yes, you’ve guessed it, I am not going to give examples of these! Basically, it is **a list or a group of unordered items** which means: The order is irrelevant, {1, 2} is the same set as {2, 1}; and the elements are not repeated.

Sets are written using curly brackets that contain the elements of the set. For example, the set containing a_{1}, a_{2}, a_{3}, …, a_{n} is written as {a_{1}, a_{2}, a_{3}, …, a_{n}}. Sets can be described by properties that the elements satisfy. If P is a property, the set is a subset of some larger set S, then the expression { x ∈ S | P(x)} or { x ∈ S : P(x)} denotes the set of all elements of S that satisfy P. For example, the set of odd natural numbers can be represented by the following equal sets, { n ∈ ℕ : n = 2k + 1 for some k ∈ ℕ} = {1, 3, 5, 7, …}

For a set S, we write x ∈ S to mean that x is an element or an object of S. We write x ∉ S to mean that x is **not** an element or an object of S. Two sets S and T are **equal** *if and only if they contain or have the same elements*, and in that case we can express it by writing S = T.

The **empty set** is a set which has no elements. A set with one element is called a singleton, e.g., {a} is a singleton. It is denoted by ∅. A set A is a **subset** of another set B if all elements of A are also elements of B. It is denoted by A ⊂ B. It is possible for A and B to be equal; if they are unequal, i.e., A ⊂ B and A ≠ B, then A is a **proper subset** of B.

The set of **integers** is denoted by the doublestruck capital letter ℤ = {…, -2, -1, 0, 1, 2, …}. It is the set of all positive whole numbers, all negative numbers, and zero. The set or **rational numbers** is denoted by the doublestruck capital letter ℚ. It is the set of all fractions with integer numerators and non-zero integer denominators.
ℚ = {^{m}⁄_{n}: m, n ∈ ℤ, n > 0}.

The set of **irrational numbers** includes all non-terminating, non-repeating decimals. The following are examples of irrational numbers: √2, √3, π. The set of rational and irrational numbers constitute the set of **real numbers.** It is denoted by ℝ. It includes all numbers with a decimal expansion. Finally, the set of **complex numbers**, ℂ = {a + bi : a, b ∈ R}, where i = √-1.

A bounded interval has real numbers for both endpoints. Given two real numbers a, b with a ≤ b we define four **bounded intervals**: (a, b) = {x ∈ ℝ : a < x < b}, [a, b] = {x ∈ ℝ : a ≤ x ≤ b}, [a, b) = {x ∈ ℝ : a ≤ x < b}, and (a, b] = {x ∈ ℝ : a < x ≤ b}; and four **unbounded intervals**: (a, ∞) = {x ∈ ℝ : a < x} , [a, ∞) = {x ∈ ℝ : a ≤ x} , (−∞, a) = {x ∈ ℝ : x < a} , (−∞, a] = {x ∈ ℝ : x ≤ a}. Bounded and unbounded intervals can also be closed or open intervals. Open intervals have *parentheses and do not include endpoints*. Closed intervals, which have *brackets instead of parentheses, include endpoints*.

The **power set** of a set S, denoted P(S), is the set of all subsets of S, e.g., power({a, b}) = {∅, {a}, {b}, {a, b}}.

The **Cartesian product** A x B of two sets A and B is **the set of all ordered pairs (a, b), where the first element of each pair, a, is an element from A, and the second, b, is an element from B**. We could express this in mathematical language as A x B = {(a, b): a ∈ A and b ∈ B}.

The **intersection** A ∩ B of two sets A and B is *a new set containing all the elements common to both sets*. Formally, A ∩ B = {x ∈ S: x ∈ A and x ∈ B}. If the intersection is empty (A ∩ B = ∅), the sets are said to be **disjoint** because they do not have any common members or elements.

The **union** A ∪ B of two sets A and B is **a new set containing all the elements of A plus all the elements of B and nothing else**. Formally, A ∪ B = {x ∈ S: x ∈ A or x ∈ B}.

The **complement** of a set A, written A^{c} is the subset consisting of those elements of the universal set (S) that are not elements of the set, that is, A^{c} ={ x ∈ S : x ∉ A}.

The **difference** A - B between two sets A and B, written A\B, is **the set containing all the elements that are in the first set, but not in the second one**: A\B = {x ∈ A : x ∉ B} = A ∩ B^{c}.

A **Venn diagram** is a widely used diagram style that shows the logical relation between sets. They are commonly used in school to teach basic math concepts such as sets, unions, and intersections.

We can describe a set by associating its elements with members of an index set. We can write A = {A_{i}: i ∈ I} where the set I is the index set. Now, we can define unions and intersections over an index set as:
∪_{i∈I}A_{i} = { x : x ∈ A_{i} for some i ∈ I} = {x : ∃i ∈ I and x ∈ A_{i}} and
∩_{i∈I}A_{i} = { x : x ∈ A_{i} for all i ∈ I} = {x : ∀i ∈ I, x ∈ A_{i}}

**Double inclusion**. Let A and B be two subsets of a set S. Then A = B if and only if, aka **iff**, A ⊆ B and B ⊆ A.
Proof: If A = B, then every element in A is an element of B, i.e., ∀x ∈ A, x ∈ B, so certainly A ⊆ B, and ceteris paribus (‘all else being equal’) B ⊆ A.

Let’s suppose that A ⊆ B and B ⊆ A. Then, for every element x ∈ S, if x ∈ A, then x ∈ B because A ⊆ B. Otherwise, if x ∉ A, then x ∉ B. That’s because B ⊆ A, that is, ∀x ∈ B, x ∈ A.

**Distributive Laws**. Let A, B, C be subsets of a set S. Then,

- (i) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- (ii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Proof. (i) Let’s suppose that x ∈ A ∪ (B ∩ C) ⇨ (then or this means that) x ∈ A, x ∈ (B ∩ C) or both. If x ∈ A ⇨ x ∈ (A ∪ B) and x ∈ (A ∪ C), and therefore x ∈ (A ∪ B) ∩ (A ∪ C). If x ∈ (B ∩ C), then x ∈ (A ∪ B) and x ∈ (A ∪ C), and therefore x ∈ (A ∪ B) ∩ (A ∪ C). So we have demonstrated that A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).

Let’s suppose that x ∈ (A ∪ B) ∩ (A ∪ C), then x ∈ (A ∪ B) and x ∈ (A ∪ C). Then, if x ∈ A ⇨ x ∈ (A ∪ B) ∩ (A ∪ C). Otherwise, if x ∉ A ⇨ x ∈ B and x ∈ C ⇨ x ∈ A ∪ (B ∩ C). So we have demonstrated that (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C), and by double inclusion, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (i).

The proof of (ii) is quite similar. May the force be with you as you try to prove it 😄.

**De Morgan’s laws. The complement of the union of two sets is the intersection of their complements and the complement of the intersection of two sets is the union of their complements**. More formally, let A and B be two subsets of a bigger set S. Then, the Morgan’s laws are as follows,
(A ∪ B)^{c} = A^{c} ∩ B^{c}, and (A ∩ B)^{c} = A^{c} ∪ B^{c}.

Proof.
Suppose x ∈ (A ∪ B)^{c} ⇨ x is not in either A or B ⇨ x ∈ A^{c} and x ∈ B^{c} ⇨ x ∈ A^{c} ∩ B^{c}. Therefore, (A ∪ B)^{c} ⊆ A^{c} ∩ B^{c}

Conversely, suppose x ∈ A^{c} ∩ B^{c} ⇨ x ∈ A^{c} and x ∈ B^{c} ⇨ x ∉ A and x ∉B, so x is in neither A nor B, and therefore x ∈ (A ∪ B)^{c}. Therefore, A^{c} ∩ B^{c} ⊆ (A ∪ B)^{c}.

(A ∪ B)^{c} ⊆ A^{c} ∩ B^{c} and A^{c} ∩ B^{c} ⊆ (A ∪ B)^{c}, and by double inclusion, (A ∪ B)^{c} = A^{c} ∩ B^{c}. The proof of (A ∩ B)^{c} = A^{c} ∪ B^{c} is quite similar. May the force be with you as you try to prove it 😄.

De Morgan’s laws can be easily generalized to any number of sets. If {A_{i}: i ∈ I} is a family of subsets of S, then
(∩_{i∈I}A_{i})^{c} = ∪_{i∈I}A_{i}^{c} and (∪_{i∈I}A_{i})^{c} = ∩_{i∈I}A_{i}^{c}

**Truth tables.** Mathematics normally uses a two-valued logic: every statement is either true or false. We can use **truth tables to determine how the truth or falsity of a complicated statement depends on the truth or falsity of its components**. They provide another way of *proving set-theoretical identities*, e.g., De Morgan’s laws.

**Cardinality.** The *number of distinct elements that make up or are contained in a set* is called the **cardinality**. It is denoted by vertical bars, like absolute value signs; for instance, for a set A its cardinality is denoted by |S|.

More formally, the empty set ∅ is finite with |∅| = 0. A set S is finite with |S| = n + 1, if there exists s ∈ S such that |S\{s}| = n for some n ∈ N. Any set that is not finite is said to be infinite. In other words, if S = {x_{1}, x_{2}, . . . x_{n}}, x_{i} ≠ x_{j} ∀ i ≠ j, then |S| = n.

Let A and B be finite sets. Then |A ∪ B| = |A| + |B| − |A ∩ B|. Simply, the number of elements in the union of set A and B is equal to the sum of elements of the sets A and B, minus that of their intersection.

If a set A is finite with |A| = n, then its power set has |P(A)| = 2^{n}.

Proof.

- If |A| = 0 ⇨ A = ∅, so it is the empty set with no elements, and a single subset, ∅, and therefore |P(A)| = 2
^{n}= 2^{0}= 1. - Let’s suppose that n ≥ 0 and that |P(S)| = 2
^{n}∀S: |S| = n. Let A be any set with |A| = n + 1, so there is an element “a” and a set A’ = A\a with |A’| = n. Any subset of A must either contain “a” or not, so P(A) = P(A’) ∪ {S ∪ {a} : S ∈ P(A’)}.

These two subsets are obviously disjoint, and therefore (If A, B are disjoint, |A ∪ B| = |A| + |B|):

|P(A)| = |P(A’)| + |{S ∪ {a} : S ∈ P(A’)}| = 2^{n} + 2^{n} [These two sets has the same cardinality and by our induction hypothesis, |P(A’)| = 2^{n}] = 2^{n+1}.