The Principle of Induction in ZFC

Recently, I came across an explanation of Principle of Induction using ZFC Set Theory and Inductive sets which I found to be pretty cool for its surprising simplicity and usage of the ZFC construction of natural numbers.

Setup

To begin, let’s denote the successor of a set with a slightly more convenient notation. \[x^+ := x \cup \set{x}.\]

Here are a few properties that immediately arise:

• \(a\in x^+\) implies either \(a\in x\) or \(a=x\).
• \(x\in x^+\).
• \(x\subseteq x^+\).

We define a natural number as a set that is a member of all inductive sets, and \(\omega\) as the set of all such natural numbers. To review, an inductive set is one that contains the empty set and also contains the successors of each of its members. That is, for an inductive set \(I\), \(\varnothing\in I\), and for any \(x\in I\), we have that \(x^+\in I\). The existence of an Inductive set is guaranteed by the Axiom of Infinity.^1, 2 Then we can denote the Natural Numbers in a familiar fashion.

\[\begin{aligned} 1 & = 0^+ = 0 \cup \set{0} = \set{0} \\ 2 & = 1^+ = 1 \cup \set{1} = \set{0, 1} \\ 3 & = 2^+ = 2 \cup \set{2} = \set{0, 1, 2} \\ & \;\; \vdots \\ n+1 & = n^+ = n \cup \set{n} = \set{0, 1, 2, \ldots, n} \end{aligned}\]

Note that \[0 \in 1 \in 2 \in 3 \in \cdots\] and \[0 \subseteq 1 \subseteq 2 \subseteq 3 \subseteq \cdots\]

ω is the Smallest Inductive Set.

First, we will show that \(\omega\) is an inductive set. Since each inductive set contains the empty set \(\varnothing\), \(\varnothing\in\omega\). Next, if \(a\in\omega\), then \(a\) is in every inductive set. It follows that \(a^+\) is also in every inductive set, and hence \(a^+\in\omega\). Therefore, \(\omega\) is an inductive set.

Furthermore, let \(I\) be any inductive set. If \(x\in\omega\), then \(x\in I\). Thus, \(\omega\subseteq I\). This demonstrates that \(\omega\) is the smallest inductive set, and if \(I\) is an inductive set such that \(I\subseteq\omega\), then \(I=\omega\).

Note that \(\omega = \set{0, 1, 2, 3, \ldots}\) because the right-hand-side is an inductive subset of \(\omega\). This is the fact that demonstrates the Principle of Induction.

The Principle of Induction

The Principles of Induction states that if for some formula \(P\),

1. \(P(0)\)
2. \((\forall n\in\omega)(P(n)\implies P(n^+))\)

then, \((\forall n \in \omega)P(n)\).

Let \(I = \set{n\in\omega: P(n)}\).

It is clear that \(P(n)\) holds for all \(n \in I\) and \(I\) is a subset of \(\omega\). By the first part of the hypothesis, we know that \(0\in I\). And by the second part of the hypothesis, we have that for every \(n \in I\), \(n^+\) is also in \(I\). Therefore \(I\) is an inductive set. We have shown that \(\omega\) is the smallest inductive set above, which implies that \(\omega\) must be a subset of the inductive set \(I\). But since the set \(I\) was created by restricting \(\omega\), \(I\) must be a subset of \(\omega\) too. Therefore, \(I = \omega\), which implies that \(P(n)\) holds for all natural numbers \(n \in \omega\). In other words

\[(\forall n \in \omega) P(n),\]

and our proof is complete.

1. See this page for the Axiom. ↩

2. It is important to specify that at least one inductive set exists because the description is effectively taking an intersection. If no inductive sets were to exist, then each and every set would vacuously satisfy the conditions of being a natural number, which effectively makes ω, the set of all natural numbers, no longer a bonafide set. ↩