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.

  • $\begingroup$ @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 $\endgroup$ – Dan Christensen May 18 '14 at 11:38
  • $\begingroup$ $X ∪ Y ⊆ Z ↔ X ⊆ Z ∧ Y ⊆ Z$ and $x ∈ X ↔ \{ x \} ⊆ X$. $\endgroup$ – Rui Baptista May 18 '14 at 12:57
  • $\begingroup$ Right ! thanks ... Thanks also to @user143882 $\endgroup$ – 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.

  • $\begingroup$ Velcome to the site! $\endgroup$ – kjetil b halvorsen May 20 '14 at 15:06
  • $\begingroup$ @Pierre B. Thanks for feedback. I hadn't picked up that $0 \in S$ automatically: amazing what a younger mind can see ! $\endgroup$ – Tom Collinge May 20 '14 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.