# Is there an error in this proof the the “strong induction” theorem? Is this Escherian logic?

By set predicates, I mean the "tests for inclusion" used in defining sets. That may be more of a computer scientific than mathematical use of the the term predicate. I included predicate logic in the tags because I believe those versed in predicate logic may have skills applicable to the subject at hand.

The way I see the proof quoted below, it has the structure of the "Escherian Stairwell":

The following is from BBFSK Vol I, page 101.

$$a

From the principle of induction we can now derive the following modified principle of induction: If the number $$m$$ is contained in the number set $$M$$ whenever $$n\in M$$ for all numbers $$n then $$M=\mathbb{N}.$$ The induction hypothesis now reads: "$$n\in M_{1}$$ for all numbers $$n"; and there is no special initial case. For the proof we consider the set $$M^{*}$$ of numbers $$m$$ with $$n\in M$$ for all $$n Then the hypothesis of our new principle simply states that $$M^{*}\subseteq M.$$ Since $$n<1$$ is not valid for any number $$n,$$ we get $$1\in M^{*}.$$ By (1), any number $$n is $$ or $$=m.$$ If we now assume that $$m\in M^{*},$$ then $$n$$ lies in $$M$$ not only in the first case but also, since $$M^{*}\subseteq M,$$ in the second case as well. Thus we have derived $$m^{\prime}\in M^{*}$$ from $$m\in M^{*},$$ so that by the argument from $$m$$ to $$m^{\prime}$$ we have $$M^{*}=\mathbb{N}$$ and thus also $$M=\mathbb{N}.$$

I've gone through this proof several times, and understand the intent of the authors. But when I try to state it in terms of set predicates, it appears to lead to a contradiction. Here's my reasoning:

Without considering $$M^{*}\subseteq M,$$ we have

