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"?

  • 1
    $\begingroup$ That's not how transfinite induction is supposed to go. $\endgroup$ – Git Gud Aug 15 '14 at 23:07
  • $\begingroup$ No, induction would only prove that $\omega\subseteq S$. You didn't state that $S\subseteq \omega$. $\endgroup$ – Thomas Andrews Aug 15 '14 at 23:08
  • $\begingroup$ And similarly for transfinite induction, you can only deduce $X\subseteq S$, since $S$ might contain more elements. $\endgroup$ – Thomas Andrews Aug 15 '14 at 23:09
  • $\begingroup$ Thanks Thomas, those were oversights on my part when I typed the question. $\endgroup$ – Elliott Aug 15 '14 at 23:14
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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. :-) $\endgroup$ – Asaf Karagila Aug 16 '14 at 6:01
  • $\begingroup$ @AsafKaragila True, thanks! $\endgroup$ – 6005 Aug 16 '14 at 7:31
  • $\begingroup$ 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. $\endgroup$ – Elliott Aug 17 '14 at 11:20

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.