# Equivalence between “mathematical induction” and “transfinite induction” for natural numbers?

The "principle of mathematical induction" says that for a subset $S$ of $\omega$ (where $\omega$ is the set of all natural numbers), if $0 \in S$ and $n \in S \implies n^+ \in S$, then $S = \omega$.

The "principle of transfinite induction" says that if $X$ is a well-ordered set, $S \subset X$, and $s(x) \subset S \implies x \in S$ (where $s(x)$ is the set of all predecessors of $x$ in $X$), then $S = X$.

Page 67 of Naive Set Theory (Halmos) says that "[the principle of transfinite induction] when applied to $\omega$ is easily proved to be equivalent to the principle of mathematical induction".

However, I had trouble proving this (possibly because I had trouble formulating this "equivalence" precisely).

How can I formulate and prove the statement that "the principle of transfinite induction, when applied to the natural numbers, is equivalent to the principle of mathematical induction"?

• That's not how transfinite induction is supposed to go. – Git Gud Aug 15 '14 at 23:07
• No, induction would only prove that $\omega\subseteq S$. You didn't state that $S\subseteq \omega$. – Thomas Andrews Aug 15 '14 at 23:08
• And similarly for transfinite induction, you can only deduce $X\subseteq S$, since $S$ might contain more elements. – Thomas Andrews Aug 15 '14 at 23:09
• Thanks Thomas, those were oversights on my part when I typed the question. – Elliott Aug 15 '14 at 23:14
• Apply mathematical induction to the statement $P(k):s(k)\subset S$ to get the transfinite induction applied to the natural numbers (I thought it was called strong induction). By the way, why are you working on such topics? I thought unless you are a working mathematician, these questions don't concern you. – Troy Woo Aug 15 '14 at 23:20

First, state the principle of transfinite induction in the case that $X = \mathbb{N}$.

If $\mathbb{N}$ is a well-ordered set, $S \subset \mathbb{N}$, and $s(x) \subset S \implies x \in S$ (where $s(x)$ is the set of natural numbers less than $x$), then $S = \mathbb{N}$.

To show this is equivalent to standard induction, you need to show the conditions are the same. I.e., you need to show that the following are equivalent:

1. For all $x \in \mathbb{N}$, if $x \in S$, then $x^+ \in S$.

2. For all $x \in \mathbb{N}$, if $s(x) \subset S$, then $x \in S$.

$1 \implies 2$ is straightforward. For $2 \implies 1$, prove the contrapositive, and use the fact that $\mathbb{N}$ is well-ordered to find a minimum counterexample.

I am a little skeptical of this, however, because to prove two forms of induction are the same you would want to be working in a world where neither of them need be true. That is, you can't use any form of induction in your proof. I do not know how one proves the natural numbers are well-ordered but I would certainly think it uses induction. And I wonder if one can even construct the natural numbers without some sort of induction. I am no expert in set theory, so I don't know how to resolve this issue, but there is certainly something fishy going on.

• I think there's a typo in your first line. It is true that $\Bbb N$ and $\Bbb Z$ are the same letter, modulo a unitary rotation matrix, but they denote different sets. :-) – Asaf Karagila Aug 16 '14 at 6:01
• @AsafKaragila True, thanks! – 6005 Aug 16 '14 at 7:31
• There was definitely induction involved in the proof that $\mathbb{N}$ is well-ordered--I'm not sure how to resolve this issue either. However, I'm okay with leaving the issue alone, and I'm happy with your answer--my main goal here was to get help with formulating the equivalence sensibly. – Elliott Aug 17 '14 at 11:20