The Foundation of Mathematics: An Introduction to Set Theory

There are two ways to do great mathematics. The first is to be smarter than everybody else. The second way is to be stupider than everybody else — but persistent, Raoul Bott.

 

An Introduction to Set Theory

Set Theory is the fundamental language of modern mathematics. Almost every mathematical concept—from numbers and functions to geometry and probability—is built on the foundation of sets.

At its most basic level in Naive Set Theory, a set is a well-defined collection of distinct objects. The objects within the collection are called the elements (or members) of the set.

Two critical rules govern the structure of a set:

1. Order is irrelevant: The set $\{1, 2, 3\}$ is exactly identical to the set $\{3, 1, 2\}$.
2. No multiplicity: Elements in a set cannot be repeated. The collection $\{1, 1, 2, 2, 3\}$ simply collapses into the set $\{1, 2, 3\}$.

If an element $x$ belongs to a set $S$, we denote this using the “element of” symbol: $x \in S$. If $x$ does not belong to $S$, we write $x \notin S$.

Two sets $A$ and $B$ are equal ($A = B$) if and only if they contain the exact same elements.

Describing Sets

There are two primary ways to define the contents of a set.

1. The Roster Method (Listing). For finite, small sets, we can simply list all the elements separated by commas and enclosed in curly braces, e.g, $V = \{a, e, i, o, u\} and E = \{0, 2, 4, 6, 8\}$.
2. Set-Builder Notation. For infinite sets, or sets with complex rules, listing elements is impossible. Instead, we use set-builder notation, which defines the properties an element must satisfy to be included. The syntax is generally $\{ \text{expression} \mid \text{rule} \}$, read as “the set of all [expression] such that [rule] is true.” Sometimes a colon “:” is used instead of a vertical bar “|”, e.g.:
   The set of even natural numbers: $\{ n \in \mathbb{N} \mid n = 2k \text{ for some } k \in \mathbb{N} \}$
   The set of prime numbers: $\{ p \in \mathbb{N} \mid p \text{ is strictly divisible only by 1 and itself} \}$
   The set of numbers between 10 and 1000: $\{ n \in \mathbb{N} \mid 10 \le n \le 1000 \}$

Famous Number Sets

Throughout mathematics, specific infinite sets are used so frequently that they are assigned dedicated “blackboard bold” letters:

• Natural Numbers, $\mathbb{N}$: The set of counting numbers. $\{0, 1, 2, 3, \dots\}$
• Integers, $\mathbb{Z}$: The set of all whole numbers, including negatives. $\{\dots, -2, -1, 0, 1, 2, \dots\}$
• Rational Numbers, $\mathbb{Q}$: The set of all fractions made of integers (where the denominator is not zero). $\{ \frac{m}{n} \mid m, n \in \mathbb{Z} \text{ and } n \neq 0 \}$
• Real Numbers, $\mathbb{R}$: The continuous number line, containing all rational numbers and all irrational numbers (like $\pi, e, \sqrt{2}$).
• Complex Numbers, $\mathbb{C}$: Numbers that include the imaginary unit $i = \sqrt{-1}$. $\{ a + bi \mid a, b \in \mathbb{R} \}$

We can also define continuous chunks of the real number line called intervals.

• Open intervals use parentheses $()$ and do not include the endpoints: $(a, b) = \{x \in \mathbb{R} \mid a < x < b\}$
• Closed intervals use brackets $[]$ and do include the endpoints: $[a, b] = \{x \in \mathbb{R} \mid a \le x \le b\}$

Subsets and the Power Set

A set $A$ is a subset of set $B$ if every element of $A$ is also an element of $B$. We denote this as $A \subseteq B$.

Notice the line under the symbol; it implies that $A$ may be equal to $B$. Every set is a subset of itself ($A \subseteq A$).

If $A$ is a subset of $B$, but $A$ is not equal to $B$ (meaning $B$ contains at least one extra element that $A$ does not), then $A$ is called a proper subset of $B$. We denote this by dropping the bottom line: $A \subset B$. Example: $\{1, 2\} \subset \{1, 2, 3\}$, but $\{1, 2\} \subseteq \{1, 2\}$.

The empty set is a unique set containing absolutely no elements. It is denoted by $\emptyset$ or $\{\}$. A profound rule of set theory is that the empty set is a subset of every set ($\emptyset \subseteq A$).

