Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
8  
Well, if $P(n+1)$ is true, then $P(n) \Rightarrow P(n+1)$ is true regardless of whether $P(n)$ is. –  dtldarek Jun 7 '12 at 12:32
5  
There are results such as Goodstein's Theorem and a certain strengthening the finite Ramsey Theorem which are not provable in Peano Arithmetic. –  Arthur Fischer Jun 7 '12 at 12:49
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. –  Hurkyl Jun 7 '12 at 13:22
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. –  Henning Makholm Jun 7 '12 at 15:25
    
Sometimes you need $\forall k\leq n. P(k)$ as induction hypothesis. –  Raphael Jun 7 '12 at 23:13

3 Answers 3

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.

share|improve this answer
2  
1/3 is rational, so it has periodic decimals. I guess we could use this fact and a period as a base case. –  user1708 Jun 7 '12 at 12:38
    
Not 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. –  Gerry Myerson Jun 7 '12 at 12:53

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.

share|improve this answer

This paper has one such example and this paper has general method for obtaining statements that are not provable in PA.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.