2
$\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)"?

  • 0
    How about "for all $n$,$\pi$ calculated to $n$ decimal digits is less than $\frac{22}{7}$"?2012-06-09

3 Answers 3

2

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.

1

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.

  • 0
    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.2012-06-07
0

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