Set Theory Fundamentals

⚡ Key Takeaways

Set theory is the mathematical study of collections of objects. A set is any well-defined collection of distinct things; from this single idea, all of modern mathematics — numbers, functions, relations, infinity — can be constructed. Founded by Georg Cantor in the 1870s, it is the universal language underlying virtually every branch of mathematics.

💡 The Core Insight

A set is determined entirely by its members — nothing else. Two sets are equal precisely when they contain exactly the same elements (the Axiom of Extensionality). Order does not matter, and repetition does not matter: $\{1,2,3\}$ , $\{3,2,1\}$ , and $\{1,1,2,3\}$ are all the same set. This stripped-down notion of "collection" is so general that it can model nearly any mathematical object.

DefinitionSet, Element, and Membership

A set is a well-defined collection of distinct objects. If an object $x$ is a member of a set $A$ , we write:

1

\quad x \in A

Derivation hint: This is primitive notation — $\in$ is read "is an element of" and is not defined in terms of anything simpler; it is the fundamental relation of set theory. If $x$ is not a member of $A$ , we write $x \notin A$ . The symbols mean:

$x$ — an object (which may itself be a set)
$A$ — a set
$\in$ — the membership relation

DefinitionSet-Builder and Roster Notation

Sets are written in two main ways. Roster (list) notation lists members between braces:

2

\quad A = \{2, 4, 6, 8\}

Derivation hint: The braces $\{\,\}$ denote "the set whose elements are exactly these"; order and repetition are irrelevant by extensionality.

Set-builder notation specifies a defining property $P(x)$ :

3

\quad B = \{\, x \mid P(x)\,\}

Derivation hint: Read " $\mid$ " as "such that"; $B$ is the set of all $x$ for which the statement $P(x)$ is true. E.g. $\{x \mid x \text{ is even and } 0 < x < 10\} = \{2,4,6,8\}$ .

DefinitionThe Empty Set

The empty set, written $\varnothing$ or $\{\}$ , is the unique set with no elements:

4

\quad \varnothing = \{\, x \mid x \neq x\,\}

Derivation hint: Since nothing satisfies $x \neq x$ , this collection has no members. Uniqueness follows from extensionality — any two empty sets contain "exactly the same elements" (namely none).

DefinitionSubset and Equality

A set $A$ is a subset of $B$ (written $A \subseteq B$ ) if every element of $A$ is also in $B$ :

5

\quad A \subseteq B \iff (\forall x)(x \in A \implies x \in B)

Derivation hint: $\forall$ means "for all"; the arrow means "implies." This says membership in $A$ guarantees membership in $B$ . Two sets are equal exactly when each is a subset of the other:

6

\quad A = B \iff (A \subseteq B \,\wedge\, B \subseteq A)

Derivation hint: This is the Axiom of Extensionality in operational form — sets with mutual containment have identical members. $\wedge$ means "and." A proper subset ( $A \subsetneq B$ ) means $A \subseteq B$ but $A \neq B$ .

DefinitionSet Operations

For sets $A$ and $B$ inside a universal set $U$ :

7

\quad A \cup B = \{\, x \mid x \in A \,\vee\, x \in B\,\}

Derivation hint: The union collects everything in either set; $\vee$ means "or" (inclusive).

8

\quad A \cap B = \{\, x \mid x \in A \,\wedge\, x \in B\,\}

Derivation hint: The intersection collects only what is in both sets simultaneously.

9

\quad A \setminus B = \{\, x \mid x \in A \,\wedge\, x \notin B\,\}

Derivation hint: The difference ("relative complement") keeps elements of $A$ that are absent from $B$ .

10

\quad A^{c} = U \setminus A = \{\, x \in U \mid x \notin A\,\}

Derivation hint: The complement is everything in the universe $U$ that lies outside $A$ .

TheoremPower Set and Its Size

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$ . If $A$ has $n$ elements (is finite of cardinality $n$ ), then:

11

\quad |\mathcal{P}(A)| = 2^{n}

Derivation hint: Each subset is formed by deciding, independently, "in or out" for each of the $n$ elements — giving $2 \times 2 \times \cdots \times 2 = 2^n$ choices.

TheoremCantor's Theorem

For any set $A$ (finite or infinite), its power set is strictly larger:

12

\quad |A| < |\mathcal{P}(A)|

Derivation hint: There can be no surjection from $A$ onto $\mathcal{P}(A)$ ; the proof builds a "diagonal" subset that no element of $A$ can be mapped to. This shows infinities come in different sizes.

