Is there any examples of statements P(n) such that "for all $n>1$, P(n)" is provable, but P(n)=>P(n+1) is not provable? (without using some mild deformation of "for all $n>1$, P(n)"=>"P(n)=>P(n+1)"?
Statements true for all integers but not provable by induction
-
8Well, if $P(n+1)$ is true, then $P(n) \Rightarrow P(n+1)$ is true regardless of whether $P(n)$ is. – 2012-06-07
-
5There are results such as [Goodstein's Theorem](http://en.wikipedia.org/wiki/Goodstein%27s_theorem) and a [certain strengthening the finite Ramsey Theorem](http://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem#The_strengthened_finite_Ramsey_theorem) which are not provable in [Peano Arithmetic](http://en.wikipedia.org/wiki/Peano_arithmetic). – 2012-06-07
-
4@GJB: It would help, I think, if you asked what you are actually looking for, rather than trying to pose a problem along with an ad-hoc dismissal of the obvious answer to the problem. – 2012-06-07
-
1+1 Hurkyl. Speficifically, if you want to exclude proofs that are "mild deformations of" the obvious one, you owe us a _definite_ and operational _definition_ of which proofs you accept and which ones you don't. – 2012-06-07
-
0Sometimes you need $\forall k\leq n. P(k)$ as induction hypothesis. – 2012-06-07
-
0How about "for all $n$,$\pi$ calculated to $n$ decimal digits is less than $\frac{22}{7}$"? – 2012-06-09
3 Answers
How about, "for all $n$, the $n$th digit in the decimal expansion of $1/3$ is 3"?
EDIT: OK, no one likes this example, I'll try another one: for all $n$, the Riemann zeta function has more than $n$ zeros in the critical strip.
-
21/3 is rational, so it has periodic decimals. I guess we could use this fact and a period as a base case. – 2012-06-07
-
0Not sure I see this. If you know that it's periodic and the repeating part is a 3 then I'm not sure there's anything to prove. – 2012-06-07
Provable in what? Note that provability is always w.r.t. to some formal system/theory, otherwise it is meaningless. Often it is omitted because it is clear from context what formal system we are using but in your question it is not clear.
To answer the question in the title, assume that $T$ is a rich-enough (e.g. contains Robinson's $Q$) effective (i.e. recursive system of axioms) first-order theory about natural number. Then by Godel's theorem there is a sentence of the form $\forall x \varphi(x)$ which is true but unprovable. Moreover for every natural number $n$ $T$ proves $\varphi(n)$. Theory $T$ can contain induction.
To answer the question in the post, if $\forall x \varphi(x)$ is provable in some theory $T$ then it follows by logic that for all terms $t$, $T$ proves $\varphi(t)$. Let $t=x+1$, then $T$ prove $\varphi(x+1)$ and again by logic it follows that $T$ proves $\varphi(x) \rightarrow\varphi(x+1)$. In other words, if $\forall x \varphi(x)$ is provable then $\forall x [\varphi(x) \rightarrow \varphi(x+1)]$ is also provable.
This paper has one such example and this paper has general method for obtaining statements that are not provable in PA.