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.

I was thinking about the incompleteness theorem. In a book it said that say RH might be unprovable and that a Mathematician could be working on a problem that is unprovable. But, was wondering is it even worse than that.

Are there problems such that it's unprovable, but cannot be proven unprovable. So the problem wouldn't be able to be solved by a Mathematician and the Mathematician will never know if it can be solved.

share|improve this question
2  
Sure, but one will find many interesting things along the way. –  André Nicolas Apr 5 '12 at 23:17
    
@AndréNicolas so the answer is yes? I didn't think Mathematics was that bad. Who has proven this? –  simplicity Apr 5 '12 at 23:30
1  
This might be of interest: math.stackexchange.com/questions/65248/… –  Dejan Govc Apr 5 '12 at 23:32
1  
@simplicity: "didn't think mathematics was that bad". Ooh, so much to learn. –  George Lowther Apr 5 '12 at 23:36
6  
The word "unprovable" makes it easy to confuse oneself, because it invites thinking that "unprovable" is a property of a particular formula in itself. Really, however, it is a relation between a formula and a particular set of axioms/assumptions. So, you want a sentence $\phi$ such that $T\not\vdash \phi$ but $S\not\vdash (T\not\vdash \phi)$ for some theories $S$ and $T$? Do you require that $S$ and $T$ are the same theory? –  Henning Makholm Apr 5 '12 at 23:44
show 2 more comments

1 Answer 1

Let $\gamma_{PA}$ be the Gödel sentence for $PA$, and let $\mathbf{Proof}_{PA}(\theta,y)$ be the predicate the says $y$ encodes a proof for $\theta$ from $PA$. Then we have

$$ \mathbb{N} \models \gamma_{PA} \longleftrightarrow (\forall y) \neg \mathbf{Proof}_{PA}(\theta,y)$$

From the proof of the first incompleteness theorem, we know that

$$ PA \nvdash \gamma_{PA}, ~~~ PA \nvdash \neg \gamma_{PA}$$

Thus $\mathbb{N} \models \gamma_{PA}$, so that the Gödel is sentence is "true," albeit unprovable in $PA$.

Now, let $\square_{PA}(\theta)$ be the predicate stating that $\theta$ is provable in $PA$. Suppose that

$$PA \vdash \neg \square_{PA}(\gamma_{PA})$$

Then $PA$ would be able to prove that $PA$ cannot prove something, and hence

$$PA \vdash \mathbf{Const}_{PA}$$

which contradicts the Second Incompleteness Theorem.

share|improve this answer
5  
The upshot of this is that no theory satisfying some hypotheses can prove of itself that there is some unprovable formula, because then it could prove itself consistent, contradicting the incompleteness theorems. This is a formalization of the fact that a general theory is consistent if and only if there is some formula that is not provable in it. –  Carl Mummert Apr 6 '12 at 0:41
add comment

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.