Theorems that can't be proved by induction

1. Dec 29, 2015

Fredrik

Staff Emeritus
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.

Last edited: Dec 29, 2015
2. Dec 29, 2015

Krylov

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

3. Dec 29, 2015

Fredrik

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

4. Dec 29, 2015

Krylov

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.)

5. Dec 29, 2015

Fredrik

Staff Emeritus
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.

6. Dec 29, 2015

Svein

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

7. Dec 29, 2015

Fredrik

Staff Emeritus
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.

8. Jan 1, 2016

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.

Last edited: Jan 1, 2016
9. Jan 1, 2016

Fredrik

Staff Emeritus
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.