$$M^*=\{m\backepsilon M=\{n\backepsilon n

Let $$P\left[n,m\right]:=n be the predicate defining $$M\equiv\left\{n\backepsilon P\left[n,m\right]\right\}.$$ So $$x\in M\iff x

Let $$P^{*}\left[m\right]:=\forall_{p be the predicate defining $$M^{*}\equiv\left\{m\backepsilon P^{*}\left[m\right]\right\}.$$ From this it's obvious that $$M^{*}=\mathbb{N}.$$

But my interest is in constructing the logical equivalent to $$M^{*}\subseteq M.$$ Evidently that would be $$m\in M^{*}\iff P^{*}\left[m\right]\implies m\in M\iff m which is a contradiction.

If I have made an error, I do not believe it is as simple as using $$m$$ to represent two different variables in the same context.

Is there a flaw in the proof given in BBFSK? If not, then what is wrong with my argument?

This is my effort to "unpack" the original paragraph. My notation is eclectic and idiosyncratic. It is intended to be self-explanatory. The part I found the trickiest is the distinction between the first case and the second case. That is also the part of the proof where my objection applies. It seems as if the reasoning lies somewhere between the finite and the infinite. That is, we appear to be injecting one infinite set into another infinite set, in finite steps. The second case is where my $$m occurs.

Of course, there is the likelihood that I'm simply overlooking something obvious and far more mundane.

Formalization

Lets call the proposition we seek to prove $$A_{5}^{\prime}$$, to indicate that it is a modification of Peano's 5th axiom.

To prepare, we give the theorem of equation (1) a fancy name

$$\Theta\equiv a

The following (copied from my older notes) is my effort to put the original paragraph into formal expressions:

Theorem:

From the principle of induction

$$$$A_{5}:=\left(P\left[1\right]\land\left(P\left[n\right]\implies P\left[n+1\right]\right)\right)\implies\underset{n}{\forall}P\left[n\right], \tag{2}$$$$

we can now derive the following modified principle of induction: If the number $$m$$ is contained in the number set $$M$$ whenever $$n\in M$$ for all numbers $$n then $$M=\mathbb{N}.$$

$$$$A_{5}\implies A_{5}^{\prime}:=\left(\left(\underset{n

$$$$M=\left\{ m\backepsilon\left(n

The induction hypothesis now reads: "$$n\in M_{1}$$ for all numbers $$n";

$$$$M_{1}=\left\{ n\backepsilon n

and there is no special initial case.

Proof:

For the proof we consider the set $$M^{*}$$ of numbers $$m$$ with $$n\in M$$ for all $$n

$$$$M^{*}=\left\{ m\backepsilon\left(n

Then the hypothesis of our new principle simply states that $$M^{*}\subseteq M.$$

$$$$H\iff M^{*}\subseteq M.\tag{7}$$$$

Since $$n<1$$ is not valid for any number $$n,$$ we get $$1\in M^{*}.$$

$$$$\left(\neg\underset{n<1}{\exists}\right)\implies1\in M^{*}.\tag{8}$$$$

By (1), any number $$n is $$ or $$=m.$$

$$$$\Theta\implies\left(n

If we now assume that $$m\in M^{*},$$ then $$n$$ lies in $$M$$ not only in the first case,

$$$$\text{first case: } m\in M^{*}\implies n\in M.\tag{10}$$$$

but also, since $$M^{*}\subseteq M,$$ in the second case as well.

$$$$\text{second case: }m\in M^{*}\land M^{*}\subseteq M\implies n\in M.\tag{11}$$$$

Thus we have derived $$m^{\prime}\in M^{*}$$ from $$m\in M^{*},$$

$$$$m\in M^{*}\implies m^{\prime}\in M^{*},\tag{12}$$$$

so that by the argument from $$m$$ to $$m^{\prime}$$ we have $$M^{*}=\mathbb{N}$$ and thus also $$M=\mathbb{N}.$$

• $M^* = \{ m \mid \forall n (n < m \to n \in M) \}$. – Mauro ALLEGRANZA May 22 at 6:20
• I acknowledge that my notation is idiosyncratic. But, I believe it is also self-explanatory. As for "the hypothesis". I believe there are two distinct hypotheses mentioned in the paragraph. One is the induction hypothesis used in applying the modified principle. The other is the hypothesis used in proving the applicability of the modified principle. I will try to expand the original paragraph to explain my interpretation. I would love to have the original German language version available. – Steven Thomas Hatton May 22 at 9:29
• @MauroALLEGRANZA Do you see how I'm arriving at $m<m$? – Steven Thomas Hatton May 22 at 10:54
• @MauroALLEGRANZA I had accepted the proof provided by BBFSK until I tried to state it in terms of logical implication. This effort, as well as my notation and conclusions are all self-inflicted. I'm fairly confident, however, that anything stated in the language of sets is also expressible in the language of predicate logic. I claim no expertise in either. I'm just trying to reduce the problem to terms that even I can understand it. – Steven Thomas Hatton May 22 at 12:01
• Perhaps my mistake is in treating "the hypothesis of our new principle $M^{*}\subseteq M.$" as an induction hypothesis, rather than as a statement about the "completed" sets $M$ and $M^*$. – Steven Thomas Hatton May 22 at 13:34

Very very long comment [from Mendelson, page 165].

We want to prove - using "ordinary" induction axiom - the "modified" induction principle :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \to (∀m)B (m)$$.

In order to use "ordinary" induction, we have to define a suitable predicate. Let :

$$C (m) := (∀n)(n \le m \to B (n))$$.

(i) Base case :

1) $$(∀m)((∀n)(n < m \to B (n)) \to B (m))$$ --- assumption

2) $$(∀n)(n < 1 \to B (n)) \to B (1)$$ --- from 1) by Universal Instantiation

3) $$\lnot (n < 1)$$ --- from Axiom

4) $$(∀n)(n < 1 \to B (n))$$ --- from tautology $$\lnot P \to (P \to Q)$$ and 3) by Modus Ponens and Universal Generalization

5) $$B (1)$$ --- from 2) and 4) by MP

6) $$(∀n)(n ≤ 1 \to B (n))$$ --- from 5) and previously proved result : $$B (1) \land B (2) \land \ldots \land B (k) \leftrightarrow (∀x)(x \le k \to B (x))$$.

But 6) is $$C(1)$$, and thus what we have proved in 1)-6) is :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash C (1)$$.

(ii) Now for the Induction step :

1) $$(∀m)((∀n)(n < m \to B (n)) \to B (m))$$ --- assumption

2) $$C(m)$$, i.e. $$(∀n)(n ≤ m \to B (n))$$ --- assumption [a]

3) $$(∀n)(n < m′ \to B (n))$$ --- from 2) using the "key fact" (see OP's text) : $$n < m' \leftrightarrow n ≤ m$$ and several logical steps

4) $$(∀n)(n < m′ \to B (n)) \to B (m′)$$ --- from 1) by UI

5) $$B (m′)$$ --- from 3) and 4) by MP

6) $$n ≤ m′ \to n < m′ \lor n = m′$$ --- from definition of $$\le$$

7) $$n < m′ \to B (n)$$ --- from 3) by UI

8) $$n = m′ \to B (n)$$ --- from 5,) using axiom for equality

9) $$(∀n)(n ≤ m′ \to B (n))$$ i.e. $$C (m′)$$ --- from 6), 7) and 8) and UG

10) $$C(m) \to C(m')$$ --- from 2) and 9) by Deduction Th, discharging assumption [a]

11) $$(∀m)(C(m) \to C(m'))$$ --- from 10) by UG.

The steps 1)-11) amounts to :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash (∀m)(C (m) \to C (m′))$$.

Now we can apply the "ordinary" induction axiom to (i), (ii) to get :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash (∀m)C (m)$$.