If we collect all possible subsets of a given set $S$, we create a new, larger set called the Power Set, denoted $\mathcal{P}(S)$. Example: If $S = \{a, b\}$, then $\mathcal{P}(S) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.

The Algebra of Sets

Just as we can add and multiply numbers to create new numbers, we can perform operations on sets to create new sets. We visualize these operations using Venn Diagrams.

1. Intersection ($\cap$). The intersection of sets $A$ and $B$ is the set containing only the elements that belong to both $A$ and $B$ simultaneously. $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$
   Example: $\{1, 2, 3, 4\} \cap \{3, 4, 5, 6\} = \{3, 4\}$.
   If $A \cap B = \emptyset$, the sets share no elements and are called disjoint.

2. Union ($\cup$). The union of sets $A$ and $B$ is the set containing all elements that belong to $A$, or $B$, or both. $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$
   Example: $\{1, 2, 3\} \cup \{3, 4, 5\} = \{1, 2, 3, 4, 5\}$.

3. Difference ($\setminus$ or $-$). The difference between $A$ and $B$ (read as “$A$ minus $B$”) is the set of elements that belong to $A$ but do not belong to $B$. $A \setminus B = \{x \mid x \in A \text{ and } x \notin B\}$.
   Example: $\{1, 2, 3, 4, 5\} \setminus \{4, 5, 6, 7\} = \{1, 2, 3\}$.

