Infinity: some set contains ∅ and every successor of its members¶

Level: 201 · for anyone who has read "there exists an infinite set" as an axiom and wondered how a formula can say "infinite"

One line: The axiom of infinity does not say "infinite"; it asks for a set that contains ∅ and, with each member x, contains x ∪ {x}, and no finite set can keep that promise, so the axiom is the one place where the universe is told to have an endless set; the smallest such set is ω, the natural numbers, and everything infinite in mathematics is built from it.

The axiom, read aloud¶

Cunningham's form, which is the one most books use:

∃I (∅ ∈ I ∧ ∀x (x ∈ I → x ∪ {x} ∈ I))

There is a set I such that ∅ is a member of I and, whenever x is a member of I, so is x ∪ {x}. A set with these two properties is called inductive. Cori and Lascar state it after the ordinals instead, as "there exists an infinite ordinal", equivalently "there exists a limit ordinal", with the formula ∃v₀ (On[v₀] ∧ ¬v₀ ≃ ∅ ∧ ∀v₁ ¬v₀ ≃ v₁ ∪ {v₁}); section 5 of the program reads it, and the two forms agree once ordinals are defined. Jech's one line is simply "there exists an infinite set".

The operation x ∪ {x} is the successor: the set x with x itself added as a new member. Starting from ∅ it produces ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, …, the von Neumann numbers 0, 1, 2, 3, each the set of the ones before it. Section 1 prints the first five.

What it is for¶

The natural numbers as a set. An inductive set must contain 0, hence 1, hence 2, and so on with no end. Different inductive sets may contain other things too, so ω is defined as what they all share: the intersection of every inductive set, which exists by comprehension inside any one of them. Section 3 shows the idea with two "inductive" sets that hold junk: the intersection keeps only the numbers. ω is the smallest inductive set, and it is the ℕ of Cori and Lascar's section 7.2.4, where 0, successor, + and × are defined on it and every theorem of arithmetic follows. The whole of number theory stands on this one axiom and the construction after it.

Everything infinite. ℤ, ℚ and ℝ are built from ω by pairs, products and power sets; so are sequences, series, limits and every function of analysis. Without this axiom the universe V_ω of hereditarily finite sets satisfies every other axiom of ZFC, and in it there is no ℕ, let alone ℝ.

Induction. A proof by induction is a proof that a set of numbers is inductive, hence contains ω, hence contains every number. The axiom is what makes "and so on" a theorem; the induction lesson shows the method at work and why it is valid.

What goes wrong without it¶

Every finite universe fails it, which section 2 shows in V₄: no set of the sixteen is inductive, and the set that holds the longest run of the chain, 0, 1, 2, needs 3, which has rank 3 and is outside. The reason is general: an inductive set contains infinitely many distinct members, since by extensionality ∅ ≠ {∅} ≠ {∅, {∅}} ≠ …, and a finite universe has no infinite set. Nor does V_ω, the union of all the finite stages, which has every finite set and no infinite one. So no other axiom implies this one, and Dedekind's attempt to prove the existence of an infinite set (1888) was abandoned by everyone after him: it has to be assumed.

Section 4 is Dedekind's own definition of infinite applied to ω: the successor map is one-to-one and never hits 0, so ω is matched with a proper part of itself. The reading guide's program checks that no finite set can do that.

What the program prints¶

Verified output of infinity.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE SUCCESSOR x ∪ {x}, AND THE AXIOM
   ∃v0 (∅ ∈ v0 ∧ ∀v1 (v1 ∈ v0 ⇒ v1 ∪ {v1} ∈ v0))   (Cunningham's form)
   there is a set I that contains ∅ and, with each member x, contains
   x ∪ {x}. Such a set is called inductive.
   0 = ∅
   1 = {∅}
   2 = {∅, {∅}}
   3 = {∅, {∅}, {∅, {∅}}}
   4 = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}
   Each is the set of the ones before it: the von Neumann numbers.

2. NO SET IN V_4 IS INDUCTIVE, AND NO FINITE SET CAN BE
   inductive sets among the 16 sets of V_4: 0
   the set holding the longest run of the chain is {∅, {∅}, {∅, {∅}}}: it has [0, 1, 2],
   so it needs 3 = {∅, {∅}, {∅, {∅}}}, which has rank 3, outside V_4.
   An inductive set must hold 0, then 1, then 2, ... with no end, so it
   is infinite; a finite universe has no infinite set; the axiom fails in
   every V_n, and in V_ω, the union of them all, which satisfies every
   other axiom of ZFC. That is why infinity is an axiom and not a theorem.

3. ω IS WHAT ALL INDUCTIVE SETS SHARE
   Two sets that hold 0..4 plus some junk (standing in for inductive sets):
   I1 = {0, 1, 2, 3, 4, apple, pear},  I2 = {0, 1, 2, 3, 4, pear, plum}
   I1 ∩ I2 keeps the numbers [0, 1, 2, 3, 4] and the junk ['pear']
   The intersection of ALL inductive sets keeps only what every one
   of them must hold: 0, 1, 2, ... and nothing else. That set is ω,
   the smallest inductive set, and it exists by comprehension inside
   any one inductive set the axiom provides.

4. ω IS INFINITE IN DEDEKIND'S SENSE
   n ↦ n ∪ {n} is one-to-one on ω and never hits 0:
   0->1  1->2  2->3  3->4  4->5  5->6  ...
   so ω matches a proper part of itself, which no finite set does.

5. CORI AND LASCAR'S FORM: A LIMIT ORDINAL EXISTS
   ∃v0 (On[v0] ∧ ¬v0 ≃ ∅ ∧ ∀v1 ¬v0 ≃ v1 ∪ {v1})
   there is an ordinal that is not ∅ and not the successor of anything.
   ω is that ordinal: every member n has a successor n + 1 in ω, and ω
   itself is n + 1 for no n. The two forms are equivalent once ordinals
   are defined, which the ordinals page does.

Po polsku, w skrócie¶

Aksjomat nieskończoności nie zawiera słowa „nieskończony". Mówi: istnieje zbiór I, który zawiera ∅ i wraz z każdym elementem x zawiera jego następnik x ∪ {x}; taki zbiór nazywa się induktywny. Od ∅ następnik daje {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, czyli liczby von Neumanna 0, 1, 2, 3, z których każda jest zbiorem poprzednich. Zbiór induktywny musi je zawierać wszystkie, więc jest nieskończony; żadne skończone uniwersum go nie ma (program sprawdza szesnaście zbiorów V₄) i nie ma go też V_ω, suma wszystkich etapów skończonych, która spełnia wszystkie pozostałe aksjomaty ZFC. Dlatego to aksjomat, a nie twierdzenie. Najmniejszy zbiór induktywny, przekrój wszystkich, to ω, czyli liczby naturalne; na nim Cori i Lascar definiują 0, następnik, dodawanie i mnożenie, i stąd bierze się cała arytmetyka. Dowód przez indukcję to dowód, że pewien zbiór liczb jest induktywny.

Auf Deutsch: Stichwörter¶

Unendlichkeit: eine Menge enthält ∅ und mit jedem Element dessen Nachfolger; ω ist die kleinste solche.

Stichwörter: Unendlichkeitsaxiom, Nachfolger x ∪ {x}, induktive Menge, ω, natürliche Zahlen nach von Neumann.

Run it yourself¶

From the root of your clone of this repository:

python3 13_Axioms_of_Set_Theory/infinity/examples/infinity.py