1
$\begingroup$

Question:

In Munkres's Topology (2nd ed.), he gives a proof for the following:

Theorem 4.2 (Strong induction principle). Let $A$ be a set of positive integers. Suppose that for each positive integer $n$, the statement $S_n\subset A$ implies the statement $n\in A$. Then $A=\mathbb{Z}_+$.

This appears to be slightly different from the "traditional" (strong) induction principle which can be stated as: let $P_n$ be a sequence of statements. Suppose $P_1$ is true and (($P_m$ is true $\forall\, m < n$) implies $P_{n}$ is true) then $P_k$ is true $\forall\, k\in \mathbb{Z}_+$.

How can one reconcile the two?

Attempt:

I'm thinking of something along the lines of:

Let $A$ be a set of positive integers and $P_n$ be a sequence of propositions. Suppose that for each positive integer $n$, the statement $S_n\subset A$ implies the statement ($n\in A$ and $P_n$ is true). Then $A=\mathbb{Z}_+$ and $P_k$ is true $\forall\, k \in \mathbb{Z}_+$.

This can proved to be equivalent to the "traditional" form in the following way:

  1. Proceed with Munkres's proof and obtain $A=\mathbb{Z}_+$.
  2. $\because S_1=\varnothing\subset A$ is true, our supposition for $n=1$ is equivalent to assuming that $P_1$ is true.
  3. ??? (how do we show that the supposition "$S_n\subset A$ implies the statement ($n\in A$ and $P_n$ is true)" is equivalent to "($P_m$ is true $\forall\, m < n$) implies $P_{n}$ is true"?)
$\endgroup$
3
$\begingroup$

Actually I just noticed that this point is discussed in Chapter 1 $\S$ 7 after Lemma 7.2 (pg 45 in 2nd ed.)

To use the principle to prove a theorem "by induction", one begins the proof with the statement "Let $A$ be the set of all positive integers $n$ for which the theorem is true," and then one goes to prove that $A$ is inductive, so that $A$ must be all of $\mathbb{Z}_+$

Using this one can write:

Let $P_n$ be a sequence of propositions and $A$ be the set of all positive integers $n$ for which $P_n$ is true. Suppose that for each positive integer $n$, the statement $S_n\subset A$ implies the statement $n\in A$. Then $A=\mathbb{Z}_+$.

The equivalence with the "traditional" induction principle is easily demonstrated:

  1. For $n=1$, the assumption ($S_1 = \varnothing \subset A \Rightarrow 1 \in A$) is equivalent to ($P_1$ is true).
  2. For $n>1$, the assumption ($S_n \subset A \Rightarrow n \in A$) is equivalent to (($P_m$ is true $\forall\, m<n$) $\Rightarrow$ $P_n$ is true)
  3. The conclusion ($A=\mathbb{Z}_+$) is equivalent to ($P_n$ is true $\forall\, n\in \mathbb{Z}_+$).
$\endgroup$
  • $\begingroup$ Yes, this is the intended argument. $\endgroup$ – Brian M. Scott Aug 31 '16 at 22:10

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.