4. Complement ($A^c$ or $A'$). If we are working within a specific “Universal Set” $U$ (for example, all integers), the complement of $A$ is the set of all elements in $U$ that are not in $A$. $A^c = \{x \in U \mid x \notin A\}$
   Notice two absolute rules of complements:
   $\star$ A set and its complement combine to form everything: $A \cup A^c = U$.
   $\star$ A set and its complement share nothing: $A \cap A^c = \emptyset$.

5. The Cartesian Product ($\times$). Unlike the operations above which only rearrange existing elements around, the Cartesian Product builds entirely new structures. $A \times B$ is the set of all possible ordered pairs $(a, b)$ where the first item comes from $A$ and the second comes from $B$. $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$
   Example: $\{1, 2\} \times \{\text{Red}, \text{Blue}\} = \{(1, \text{Red}), (1, \text{Blue}), (2, \text{Red}), (2, \text{Blue})\}$.

Proving Set Equality: Double Inclusion

In algebra, proving $x = y$ is usually straightforward. In set theory, proving two sets are equal ($A = B$) requires a specific logical framework called Double Inclusion.

To prove $A = B$, you must prove two things separately:

1. $A \subseteq B$, every element of $A$ is also an element of $B$.
2. $B \subseteq A$, every element of $B$ is also an element of $A$.

If both are true, the sets must be identical.

Example: Proving De Morgan’s Law

Let’s use Double Inclusion to prove one of De Morgan’s Laws: The complement of a union is the intersection of the complements. $(A \cup B)^c = A^c \cap B^c$

Part 1: Prove $(A \cup B)^c \subseteq A^c \cap B^c$

1. Let $x$ be an arbitrary element such that $x \in (A \cup B)^c$.
2. By the definition of the complement, this means $x \notin (A \cup B)$.
3. If $x$ is not in the union of $A$ and $B$, it means $x$ cannot be in $A$, and $x$ cannot be in $B$. Therefore, $x \notin A$ and $x \notin B$.
4. By the definition of the complement, $x \in A^c$ and $x \in B^c$.
5. Since $x$ is in both sets, by the definition of intersection, $x \in (A^c \cap B^c)$.
6. Therefore, $(A \cup B)^c \subseteq A^c \cap B^c$.

Part 2: Prove $A^c \cap B^c \subseteq (A \cup B)^c$

1. Let $x$ be an arbitrary element such that $x \in (A^c \cap B^c)$.
2. By the definition of intersection, $x \in A^c$ and $x \in B^c$.
3. By the definition of complement, $x \notin A$ and $x \notin B$.
4. Since $x$ is in neither $A$ nor $B$, it cannot be in their union. Therefore, $x \notin (A \cup B)$.
5. By the definition of complement, $x \in (A \cup B)^c$.
6. Therefore, $A^c \cap B^c \subseteq (A \cup B)^c$.

Since we have proven inclusion in both directions, the two sets are exactly equal. $\blacksquare$

The Algebra of Sets, Logic, and Cardinality

Set theory is not just about categorizing objects; it is an algebra in its own right. Just as we manipulate equations in standard algebra, we can manipulate sets using a strict set of algebraic laws.

The Laws of Set Algebra. Let $U$ be a universal set, and let $A, B$, and $C$ be arbitrary subsets of $U$. The following fundamental laws govern how these sets interact:

• Idempotency: Operating a set with itself yields itself. $A \cup A = A \quad \text{and} \quad A \cap A = A$
• Identity: $A \cup \emptyset = A \quad \text{and} \quad A \cap U = A$
• Absorption (Domination): $A \cup U = U \quad \text{and} \quad A \cap \emptyset = \emptyset$
• Complements: $A \cup A^c = U \quad \text{and} \quad A \cap A^c = \emptyset$
• Commutativity: Order does not matter. $A \cup B = B \cup A \quad \text{and} \quad A \cap B = B \cap A$
• Associativity: Grouping does not matter for identical operations. $A \cup (B \cup C) = (A \cup B) \cup C \quad \text{and} \quad A \cap (B \cap C) = (A \cap B) \cap C$
• Distributivity: Operations distribute over one another.

1. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
2. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Proving Distributivity via Double Inclusion

Let’s rigorously prove the first Distributive Law: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

Part 1: Prove $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ Let $x \in A \cup (B \cap C)$. By the definition of union, there are two cases:

• Case 1: $x \in A$. If $x$ is in $A$, it is automatically in any union involving $A$. Therefore, $x \in (A \cup B)$ and $x \in (A \cup C)$. Because $x$ is in both, $x \in (A \cup B) \cap (A \cup C)$.
• Case 2: $x \in (B \cap C)$. By definition, $x \in B$ and $x \in C$. Since $x \in B$, we know $x \in (A \cup B)$. Since $x \in C$, we know $x \in (A \cup C)$. Because it is in both, $x \in (A \cup B) \cap (A \cup C)$.

Since both cases lead to the target set, the forward inclusion is proven.

Part 2: Prove $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$

Let $x \in (A \cup B) \cap (A \cup C)$. By definition, $x$ is in both $(A \cup B)$ and $(A \cup C)$. Again, we have two cases:

• Case 1: $x \in A$. If $x$ is in $A$, then by the definition of union, $x \in A \cup (B \cap C)$.
• Case 2: $x \notin A$. Because we know $x \in (A \cup B)$ but $x$ is not in $A$, it must be true that $x \in B$. Similarly, because $x \in (A \cup C)$ but $x \notin A$, it must be true that $x \in C$. Since $x \in B$ and $x \in C$, we have $x \in (B \cap C)$. Therefore, $x \in A \cup (B \cap C)$.

By double inclusion, the two sets are exactly equal. $\blacksquare$

De Morgan’s Laws

The most famous theorems in set algebra deal with how complements interact with unions and intersections.

Theorem: The complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements. $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$.

These laws can be generalized to infinite families of sets $\{A_i\}_{i \in I}$: $\left( \bigcup_{i \in I} A_i \right)^c = \bigcap_{i \in I} A_i^c \quad \text{and} \quad \left( \bigcap_{i \in I} A_i \right)^c = \bigcup_{i \in I} A_i^c$

The Logic-Set Connection: Truth Tables

Truth tables. Mathematics normally uses a two-valued logic: every statement is either true or false and not both.

There is a perfect isomorphic mirror between Set Theory and Boolean Logic. Every set operator has a direct logical equivalent:

• Intersection ($\cap$) $\equiv$ Logical AND ($\land$)
• Union ($\cup$) $\equiv$ Logical OR ($\lor$)
• Complement ($^c$) $\equiv$ Logical NOT ($\neg$)

Because of this mapping, we can prove set theory properties by building truth tables. If the logical columns for two expressions perfectly match for every possible combination of True (T) and False (F), the corresponding sets are equal.

Truth tables provide another way of proving set-theoretical properties, e.g., De Morgan’s laws.

p	q		AND	OR	XOR	NAND	NOR
T	T		T	T	F	F	F
T	F		F	T	T	T	F
F	T		F	T	T	T	F
F	F		F	F	F	T	T

XOR (Exclusive or) is a logical operation that is true if and only if its arguments differ (one is true, the other is false). NAND (not and) is described loosely as “not both” and is equivalent to the negation of the “and” operation. It produces a value of true if and only if at least one of the propositions is false. NOR (logical NOR) is the negation of the logical OR, a sentence of the form $p\ \mathrm{NOR}\ q$ is true when neither $p$ nor $q$ is true, i.e., when both are false.

Cardinality and Finite Sets

The cardinality of a set is the number of distinct elements it contains. For a finite set $S$, we denote its cardinality using vertical bars: $\vert{}S\vert{}$.

Example: If $S = \{a, b, c\}$, then $\vert{}S\vert{} = 3$. The cardinality of the empty set is $\vert{}\emptyset\vert{} = 0$.

The Principle of Inclusion-Exclusion. If we want to find the total number of elements in the union of two finite sets, we cannot simply add their cardinalities together.

Theorem: For any finite sets $A$ and $B$, $\vert{}A \cup B\vert{} = \vert{}A\vert{} + \vert{}B\vert{} - \vert{}A \cap B\vert{}$

Example. $A = \{a, b, c, d, e\}, B = \{a, e, i, o, u\}, A \cap B = \{a, e\}, A \cup B = \{a, b, c, d, e, i, o, u\}$, and $\vert{} A \cup B\vert{} = \vert{}A\vert{} + \vert{}B\vert{} − \vert{}A \cap B\vert{} = 5 + 5 - 2 = 8$.

Proof:

We can partition the union $A \cup B$ into three strictly disjoint (non-overlapping) sets:

1. Elements only in $A$: $(A \setminus B)$
2. Elements only in $B$: $(B \setminus A)$
3. Elements in both: $(A \cap B)$

Because these three sets are mutually disjoint, we can safely add their cardinalities: $\vert{}A \cup B\vert{} = \vert{}A \setminus B\vert{} + \vert{}B \setminus A\vert{} + \vert{}A \cap B\vert{}$

Now, observe that the total size of $A$ is made of the elements only in $A$, plus the intersection: $\vert{}A\vert{} = \vert{}A \setminus B\vert{} + \vert{}A \cap B\vert{}$. Therefore, $\vert{}A \setminus B\vert{} = \vert{}A\vert{} - \vert{}A \cap B\vert{}$. Similarly, $\vert{}B \setminus A\vert{} = \vert{}B\vert{} - \vert{}A \cap B\vert{}$.

Substitute these back into our first equation:

$$\begin{aligned} \vert{}A \cup B\vert{} &= (\vert{}A\vert{} - \vert{}A \cap B\vert{}) + (\vert{}B\vert{} - \vert{}A \cap B\vert{}) + \vert{}A \cap B\vert{} \\ &= \vert{}A\vert{} + \vert{}B\vert{} - \vert{}A \cap B\vert{} \quad \blacksquare \end{aligned}$$

Intuition: If you simply calculate $\vert{}A\vert{} + \vert{}B\vert{}$, you are counting the overlapping elements (the intersection) twice—once when you count $A$, and once when you count $B$. You must subtract $\vert{}A \cap B\vert{}$ once to correct for this double-counting.

Cardinality of the Power Set. The Power Set $\mathcal{P}(A)$ is the set of all possible subsets of $A$. How big is the power set?

Theorem: If a finite set $A$ has cardinality $\vert{}A\vert{} = n$, then its power set has cardinality $\vert{}\mathcal{P}(A)\vert{} = 2^n$.

Proof by Mathematical Induction:

• Base Case ($n=0$): If $\vert{}A\vert{} = 0$, then $A = \emptyset$. The only subset of the empty set is the empty set itself. Thus, $\mathcal{P}(\emptyset) = \{\emptyset\}$. The cardinality is $1$, and $2^0 = 1$. The base case holds.

• Inductive Step: Assume the theorem is true for any set of size $n$, so $\vert{}\mathcal{P}(S)\vert{} = 2^n$. Let $A$ be a set with $n+1$ elements. We can isolate one specific element from $A$ and call it $a$. The remaining elements form a subset $A' = A \setminus \{a\}$, which has exactly $n$ elements.

Every possible subset of $A$ falls strictly into one of two disjoint categories:

1. Subsets that do not contain $a$. These are exactly the subsets of $A'$. By our inductive hypothesis, there are $2^n$ of these.
2. Subsets that do contain $a$. You can create all of these by taking every subset from category 1 and tossing the element $a$ into it. Since we are doing a 1-to-1 mapping, there are exactly $2^n$ of these as well.

Because these two categories are disjoint, we simply add them together: $\vert{}\mathcal{P}(A)\vert{} = 2^n + 2^n = 2 \cdot 2^n = 2^{n+1}$

By the principle of induction, the theorem holds for all $n \in \mathbb{N}$. $\blacksquare$