ProofDe Morgan's Laws

We prove the first De Morgan law, $(A \cup B)^c = A^c \cap B^c$ , by showing mutual subset inclusion (equation [6]).

Step 1. Take any $x \in (A \cup B)^c$ . By definition of complement [10], $x \notin A \cup B$ .

Step 2. By definition of union [7], $x \notin A \cup B$ means it is false that ( $x \in A$ or $x \in B$ ). By logic, this is equivalent to ( $x \notin A$ and $x \notin B$ ).

Step 3. Thus $x \in A^c$ and $x \in B^c$ , so by definition of intersection [8], $x \in A^c \cap B^c$ . This proves $(A\cup B)^c \subseteq A^c \cap B^c$ .

Step 4. Now take any $y \in A^c \cap B^c$ . Then $y \notin A$ and $y \notin B$ , so $y$ is in neither set, hence $y \notin A \cup B$ , hence $y \in (A \cup B)^c$ . This proves the reverse inclusion.

Step 5. Both inclusions hold, so by [6] the sets are equal. $\blacksquare$

∎

ProofCantor's Theorem by Diagonalization

We show no function $f: A \to \mathcal{P}(A)$ can be surjective (hit every subset).

Step 1. Suppose, for contradiction, that $f$ is a surjection. For each $x \in A$ , $f(x)$ is a subset of $A$ .

Step 2. Define the "diagonal" set:

\quad D = \{\, x \in A \mid x \notin f(x)\,\}.

This $D$ is a subset of $A$ , so $D \in \mathcal{P}(A)$ .

Step 3. Since $f$ is assumed surjective, there exists some $d \in A$ with $f(d) = D$ .

Step 4. Ask: is $d \in D$ ? By the definition of $D$ , $d \in D \iff d \notin f(d) = D$ . So $d \in D$ if and only if $d \notin D$ — a contradiction.

Step 5. The assumption fails: no surjection exists. Hence $|A| < |\mathcal{P}(A)|$ . $\blacksquare$

∎

mathematician · Georg Cantor | 1845–1918

Georg Cantor, a German mathematician born in St. Petersburg, single-handedly created set theory in the 1870s–1880s. He proved that the rational numbers are countable but the real numbers are not, establishing that infinity comes in different sizes. His introduction of cardinal and ordinal numbers and the "diagonal argument" revolutionized mathematics. His ideas met fierce resistance — Leopold Kronecker called them dangerous — and Cantor suffered repeated depressive episodes. Today his work is foundational to nearly all of modern mathematics.

🧠 Intuition

Think of a set as a box with no order and no duplicates — only the question "is this thing in the box?" matters. A subset is a box whose contents are entirely contained in a bigger box. Union is dumping two boxes together (throwing away duplicates); intersection is keeping only what both boxes share. The power set is the box containing every possible smaller box you could form — and Cantor's theorem says this "box of boxes" is always strictly bigger than the original, even when the original is infinite. The empty set is the box with nothing in it — and crucially, the empty box is still a box, which is why $\varnothing$ is a perfectly good set.

Figure

Venn diagram of two sets showing union, intersection, and complement within a universal set U

ExamplePower Set of a 3-Element Set

Given: $A = \{a, b, c\}$ . Find $\mathcal{P}(A)$ and verify equation [11].

Step 1. By [11], the number of subsets is $2^n = 2^3 = 8$ .

Step 2. List all subsets by size:

Size 0: $\varnothing$
Size 1: $\{a\}, \{b\}, \{c\}$
Size 2: $\{a,b\}, \{a,c\}, \{b,c\}$
Size 3: $\{a,b,c\}$

Step 3. Count: $1 + 3 + 3 + 1 = 8$ . ✓ (These are the binomial coefficients $\binom{3}{0},\binom{3}{1},\binom{3}{2},\binom{3}{3}$ .)

\boxed{\;\mathcal{P}(A) = \big\{\,\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\,\big\},\quad |\mathcal{P}(A)| = 8\;}

ExampleSet Operations with Numbers

Given: Universe $U = \{1,2,3,4,5,6,7,8,9,10\}$ , $A = \{1,2,3,4,5\}$ , $B = \{4,5,6,7\}$ .

Step 1. Union [7]: combine all elements (no repeats):

A \cup B = \{1,2,3,4,5,6,7\}.

Step 2. Intersection [8]: keep shared elements:

A \cap B = \{4,5\}.

