0
$\begingroup$

The proof for Gödel's incompleteness theorem shows that for any formal system $F$ strong enough to do arithmetic, there exists a statement $P$ that is unprovable in $F$ yet $P$ is true.

Let $F$ be the system we used to prove this theorem.

Then $P$ is unprovable in $F$ yet we proved it is true in $F$.

Contradiction.

Am I saying something wrong? Is $F$ forced to be inconsistent?

$\endgroup$

closed as off-topic by Andrés E. Caicedo, Carl Mummert, Claude Leibovici, user91500, Namaste Jun 3 '17 at 15:50

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user91500, Namaste
  • "This question is not about mathematics, within the scope defined in the help center." – Andrés E. Caicedo, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ P is true according to the "natural interpretation" of it. See Gödel's Incompleteness Theorems: G's sentence asserts its own unprovability (in the system F). But G's Th shows that it is unprovable in F; thus, the G's sentence "speaks the true". $\endgroup$ – Mauro ALLEGRANZA May 31 '17 at 14:27
  • 2
    $\begingroup$ The underlying assumption is that $\mathsf{PA}$ is sound, meaning that $\mathbb N\models\mathsf{PA}$. To say that $P$ is true is simply to claim that $\mathbb N\models P$. A different matter is how to verify the latter. Any proof of it by necessity takes place in a stronger theory than $\mathsf{PA}$. $\endgroup$ – Andrés E. Caicedo May 31 '17 at 14:39
  • 3
    $\begingroup$ " let F be the system of logic we use to prove godels theorem." NO; the G's Th is about the system $F$ (e.g. first-order Peano arithmetic: usually abbreviated $\mathsf {PA}$) and it asserts that $P$ is unprovable in F. G's Th itself is proved in a meta-theory that we can formalize in some new formal system. $\endgroup$ – Mauro ALLEGRANZA May 31 '17 at 14:49
  • 1
    $\begingroup$ No, the theorem requires the system F to be consistent. Otherwise, P (and anything else) is provable in F. But (from the second incompleteness theorem) F itself cannot prove that F is consistent. Gödel assumes that $\mathsf{PA}$ is consistent, since he assumes that it has a model (namely, $\mathbb N$). This assumption puts the argument outside of $\mathsf{PA}$. (And yes, Gödel does not mention $\mathsf{PA}$ explicitly, because he argues in terms of the system of Russell and Whitehead's Principia. The same remarks apply.) $\endgroup$ – Andrés E. Caicedo May 31 '17 at 15:06
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is based on a misreading - choosing a system F at the beginning and then re-choosing F to be something else later . $\endgroup$ – Carl Mummert May 31 '17 at 18:13
2
$\begingroup$

It seems you are missing a key hypothesis in the statement of Gödel's incompleteness theorem. You wrote in a comment:

Godels theorem is proved In a certain system L and shows that for any F (strong enough to do arithematic) P is true and unprovable.

This is incorrect. Gödel's theorem is proved in a certain system $L$ and says the following. Suppose $F$ is a formal system which is strong enough to do arithmetic and consistent (that is, it does not prove a contradiction). Then a certain arithmetic statement $P$ (which is defined in terms of the system $F$) is true but is not provable in $F$.

Now you want to substitute $L$ for $F$. That's fine, but in order to apply Gödel's theorem, you need to know that the hypotheses are satisfied. That is, you need to know that $L$ is strong enough to do arithmetic and that $L$ is consistent. Verifying the first hypothesis is easy, but verifying the second hypothesis is not easy at all. Before you can carry out your argument, you need to prove (within the system $L$) that $L$ is consistent.

In fact, your argument does work (modulo some details that are technical but important) if $L$ could prove that $L$ is consistent, and would reach a contradiction. So actually, your argument shows that if $L$ can prove that $L$ is consistent, there is a contradiction in $L$ (and so $L$ is not actually consistent at all!). This is exactly the statement of Gödel's second incompleteness theorem, which says that no consistent formal system strong enough to do arithmetic can prove its own consistency.

(The technical details: to reach a contradiction, you need to not prove $P$ within $L$, but prove that $L$ proves $P$ within $L$. That is, $L$ needs know not just that $P$ is true, but that $L$ can prove $P$, since this is what contradicts the fact that $P$ is unprovable in $L$. The fact that if $L$ proves $P$ then $L$ proves that it proves $P$ is a consequence of being able to do arithmetic in $L$.

These details are important because in order to prove that $L$ proves $P$, you have to actually have an honest proof of $P$ within $L$. If you have a proof within $L$ that $L$ is consistent, then you get such an honest proof of $P$ from Gödel. But if you just assume for a contradiction that $L$ is consistent, you don't get such a proof and so you cannot conclude that $L$ proves $P$; instead you only know that $P$ is true. So you can't reach a contradiction: there is no contradiction between the two statements "$P$ is true" and "$L$ cannot prove $P$".)

$\endgroup$
  • $\begingroup$ Actually, the argument, as sketched, would reach a contradiction only if one assumes soundness of L (that is, that L only proves true statements). This is stronger than mere consistency. (By the way, Gödel's result does not require this assumption, but his original proof does.) $\endgroup$ – Andrés E. Caicedo May 31 '17 at 16:55
  • $\begingroup$ I don't think so (and I think you may be misinterpreting OP's argument, or maybe I am). If $L$ proves its consistency, then $L$ proves $P$ and $L$ proves that $L$ does not prove $P$. But if $L$ proves $P$, then $L$ proves that $L$ proves $P$. So $L$ proves both that $L$ proves $P$ and that $L$ does not prove $P$, which is a contradiction. (Of course, OP did not make explicit the step where $L$ proves that $L$ can prove $P$, but I think this version is closer to what they had in mind than any argument using soundness.) $\endgroup$ – Eric Wofsey May 31 '17 at 17:04
  • 1
    $\begingroup$ Ah, but there's a difference between $L$ being consistent and $L$ proving that $L$ is consistent. It is possible that $L$ is consistent, but $L$ cannot prove that $L$ is consistent. $\endgroup$ – Eric Wofsey May 31 '17 at 17:18
  • 1
    $\begingroup$ In particular, it seems you have the following argument in mind (working within $L$). Suppose (for a contradiction) that $L$ is consistent. Then by Gödel, $P$ is true and $L$ cannot prove $P$. Therefore $L$ proves $P$ and $L$ cannot prove $P$, which is a contradiction. The error in this argument is that "Therefore $L$ proves $P$" does not follow. Within this argument we know that $P$ is true, but we don't know that $L$ proves $P$. $\endgroup$ – Eric Wofsey May 31 '17 at 17:23
  • 1
    $\begingroup$ @EricWofsey Well, "truth" has a technical meaning. The difference between it and provability is essential in the context of the incompleteness theorems. Anyway, the OP seems satisfied, so we can move on. $\endgroup$ – Andrés E. Caicedo May 31 '17 at 18:06
2
$\begingroup$

Not the biggest expert in this, but maybe this helps until the real experts show up.

To prove a statement $\phi$ from (a first-order theory) $F$ means (by the completeness theorem) to show that it holds in all models of $F$. However, still without proving $\phi$ from $F$ we can look at some particular model of $F$ (via meta theory) and find that $\phi$ indeed holds there. So we have an external proof of $\phi$ for this specific model.

Now if $\phi$ says "$\phi$ cannot be proven from $F$", then this means that we need this meta theory on this specific model to prove $\phi$ and it cannot be done from $F$ alone.

Even another way: we showed that $\phi$ holds in some model (externally). Then $\phi$ showed that there are models where it does not hold. So not all models agree. So neither $\phi$ nor $\neg \phi$ can be provable.

$\endgroup$
  • $\begingroup$ What I'm saying is what if the meta-logic and the normal logic are the same? What if F was the normal system of logic in which we proved godels theorem? $\endgroup$ – user47376 May 31 '17 at 14:41
  • 1
    $\begingroup$ @user47376 - the issue of G's Th is exactly that the system (not "the logic"), say $F$, and the meta-system cannot be the same. If we use a "sufficiently strong" system (like Peano Arithmetic) that can prove "facts" about formal systems (and thus is suitable as a meta-theory), this kind of system cannot proves "all" that is true. Specifically, a system like $\mathsf {PA}$, when used as a meta-system, cannot prove its own consistency. This means that the formal system $\mathsf {PA}$ is in some sense "limited"; it does not mean that it is inconsistent. $\endgroup$ – Mauro ALLEGRANZA May 31 '17 at 15:32
  • $\begingroup$ My reasoning shows that it proves it's own inconsistency. Why can't they be the same? This is my question. $\endgroup$ – user47376 May 31 '17 at 15:38
  • $\begingroup$ @user47376 Something cannot be true in $F$, just provable from it. And $\phi$ says that it is not. However $\phi$ is either true or false in any model of $F$. There is no contradiction. One the one hand you showed that $\phi$ is true in some model. On the other hand you showed that it is not true in all models (that's what you call truth)! $\endgroup$ – M. Winter May 31 '17 at 15:41
  • $\begingroup$ Saying P is true is saying that it is provable in the meta-system, but since they are both F it's a contradiction. What do you mean in all models? I'm talking about a specific F, the one which we use to prove G's Th. $\endgroup$ – user47376 May 31 '17 at 15:51
0
$\begingroup$

(Disclaimer: In what follows when I say formal system I mean a first-order theory)

Be careful, you are mixing two different concepts namely "provability" and "truth".

Gödel incompleteness theorem (more correctly its generalization, Rosser's theorem) says that

If $F$ is a formal system in which you can interpret arithmetic (which roughly means that you can say what is a number, a zero, a successor, the addition and multiplication and prove the axioms of arithmetic) then it is either inconsistent, hence it proves everything, or it is incomplete (that is there are statement which aren't provable nor disprovable).

In this form of the theorem there is no reference to the concept of truth.

Actually the original Gödel's incompleteness theorem says something different:

There are statement that are not provable in Peano Arithmetic but are true in the model of the natural numbers $\mathbb N$.

A statement can be proved in a formal system $F$ but it doesn't make any sense to say that it is true in $F$, a statement is either true or false in a given interpretation.

You could define that a statement is true in a formal system $F$ if it is true in all its model, that is if it is a logical consequence of the axioms in $F$. Of course by the Gödel's completeness theorem that is equivalent to the fact that the statement is provable in $F$, so clearly this is not the correct statement of Gödel incompleteness theorem.

Hope this helps.

$\endgroup$

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