Set Theory

Elements

The fundamental element of set theory is the object — anything that can be collected. A set is a collection of distinct, unordered elements; each element appears only once.

$A = \{1, 2, 3\}, \quad B = \{x \mid x^2 < 10\}$

Hierarchy of Forms

• Element ($\in$): the primitive membership relation — $x \in A$ means $x$ belongs to $A$
• Set: the basic form — finite, infinite, countable, uncountable, ordered, unordered
• Subset: $A \subseteq B$ if every element of $A$ is in $B$
• Power set: $\mathcal{P}(A)$ — the set of all subsets of $A$; if $|A| = n$, then $|\mathcal{P}(A)| = 2^n$

Set Operations

ZFC Axiomatic System

Modern set theory is built on the Zermelo–Fraenkel axioms with Choice (ZFC) — a minimal set of axioms from which all of standard mathematics can be derived.

The key axioms state what sets exist:

• Extensionality — sets are determined entirely by their members
• Empty set — $\emptyset$ exists
• Power set — $\mathcal{P}(A)$ exists for any $A$
• Infinity — an infinite set exists (foundation of $\mathbb{N}$)
• Separation — $\{x \in A \mid P(x)\}$ exists for any predicate $P$

Cantor’s Theorem

From Separation alone, a fundamental asymmetry follows:

$|A| < |\mathcal{P}(A)| \quad \text{for every set } A$

No set can be placed in bijection with its own power set. Applying this to $\mathbb{N}$ proves that the real numbers are uncountable — a strictly larger infinity.

The Axiom of Choice

The most controversial axiom: for any collection of non-empty sets, there exists a function selecting one element from each. It is independent of the other ZFC axioms — neither provable nor disprovable without it.

Set Operations as Procedures

The algorithmic lens treats set theory as a collection of decision and construction procedures — operations with clear inputs, steps, and outputs.

Membership Testing

Given a set $A = \{x \mid P(x)\}$ and element $e$: evaluate $P(e)$. If true, $e \in A$; otherwise, $e \notin A$.

Power Set Construction

For a set $A$ with $n$ elements, the power set has $2^n$ members:

1. Begin with $\{\emptyset\}$.
2. For each element $a_i \in A$, extend every existing subset with $a_i$.
3. Collect all $2^n$ subsets.

Cardinality Comparison

Two sets have the same cardinality if there exists a bijection between them. For infinite sets this diverges from size intuition: $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|$ (all countable), but $|\mathbb{R}| > |\mathbb{N}|$ (uncountable).

Transfinite Induction

The generalization of mathematical induction to well-ordered sets and ordinals — the procedure for proving properties over the entire infinite hierarchy of sets.

Set Theory as a System

In the classical view, set theory is a two-level system:

• Elements (objects): the primitive units — anything can be an element
• Sets (forms): the structures that collect elements under a predicate

Modern set theory extends this: sets themselves become elements of other sets, giving the system a recursive, self-referential structure.

Stocks and Flows

• Stock: the universe of sets $V$ — built cumulatively by the von Neumann hierarchy $V_0 \subset V_1 \subset V_2 \subset \ldots$
• Flow: set operations (union, power set, replacement) generate new sets from existing ones
• Reinforcing loop: power set construction — each set generates a strictly larger set, driving the hierarchy upward without limit

Finite vs. Infinite

The system has no natural upper boundary: the cumulative hierarchy of sets forms the universe of mathematics.