2
$\begingroup$

Suppose that I'm a working mathematician that has just proved a Theorem, say, in Number Theory.

Does Gödel's Incompleteness Theorem imply that I can't know for sure if there exists a proof of the logical negation of my Theorem?

$\endgroup$
4
  • 7
    $\begingroup$ Goedel's Second Incompleteness Theorem implies that there is a formal, finitistic proof that the logical negation of your theorem cannot be proven from the axioms of Peano Arithmetic if and only if Peano Arithmetic is inconsistent. Goedel's Theorems are not about "truth" and "falsity", they are about provability. $\endgroup$ – Arturo Magidin May 8 '12 at 20:35
  • 1
    $\begingroup$ I don't know if it will help or not, but here's an answer I wrote some time ago about trying to understand what Goedel's theorems tell us. $\endgroup$ – Arturo Magidin May 8 '12 at 20:37
  • 1
    $\begingroup$ The Second Incompleteness Theorem shows that a certain sentence $\text{Con}_{PA}$ of PA, which seems to capture the meaning of consistency of PA, is not provable in PA (if PA is consistent!). Not to worry, PA is consistent. $\endgroup$ – André Nicolas May 8 '12 at 20:47
  • 1
    $\begingroup$ The second incompleteness theorem implies that you can't prove inside the theory that there is no proof of the logical negation of your theorem. $\endgroup$ – Yuval Filmus May 8 '12 at 22:37
2
$\begingroup$

No, that is a complete misunderstanding (but understandable given the incorrect philosophical use often made of Gödel's theorem.

As long as Number Theory is consistent by definition there can't be a proof of the negation of your statement.

The consistency of your axiom system is something one simply has to take on faith and that has nothing to do with metamathematics. After all if the system you are using was inconsistent than any demonstration in that system (or one of equivalent power) would be useless since you can prove anything in an inconsistent system. Unfortunately, Gödel's theorems are often invoked as if it showed this simple philosophical point: if your basic principles of reasoning are flawed then you can't use them to reason your way out of the error.

What Gödel's first incompletness theorem (really the Gödel-Rosser theorem) tells you is that IF your axiom system is consistent (you can't prove any statement and it's negation), strong enough to represent basic number theory and you can enumerate what the system's axioms are (technically the axioms are computably enumerable) then there is sentence which is neither provable nor refutable from those axioms.

The reason for the confusion is that Gödel's second incompleteness theorem tells us that if a theory T satisfies the above (such as what you use to do number theory) then CON(T) is neither provable or disprovable in T where CON(T) is the formal statement that T is consistent. But a key point here is that CON(T) is undecidable in T not because of some uncertainty of the consistency of T (we are assuming T is consistent) but because it's not clear if the formal statement CON(T) really captures the informal notion of proof. Indeed $T + \lnot CON(T)$ is actually a consistent theory. It just turns out that this theory allows infinite integers which code up fake proofs for a sentence and it's negation causing CON(T) to be false even though the system is actually consistent.

$\endgroup$
4
  • $\begingroup$ I don't think this is correct or, in any case, clearly explained. It looks more like a misrepresentation of the working mathematician's understanding. $\endgroup$ – Andrés E. Caicedo Mar 10 '19 at 13:31
  • $\begingroup$ In what fashion? If you are talking about the end it is simply noting the following basic point. Assume T is consistent but T+ $\lnot CON(T)$ is not then if $M \models T$ then $M \models \lnot CON(T) = \exists P$( P PROVES $\bot$ from $T$). Hence, the provability predicated as interpreted in M says that $\bot$ is provable from $T$ when in actual fact it isn't (T consistent). Hence provability predicate in M (arbitrary T model) failed to capture the true well-founded notion of provability. $\endgroup$ – Peter Gerdes May 2 '19 at 13:50
  • $\begingroup$ As for the earlier part this is simply summarizing the basic philosophical point that if one isn't sure of the consistency of T the mere (hypothetical) fact that there was a T proof of CON(T) would grant you now additional certainty in consistency of T since if T is inconsistent it also proves CON(T). $\endgroup$ – Peter Gerdes May 2 '19 at 14:20
  • $\begingroup$ Also it is a correct representation of my understanding and I'm a working mathematician (indeed logician) and I can assure you it does represent my understanding. $\endgroup$ – Peter Gerdes May 2 '19 at 14:22
0
$\begingroup$

Gödel's First Incompleteness Theorem states that some true properties of Arithmetics cannot be proven from axiomatizations of Arithmetics like Q (Robinson Arithmetics) or PA (Peano Arithmetics).

Thus, Gödel's First Incompleteness Theorem does not imply that the negation of a theorem of Arithmetics might be provable: The answer to your question is "no".

$\endgroup$
1
  • $\begingroup$ I don't think this is quite accurate. One needs to further assume the consistency of Q and even of PA to make the first paragraph correct. The answer to the question is arguably yes, but the relevant result is the second incompleteness theorem rather than the first: if PA is consistent, we cannot know for sure, arguing within PA, and if it isn't, it surely proves the negation of the working mathematician's result. $\endgroup$ – Andrés E. Caicedo Mar 10 '19 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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