Past exam of the logic and set theory course of the University of Oxford / 2007 / B / 5

The axiom of infinity asserts that an inductive set exists: some set $I$ contains $0=\varnothing$ and contains $x^{+}=x\cup \{x\}$ whenever it contains $x$. Inside one such $I$, axiom of separation definesThis intersection is itself inductive and is contained in every inductive set, by intersecting that set with $I$. It is therefore the set of natural numbers. If a property holds at $0$ and passes from $n$ to $n^{+}$, axiom of separation forms the subset of $\omega$ on which it holds. That subset is inductive, so must equal $\omega$. This proves mathematical induction, including properties with set parameters.

Recursion on $\omega$ defines the arithmetic operations byExistence and uniqueness follow from the recursion theorem on the natural numbers.

For associativity of addition fix $m,n$ and induct on $k$. At $k=0$ both sides equal $m+n$. If the equality holds at $k$, thenThusEvery step after the induction hypothesis is a defining successor equation, so commutativity has not been used prematurely.

Induct on $n$. The initial equation is $0+0=0$ by the zero clause. If $0+n=n$, the successor clause givesConsequentlyThis proves the left-identity property independently of the right-identity equation built into the recursive definition.

Fix $m$ and induct on $n$. At $n=0$,If $m^{+}+n=m+n^{+}$, thenThe last expression is the right-hand side required at the successor $n^{+}$. ThereforeIn particular both sides also equal $(m+n{)}^{+}$ by the recursion equation for the second argument.

Fix $m,n$ and induct on $k$. For $k=0$,For the induction step, use the multiplication recursion, the induction hypothesis, and addition associativity from (i):ThusThis establishes the indicated distributive law without assuming multiplication is commutative.

Fix $m$ and induct on $n$. The initial equality $m+0=0+m$ follows from the defining zero clause and (ii). Assuming $m+n=n+m$, the successor clause and (iii) giveThis provesThe extension to arbitrary ordinals is false. By the limit clause for ordinal addition,whereas $\omega +1$ is the successor ordinal of $\omega$ and is strictly greater than it. ThereforeFinite addition is commutative; ordinal addition records the order of concatenated well-orders and need not be commutative.