Step 3. Difference [9]: $A$ minus what is in $B$ :

A \setminus B = \{1,2,3\}.

Step 4. Complement [10]: $U$ minus $A$ :

A^c = \{6,7,8,9,10\}.

Step 5. Verify De Morgan [proof above]: $(A \cup B)^c = \{8,9,10\}$ . Also $A^c \cap B^c = \{6,7,8,9,10\} \cap \{1,2,3,8,9,10\} = \{8,9,10\}$ . ✓

\boxed{\;A\cup B=\{1,...,7\},\ A\cap B=\{4,5\},\ A\setminus B=\{1,2,3\},\ A^c=\{6,...,10\}\;}

⚠️ Element vs. Subset

The two most confused relations are membership ( $\in$ ) and subset ( $\subseteq$ ). For $A = \{1, 2, \{3\}\}$ :

$1 \in A$ ✓ (1 is an element)
$1 \subseteq A$ ✗ (1 is not even a set; this is meaningless/false)
$\{1\} \subseteq A$ ✓ (the set containing 1 is a subset)
$\{1\} \in A$ ✗ (the set $\{1\}$ is not listed as an element)
$\{3\} \in A$ ✓ (the set $\{3\}$ is a listed element)

Also note: $\varnothing \subseteq A$ for every set (vacuously true), but $\varnothing \in A$ only if $\varnothing$ is explicitly an element.

CounterexampleNaïve Comprehension Fails — Russell's Paradox

One might think any property $P(x)$ defines a set $\{x \mid P(x)\}$ . This is false. Consider:

R = \{\, x \mid x \notin x\,\} \quad\text{("the set of all sets that are not members of themselves").}

Ask: is $R \in R$ ? If $R \in R$ , then by its defining property $R \notin R$ . If $R \notin R$ , then it satisfies the property, so $R \in R$ . Both cases contradict — so $R$ cannot exist as a set. This 1901 paradox showed naïve set theory is inconsistent, forcing the development of axiomatic set theory (ZFC), which restricts which collections count as sets.

connection

Set theory is the connective tissue of mathematics. Functions and Relations are defined as sets of ordered pairs. The number systems of Natural Numbers are constructed set-theoretically (e.g., $0 = \varnothing$ , $1 = \{\varnothing\}$ , $2 = \{\varnothing, \{\varnothing\}\}$ ). Mathematical Logic supplies the symbols $\forall, \exists, \wedge, \vee$ that set-builder notation relies on. Cardinality and Infinity extends counting to infinite sets via Cantor's theorem [12]. And Probability Theory defines events as subsets of a sample space, with union and intersection encoding "or" and "and."

🔬 Where this appears

⏳ History

- 1874 — Georg Cantor publishes his first paper proving the algebraic numbers are countable and the reals are not, launching set theory.

- 1878 — Cantor formulates the Continuum Hypothesis: there is no infinity strictly between

|\mathbb{N}|

and

|\mathbb{R}|

.

- 1883 — Cantor introduces transfinite ordinal and cardinal numbers.

- 1891 — Cantor publishes the diagonal argument, the cleanest proof of

|A| < |\mathcal{P}(A)|

(equation [12]).

- 1901 — Bertrand Russell discovers Russell's Paradox, exposing the inconsistency of naïve comprehension.

- 1908 — Ernst Zermelo proposes the first axiomatization of set theory to avoid paradoxes.

- 1922 — Abraham Fraenkel and Thoralf Skolem refine it into Zermelo–Fraenkel set theory (ZF); adding the Axiom of Choice gives ZFC, the modern standard.

- 1931 — Kurt Gödel's incompleteness theorems show no axiom system (including ZFC) can prove its own consistency.

- 1963 — Paul Cohen invents forcing and proves the Continuum Hypothesis is independent of ZFC — it can be neither proved nor disproved.

open-problem

The Continuum Hypothesis (CH) asks whether any infinite set of real numbers must be either countable (size $|\mathbb{N}|$ ) or as large as all reals (size $|\mathbb{R}|$ ) — with nothing in between. Gödel (1940) showed CH cannot be disproved from ZFC; Cohen (1963) showed it cannot be proved either. CH is therefore independent of the standard axioms: it is genuinely undecidable within them. This raises a deep philosophical question — is CH "really" true or false, or is mathematical truth itself relative to a chosen axiom system? Mathematicians still debate whether new, well-motivated axioms (e.g., large-cardinal axioms) should be adopted to settle it.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also