3
$\begingroup$

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)"?

  • 8
    Well, if $P(n+1)$ is true, then $P(n) \Rightarrow P(n+1)$ is true regardless of whether $P(n)$ is.2012-06-07
  • 5
    There 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
  • 0
    Sometimes you need $\forall k\leq n. P(k)$ as induction hypothesis.2012-06-07
  • 0
    How about "for all $n$,$\pi$ calculated to $n$ decimal digits is less than $\frac{22}{7}$"?2012-06-09

3 Answers 3