1
$\begingroup$

I have two question regarding Godel's incompletness theorem. The theorem says that every axiomatic system is either incomplete or inconsistent. If it's consistent, then there are true statements that are unprovable.

If so, then it must also be the case that there are false statements that cannot be proven to be false, becuase if we could prove that every false statement is false, then we would be able to prove every true statement - by contradiction.

If every false statement was provably false, then I could just take the unprovable true statement $A$, prove the falsehood of its negation and I would have a proof of $A$.

Then there must exist both true and false statements that cannot be proven true and false respectively.

Question: where is the logical error I'm making here?

$\endgroup$
9
  • 2
    $\begingroup$ "Every axiomatic system is either incomplete or inconsistent". It doesn't really say this. $\endgroup$ – Git Gud Sep 7 '15 at 11:32
  • 1
    $\begingroup$ You aren't making any mistake. Saying that P is true but not provable is exactly the same thing as saying that ¬P is false but not provably so. $\endgroup$ – PseudoNeo Sep 7 '15 at 11:55
  • 1
    $\begingroup$ What the person states is true for some very specific forms of mathematical statements, like Goldbach's conjecture. If Goldbach's conjecture is false, it means that there is an even integer n which is not a sum of two prime numbers. But, if such an integer exists, you can prove that it exists with only finistic computations, so you will be able to translate this fact into a proof in Peano's arithemetic PA (or even Robinson's arithmetic Q). So if Goldbach's false, PA proves it's false. But that's not true for other mathematical results (that's not true for the negation of Goldbach's conjecture… $\endgroup$ – PseudoNeo Sep 7 '15 at 12:06
  • 1
    $\begingroup$ …for instance). For this fact and many very interesting comments about what Gödel's theorem says and does not say, I can't recommend Franzén Gödel's theorem: an incomplete guide to its use and abuse enough. This book is absolutely marvelous and clarifies a lot of things. It is also very readable, as it aims to be readable by philosophers or people from social sciences. $\endgroup$ – PseudoNeo Sep 7 '15 at 12:09
  • 1
    $\begingroup$ @skyking: typically, the statement in question can be proven in some stonger system whose axioms we regard as true. So that is how we know the statement is true. At the same time, the statement can be unprovable in a weaker system that we happen to be studying. E.g. a statement can be provable in set theory, but unprovable in Peano arithmetic. $\endgroup$ – Carl Mummert Sep 7 '15 at 12:20
3
$\begingroup$

According to G's Th, it is correct to say that :

"there must exist false sentences that cannot be proven false".

If a "suitable" theory $T$ is consistent, then - by G's Th - there exists a true sentence $G_T$ such that:

$T \nvdash G_T$ and $T \nvdash \lnot G_T$;

this is the incompleteness of $T$.

But if $G_T$ is true, then $\lnot G_T$ is false.

To say that a sentence $A$ is "provably false (in the theory $T$)" must be transalted as :

if $A$ is false, then $T \vdash \lnot A$.

Thus, $\lnot G_T$ is a false sentence of $T$ and $T \nvdash G_T$, i.e. :

$T \nvdash \lnot (\lnot G_T)$

and so we have that $T$ has a false sentence (i.e. $\lnot G_T$) that cannot be proved false.

$\endgroup$
0
$\begingroup$

How do you know that a statement is true if one cannot prove it? If a statement is not decideable from the given axioms you can decide whether it is true or false by adding the statement or its negation to the axioms.

$\endgroup$
3
  • $\begingroup$ Typically, the way we know a statement is true is that it is provable in some stronger system $T'$, whose axioms we regard as true, even though the statement may not be provable in the system $T$ that we are studying. Adding the negation of a true statement as an axiom does not make the negation true; rather, it simply makes a consistent system with a false axiom. $\endgroup$ – Carl Mummert Sep 7 '15 at 12:05
  • $\begingroup$ @CarlMummert So we can't prove the axiom of choice in ZF, but in the stronger ZFC we can and in the also stronger ZF-C we can disprove it. How do you kvow that one or the other stronger system's axioms should be regarded as true? $\endgroup$ – skyking Sep 7 '15 at 12:20
  • 1
    $\begingroup$ @skyking: the argument that we should regard a particular set of axioms as true is not, strictly speaking, a mathematical one. An entire book could be written on the subject. But the most common way is that we begin with an "intended" structure, such as the natural numbers, and we argue that the axioms of our system are true in that structure. This is how we argue that Peano arithmetic is true (by arguing it is true in the standard natural numbers) and how we argue that ZFC is true (by arguing it is true in the standard cumulative hierarchy). $\endgroup$ – Carl Mummert Sep 7 '15 at 12:22
0
$\begingroup$

It is not true that EVERY axiomatic system is incomplete. Godel himself proved the completeness of first order logic. It is true that a system sufficiently rich enough to do mathematics with (i.e. one that can formulate the Peano axioms) is incomplete.

In this case what you say is true. There are false statements which are not provably false; I mean, we can't decide on their truth value.

$\endgroup$
6
  • $\begingroup$ The sense of "completeness" in the theorem that first-order logic is complete is different than the sense of "completeness" in which Gödel's theorem proves that Peano arithmetic is incomplete. $\endgroup$ – Carl Mummert Sep 7 '15 at 12:04
  • $\begingroup$ Can you please explain? I didn't realise that $\endgroup$ – User0112358 Sep 7 '15 at 12:05
  • 3
    $\begingroup$ First-order logic is complete in the following sense: a sentence is provable if and only if the sentence is true in every model. First-order logic is not complete in the sense that every statement or its negation is provable. There are lots of sentences that are neither provable or disprovable in ordinary first-order logic. That latter sense of completeness is what the incompleteness theorem is about. Unfortunately, the terminology has become established, with two meanings for the term "complete", which is a perpetually confusing point for people learning the field. $\endgroup$ – Carl Mummert Sep 7 '15 at 12:07
  • $\begingroup$ Thank you. They seem very similar, I will have to meditate on the difference! $\endgroup$ – User0112358 Sep 7 '15 at 12:09
  • 1
    $\begingroup$ If we can't decide on their truth value, how can we know they're false? $\endgroup$ – skyking Sep 7 '15 at 12:16

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.