But $$C(m)$$ is $$(∀n)(n \le m \to B (n))$$ and thus what we have proved is :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash (∀m)(∀n)(n \le m \to B (n))$$

Now we apply UI twice to the conclusion to get :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash (m ≤ m \to B (m))$$.

But $$\vdash m ≤ m$$. Thus, using MP and UG we get :

$$(∀m)((∀n)(n < m \to B (n)) \to B (m)) \vdash (∀m)B(m)$$.

Finally, we use DT to conclude with :

$$\vdash (∀m)((∀n)(n < m \to B (n)) \to B (m)) \to (∀m)B(m)$$.

New long comment, regarding your original post (to be deleted after having detected the error).

The original proof is expressed in "set terms" :

From the principle of induction we can now derive the following modified principle of induction : "if the number $$m$$ is contained in the number set $$M$$, whenever $$n \in M$$ for all numbers $$n < m$$, then $$M = \mathbb N$$."

The ensuing comment is related to the way the modified pirnciple must be used (and not to its proof) :

The induction hypothesis [of the modified principle] now reads: "$$n\in M$$ for all numbers $$n < m$$"; and there is no special initial case.

It means that - when available - the new principle will need no base case (i.e. $$1 \in M$$) and thus, in order to apply it, what we have to prove is the antecedent (i.e. that "$$n\in M$$ for every$$n < m$$"), and it will be enough to conclude with :

$$n \in M$$, for every $$n$$.

As said in the book :

the hypotheses of the "modified" principle is "$$m \in M$$, whenever $$n \in M$$ for all numbers $$n", i.e.

$$(\forall n) (n < m \to n \in M) \to m \in M$$ [and this is the "set form" corresponding to the "overall" assumption in the "predicate form" proof above (line 1) of both (i) and (ii))],

and we have to prove that : $$M = \mathbb N$$.

To do it, define the set $$M^* = \{ m \mid (\forall n < m)(n \in M) \}$$ [and this is the "set form" of formula $$C(m)$$ above], that amounts to saying that : $$m \in M^* \text { iff } (\forall n < m)(n \in M)$$.

And prove - using "ordinary" induction - that $$M^* = \mathbb N$$.

But what does it mean to prove - by "ordinary" induction - that $$M^* = \mathbb N$$ ? It means to show that $$1 \in M^*$$ and that $$M^*$$ is closed under the successor operation.

We have $$1 \in M^*$$ trivially, and we show (using the hypotheses above) that $$m \in M^* \to m' \in M^*$$.

Thus, by induction : $$m \in M^*$$, for every $$m$$, i.e. $$M^* = \mathbb N$$ [and this conclusion corresponds to $$\forall m C(m)$$ above].

Now the induction is completed.

The last step does not use induction anymore [see the last part of the proof above].

We have proved that $$M^* = \mathbb N$$ and we have $$M^* \subseteq M$$; thus we conclude with :

$$M = \mathbb N$$.

IMO, the mistake is in your definition of $$M^* = \{ m \mid M= \{ n \mid n and that of the corresponding predicate $$P[n,m] := n.

We have not $$x ∈ M ⟺ x, and thus the conclusion :

Evidently that would be $$m∈M^* ⟺ P^*[m] ⟹ m∈M ⟺ m, which is a contradiction,

does not follows.

We have : $$m \in M^* \text { iff } (\forall n < m)(n \in M)$$ and we have that $$m ∈ M$$, but this does not imply a contradiction, because we have not $$M = \{ n \mid n < m \}$$.

Obviously, if $$M = \{ n \mid n < m \}$$ we would have $$m \in M \text { iff } m < m$$, and this is contradictory.

• Thanks for the homework! ;) It will take me some time to work through this. My approach is to transcribe it all into my notation. Not to say that my notation is superior. It just reflects how I think. It also forces me to touch every piece of the demonstration, and reinterpret it. For example, the statement of the theorem in my notation is $\forall_{m}\left[\forall_{n<m}\left[B\left[n\right]\right]\implies B\left[m\right]\right]\implies B\left[\mathbb{N}\right].$ That's not the only way I might write it, but it is the least confusing to me. – Steven Thomas Hatton May 22 at 12:45
• I really appreciate the effort you have put into responding to my question, and I intend to give your input careful consideration. I am still curious to know if you understand how I arrived at $m<m$ in my original post? Apparently, for every induction step we are to assume $M=\left\{n\backepsilon n<m\right\},$ and then assert $m\in M$ for the same $m$ as used to define $M$. That seems wrong to me. But BBFSK is no ordinary set of books. Even though I am proposing that their proof is wrong, I really want my proposition to be refuted. – Steven Thomas Hatton May 22 at 13:02
• OK. $m<n\implies m\in M$ does not require $m\in M\implies m<n$. – Steven Thomas Hatton May 22 at 14:57