Theorems that can't be proved by induction

[Fredrik]

I know that I've seen an example of a statement of the form $\forall n~P(n)$ (where the scope of the "for all" is the set of positive integers) that can be proved, but can't be proved by induction. I thought I had seen it in one of Roger Penrose's books, but I have looked for it and wasn't able to find it. Maybe I saw it on some web page. I'm pretty sure that Penrose was involved somehow. The example defines a sequence for each positive integer. Each of the sequences starts out growing absurdly fast, and at an increasing rate, and it's clear that each sequence will continue to grow for a long time. But, if I remember correctly, the claim that you can't prove by induction, is that in each sequence, all but a finite number of terms are zero.

Does this sound familiar to anyone? I would like to look at that example again. If you know any other fun examples of when induction fails, I'd be interested in them as well.

 

[S.G. Janssens]

The example defines a sequence for each positive real number. Each of the sequences starts out growing absurdly fast, and at an increasing rate, and it's clear that each sequence will continue to grow for a long time. But, if I remember correctly, the claim that you can't prove by induction, is that in each sequence, all but a finite number of terms are zero.

Interesting result. I'm afraid I don't know the example, but I have some questions. What is the role of the positive real number? Do you mean that for every real number $a > 0$ he defines a sequence $(x_n)_{n \in \mathbb{N}}$ such that $x_1 = a$, the sequence has the described growth behavior, but eventually it becomes identically zero?

In that case, does the failure of induction have to do with the fact that $(0,\infty) \times \mathbb{N}$ is uncountable?

EDIT: Does it maybe also have to do with the fact that the natural number $N(a)$ such that $x_n = 0$ for all $n \ge N(a)$ itself grows beyond any bounds as a function of $a$?

 

[Fredrik]

Sorry, I meant positive integer. I will edit my post. Thanks for spotting the mistake. The example involves a sequence of sequences.

 

[S.G. Janssens]

Sorry, I meant positive integer. I will edit my post. Thanks for spotting the mistake. The example involves a sequence of sequences.

Ah ok, clear now.

EDIT: Incidentally, I would be curious to know how one proves that one cannot prove a certain proposition with induction. (Sorry for editing my post again, I think slowly.)

 

[Fredrik]

EDIT: Incidentally, I would be curious to know how one proves that one cannot prove a certain proposition with induction. (Sorry for editing my post again, I think slowly.)

I think that this wasn't explained in that text. I'd be interested in that too. Maybe we can figure it out when we see the example.

 

[Svein]

Each of the sequences starts out growing absurdly fast, and at an increasing rate, and it's clear that each sequence will continue to grow for a long time.

Might it have been the Ackermann function (https://en.wikipedia.org/wiki/Ackermann_function)?

 

[Fredrik]

Might it have been the Ackermann function (https://en.wikipedia.org/wiki/Ackermann_function)?

Yes, that might be it. Some of the expressions in the "table of values", like $2^{2^{2^2}}-3$, look very familiar. So maybe the $n$th sequence in the text I read was either $(A(n,m))_{m=1}^\infty$ or $(A(m,n))_{m=1}^\infty$. I will take a closer look later.

 

[Demystifier]

@Fredrik I think it was the Goodstein theorem.
https://en.wikipedia.org/wiki/Goodstein's_theorem
I am pretty convinced that Penrose indeed discussed the Goodstein theorem.

The theorem can't be proved with first order Peano axioms, including the first order induction. It can be proved with transfinite numbers, even though the theorem is a statement about finite numbers. It also can be proved with second order Peano axioms (with second order induction), but this is less known and usually ignored because most logicians don't like second order logic.

 

[Fredrik]

@Fredrik I think it was the Goodstein theorem.
https://en.wikipedia.org/wiki/Goodstein's_theorem
I am pretty convinced that Penrose indeed discussed the Goodstein theorem.

That's definitely it. The "hereditary base n notation", the replacement n→n+1 and and the "-1" part of the construction all look familiar. Thanks.