The axiom of infinity

1. The natural numbers and induction

The axiom of foundation, combined with extensionality, pair set and sum set, tells us there is a definable operation of sets, $s (x) = x \cup \{x\}$ , called the successor operation which is 1-1 and does not contain $0$ (i.e. $\emptyset$ ) in its range.

Definition.

A set $x$ is inductive if $0 \in x$ and $\forall y \in x s (y) \in x$ .

An inductive set is therefore infinite.

Axiom of infinity: there is an inductive set, $\exists x (0 \in x \land \forall y \in x s (y) \in x)$ .

The axiom says there is one such inductive set, but in fact we can find a very special one, the least such.

Proposition.

If $x, y$ are inductive then so is $x \cap y = \{u \in x: u \in y\}$ .

Proof.

Easy exercise.

Definition.

If $x$ is a non-empty set, $⋂ x$ denotes $\{u: \forall y \in x (u \in y)\}$ . This is easily seen to be a set by separation as for any $z \in x$ we have $⋂ x = \{u \in z: \forall y \in x (u \in y)\}$ .

Definition.

Let $x$ be inductive. The set $ω$ is the set $⋂ \{u \subseteq x: u is inductive\}$ . This is a set by power set and separation, and is independent of the choice of $x$ by the previous proposition. We also see that $ω$ is definable by a formula of $L_{\in}$ , $u = ω$ holds if and only if $\forall x (x is inductive \to u \subseteq x)$ .

Proposition.

$ω$ is inductive.

Proof.

Easy exercise.

The simplicity of the results her bely their power. What we have done is to define a set $ω = \{0 s (0) s (1) \dots\}$ and prove it is the least inductive set. (Be careful, as the $\dots$ is not precise and sets cannot be defined in this way except through special means such as those above.) What this is is in fact an induction principle, and $ω$ is a copy of the natural numbers. To ephasise this we shall write $1$ for $s (0)$ , $2$ for $s (1)$ , $3$ for $s (2)$ , and so on.

Principle of induction on $ω$ : If $ϕ (x)$ is a first order $L_{\in}$ formula, possibly with parameters, and suppose $ϕ (0)$ holds and also $\forall x (ϕ (x) \to ϕ (s (x)))$ . Then $\forall x \in ω ϕ (x)$ .

Proof.

The set $\{x \in ω: ϕ (x)\}$ exists by separation and is inductive by hypothesis. Hence it equals $ω$ .

2. Examples of induction on the natural numbers

Proposition.

Every nonempty set $x \in ω$ contains $0$ .

Proof.

Induction on $x$ .

Definition.

A set $t$ is transitive if for all sets $x, y$ we have $x \in y \in t$ implies $x \in t$ .

Proposition.

Every set $x \in ω$ is transitive.

Proof.

Induction on $x$ .

3. Recusion on the natural numbers

Going hand-in-hand with induction is recursion, also sometimes called inductive definitions. We need to explain and justify these.

Set theory has many notions of function. One is function as a definable first order formula. A formula $ϕ (\overline{x}, y)$ behaves like a function if $\forall \overline{x} \exists y (ϕ (\overline{x}, y) \land \forall z (ϕ (\overline{x}, z) \to y = z))$ . (This is usually abbreviated to $\forall \overline{x} \exists! y ϕ (\overline{x}, y)$ .) Sometimes this is true when restricted to $\overline{x}$ from a particular set or satisfying a partucular formula. Functions defined by formulas are called class functions.

The other kind of function is a function as a set.

Definition.

$⟨ x, y ⟩$ is the set $\{\{x\}, \{x, y\}\}$ .

This exists by the pair set axiom.

Proposition.

If $⟨ x, y ⟩ = ⟨ x', y' ⟩$ then $x = x'$ and $y = y'$ .

Proof.

Easy case-by-case argument.

Definition.

A set function is a set $f$ such that every element of $f$ is $⟨ x, y ⟩$ for some sets $x, y$ and $\forall x, y, z (⟨ x, y ⟩ \in f \land ⟨ x, z ⟩ \in f \to x = z)$ . For such an $f$ we write $dom (f)$ for $\{u: \exists v ⟨ u, v ⟩ \in f\}$ and $f (u)$ for the unique $v$ such that $⟨ u, v ⟩ \in f$ when $u \in dom (f)$ .

Theorem.

Suppose $ϕ (x, \overline{a})$ and $ψ (x, y, z, \overline{a})$ are first order formulas such that $\exists! x ϕ (x, \overline{a})$ and $\forall x \forall y \exists! z ψ (x, y, z, \overline{a})$ . Then there is a formula $θ (x, y, \overline{a})$ such that $\forall x \in ω \exists! y θ (x, y, \overline{a})$ and

$θ (0, y, \overline{a}) \leftrightarrow ϕ (y, \overline{a})$
$θ (x, y, \overline{a}) \land ψ (x, y, z, \overline{a}) \to θ (s (x), z, \overline{a})$

This shows that we can define a function $f (x, \overline{a})$ by $f (0, \overline{a}) = g (\overline{a})$ and $f (x + 1, \overline{a}) = h (x, f (x, \overline{a}), \overline{a})$ . In the statement of this theorem we have used class functions, but set functions take part in the proof.

Proof.

We say a set-function $f$ is an attempt if $dom (f)$ is $x \cup \{x\}$ for some $x \in ω$ such that

$ϕ (y, \overline{a}) \to f (0) = y$
$\forall u \in dom (f) \forall y \forall z (u \neq x \land f (u) = y \land ψ (u, y, z, \overline{a}) \to f (s (x)) = z)$

Our formula $θ (x, y, \overline{a})$ is the formula stating there is an attempt $f$ with $x \in dom (f)$ and $y = f (x)$ .

The rest is an exercise. You need to prove by induction on $ω$ that for all $x \in ω$ attempts exist with $x \in dom (f)$ and that any two attempts $f, g$ agree on the values they give for $f (x), g (x)$ .