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$

1 Answer 1

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$
1
  • 1
    $\begingroup$ Yes, this is the intended argument. $\endgroup$ Aug 31, 2016 at 22:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .