4
$\begingroup$

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.

  • 2
    Sure, but one will find many interesting things along the way.2012-04-05
  • 1
    @AndréNicolas so the answer is yes? I didn't think Mathematics was that bad. Who has proven this?2012-04-05
  • 1
    This might be of interest: http://math.stackexchange.com/questions/65248/are-there-statements-that-are-undecidable-but-not-provably-undecidable2012-04-05
  • 0
    @simplicity: Folklore, I do not have specific reference. Can push through a proof, it is easy to see what to do. As to "that bad," Incompleteness does not prevent beautiful results from being proved every year.2012-04-05
  • 1
    @simplicity: "didn't think mathematics was that bad". Ooh, so much to learn.2012-04-05
  • 0
    @DejanGovc Is there a more general proof that isn't based on ZFC?2012-04-05
  • 7
    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?2012-04-05

1 Answers 1

3

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.

  • 7
    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.2012-04-06
  • 1
    I do not understand the answer. Is the answer to the OP yes or no?2015-10-27