# Is this a Correct Proof of the Principle of Complete Induction for Natural Numbers in ZF?

I have reviewed a number of previous posts on this subject without finding an answer to my own point of interest, which is a proof that is closely related to ZF axioms and doesn't pre-suppose results on arithmetic, ordering or cardinality (there are a number of proofs using induction on the size of sets [cardinality] or which look at numbers < n (order) or which simply list numbers 1,2, ..n and then say something about n+1 [order and arithmetic]). Here is my attempt at a proof which excludes arithmetic, ordering or cardinality : I would appreciate feedback on its correctness.

Summary of natural numbers and the principle of mathematical induction (PMI) in ZF: define the successor of a set X as $X^+ = X \cup$ {$X$}. Define Z as a successor set if $\emptyset \in Z$, and $z \in Z \Rightarrow z^+ \in Z$. The axiom of infinity guarantees the existence of a successor set. Define $\omega$ as the minimal successor set and prove $\omega \subset$ every successor set. Define the natural numbers as the elements of $\omega$ and label them $0 = \emptyset; 1 = 0^+ = \,${$0$}$; 2 = 1^+ = \,${$0, 1$}$, ...$. PMI then says that if $S \subset \omega$ and if $\emptyset \in S$, and $s \in S \Rightarrow s^+ \in S$, then $S = \omega$. The proof is trivial: S is by definition a successor set and so $\omega \subset S$ and $S \subset \omega$ therefore $S = \omega$.

Statement of the principle of complete induction for natural numbers (PCI) in ZF. Without involving order, PCI can be stated that if $\emptyset \ne S \subset \omega$ and if for $s \in \omega$, s $\subset S \Rightarrow s \in S$, then $S = \omega$. To see how this relates to a more common expression of PCI, note that the order relation on the naturals is defined by $x < s$ if $x \in s$. The elements of the set s are thus all the numbers less than s: so with the additional interpretation of order, PCI says that for a non-empty set S, if $x \in S \;\forall \; x < s \Rightarrow s \in S$ then $S = \omega$.

Proof: PMI $\Rightarrow$ PCI. Let S be a non-empty subset of $\omega$ where for $s \in \omega$, s $\subset S \Rightarrow s \in S$.

Note that $0 \in S$ because $0 (\in \omega) = \emptyset$ and $\emptyset \subset any set$ so $\emptyset (=0) \subset S \Rightarrow 0 \in S$

Let $T \subset S =${$t \in S:t \subset S$}

$0 \in T$ because $0 \in S$ and $0 \subset S$,

If $n (\in \omega)\in T$ then by the property of T $(n \in S$ and $n$ $\subset S )$ which $\Rightarrow n \cup$ {n} $\subset S$. (see ** below)

But $n \cup$ {n} $= n^+$, so $n^+$ $\subset S$ and by the property of S, $n^+$ $\subset S \Rightarrow$ $n^+ \in S$

So by the specification of T, with $n^+ \in S$ and $n^+$ $\subset S$ then $n^+ \in T$.

So, $0 \in T$ and if $n \in T$ then $n^+ \in T$, so by PMI $T = \omega$, and $\omega = T \subset S \ \subset \omega$ so $S = \omega$ ∎

** What $n \cup$ {n} is, and why $(n \in S$ and $n$ $\subset S )$ $\Rightarrow n \cup$ {n} is a subset of S. The nesting of sets can be confusing. $n \cup$ {n} is a set whose elements are the elements of n, and the set n itself. If $m \in n \cup$ {n}, then either (a) m is an element of n i.e. $m \in n$, or (b) $m = n$ . If (a) since $n$ $\subset S$ then $m \in n \subset S \Rightarrow m \in S$ or if (b), since $n \in S$ then $m = n \in S$. So in either case $m \in n \cup$ {n} $\Rightarrow m \in S$, which is exactly the definition that $n \cup$ {n} is a subset of S.

• @TomCollinge I haven't got time to go through your proof, but I have struggled with this notion using not ZFC, but my own set theory. If we assume the existence of a Dedekind infinite set (roughly equivalent to AoI in ZFC), you can prove the existence of a subset of that set that satisfies all of Peano's axioms including PMI. See my own formal proof at dcproof.com/ProofByInduction.html – Dan Christensen May 18 '14 at 11:38
• $X ∪ Y ⊆ Z ↔ X ⊆ Z ∧ Y ⊆ Z$ and $x ∈ X ↔ \{ x \} ⊆ X$. – Rui Baptista May 18 '14 at 12:57
• Right ! thanks ... Thanks also to @user143882 – Mauro ALLEGRANZA May 18 '14 at 13:40

Your proof is essentially correct (although, if you don't mind my saying, hard to read). Just one thing: it is not necessary to assume $S \ne \emptyset$ since, as you show, $0 \in S$ follows from $0 \subset S$.
It is also possible to prove PCI $\implies$ PMI in a similar way, relying on the fact that every nonzero natural number is the successor of a natural number.
• @Pierre B. Thanks for feedback. I hadn't picked up that $0 \in S$ automatically: amazing what a younger mind can see ! – Tom Collinge May 20 '14 at 16:04