Foundations via ZFC Axioms

Overview

These lectures introduce the nine axioms of Zermelo-Fraenkel set theory with the axiom of choice (ZFC), which form the foundational language for all standard mathematics. The epsilon (∈) relation serves as the fundamental primitive, defined only through axioms rather than explicit definitions.

The Epsilon Relation and Fundamental Concepts

• Epsilon (ε) is a fundamental relation, defined as a predicate of two variables.
• No explicit definition exists for epsilon or what a set is in the strictest sense.
• Nine axioms teach how to use epsilon and what constitutes a set through their interplay.
• The approach is necessary to build mathematics from scratch without prior notions or terms.

The Nine Axioms Mnemonic: EEPERPICF

Basic Definitions Using Epsilon

• Not element: x ∉ y defined as ¬(x ∈ y)
• Subset: x ⊆ y means ∀a(a ∈ x → a ∈ y)
• Equality: x = y defined as (x ⊆ y) ∧ (y ⊆ x)
• Equality is ultimately defined in terms of epsilon relation, not taken as primitive.

Axiom 1: Epsilon Relation

• x ∈ y is a proposition (true or false) if and only if both x and y are sets.
• Clarifies that epsilon acts only on sets, not arbitrary objects.
• Historically considered trivial but actually essential for consistency.

Russell's Paradox

• Assume U contains all sets that do not contain themselves: Z ∈ U ↔ Z ∉ Z.
• If U ∈ U is true, then by definition U ∉ U (contradiction).
• If U ∈ U is false, then U ∉ U, so by definition U ∈ U (contradiction).
• Conclusion: U is not a set, demonstrating naive set theory is inconsistent.
• Axiom of foundation ultimately excludes such constructions.

Axiom 2: Empty Set

• There exists a set containing no elements: ∃x∀y(y ∉ x).
• Theorem: There is only one empty set, denoted ∅.
• Proof uses definition of subset and equality to show two empty sets must be identical.
• Standard proof uses implication: false statement implies anything (ex falso quodlibet).

Axiom 3: Pair Set

• For any sets x and y, there exists set M containing precisely x and y.
• Formal: ∀x∀y∃M∀u(u ∈ M ↔ (u = x ∨ u = y))
• Notation: {x, y} denotes pair set.
• Order doesn't matter: {x, y} = {y, x} provable from element relation.
• Also guarantees one-element sets: {x} = {x, x}.

Axiom 4: Union Set

• Given set X, there exists set U containing precisely the elements of elements of X.
• Notation: U = ⋃X
• Example: If X = {{a}, {b, c}}, then ⋃X is set containing a, b, c.
• Combined with pair set axiom, defines finite n-element sets recursively.
• Key restriction: can only unify as many sets as fit into a set.

Axiom 5: Replacement

• Let R be functional relation and M be a set; then image of M under R is a set.
• Functional relation: For every x, exists precisely one y such that R(x,y).
• Image: Consists of all y for which there exists x ∈ M with R(x,y).
• Strongest axiom, though full power rarely needed in practice.

Principle of Restricted Comprehension

• Follows from replacement axiom but weaker than replacement itself.
• Let P be one-variable predicate and M be set.
• Then {y ∈ M | P(y)} is a set (selecting elements satisfying condition).
• Not universal comprehension: Cannot collect all y satisfying P without restricting to existing set.
• Universal comprehension leads to Russell's paradox; restricted version is consistent.
• Allows defining complements and intersections of sets.

Axiom 6: Power Set

• For any set M, there exists set P(M) whose elements are precisely subsets of M.
• Cannot be derived from restricted comprehension (no larger set to restrict from).
• Requires dedicated axiom for existence.
• Example: If M = {a, b}, then P(M) = {∅, {a}, {b}, {a,b}}.

Axiom 7: Infinity

• There exists set containing empty set and, with each element y, also contains {y}.
• Smallest such set: {∅, {∅}, {{∅}}, {{{∅}}}, ...}
• These correspond to natural numbers 0, 1, 2, 3, ... under standard construction.
• Corollary: Non-negative integers form a set in axiomatic set theory.
• Real numbers defined as power set of integers.
• Entire universe of sets built from empty set via power sets and constructions.

Axiom 8: Choice

• Let X be set whose elements are non-empty and mutually disjoint sets.
• Then exists set Y containing exactly one element from each element of X.
• Y called "choice set" (no algorithm specified for selection).
• Independence: Axiom of choice is independent of other eight axioms.
• Standard mathematics uses axiom of choice (ZFC includes it).
• Needed to prove every vector space has basis.
• Required for existence of complete system of representatives of equivalence relations.

Axiom 9: Foundation

• Every non-empty set X contains element Y with no elements in common with X.
• Excludes self-referential constructions: no set x satisfies x ∈ x.
• Ensures all sets ultimately built from empty set.
• Introduced last historically despite name "foundation."
• Completes exclusion of Russell-type paradoxes.

Zermelo-Fraenkel Set Theory (ZFC)

• The nine axioms together constitute Zermelo-Fraenkel set theory with choice (ZFC).
• Without axiom C, called ZF set theory.
• All standard mathematics can be constructed from ZFC axioms in principle.
• Every mathematical object ultimately built from empty set using construction axioms.