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
3
$\begingroup$
logic
induction
proof-theory
-
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