0

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?

user4205580
  • 2,083
  • 2
    "Every axiomatic system is either incomplete or inconsistent". It doesn't really say this. – Git Gud Sep 07 '15 at 11:32
  • 1
    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. – PseudoNeo Sep 07 '15 at 11:55
  • This video made me ask this question. In 3:02 the person states that if a theorem is false, it's provably false. Which is wrong, apparently. I know youtube is not the best source of mathematical knowledge, but I just wanted to make sure he was wrong saying it. – user4205580 Sep 07 '15 at 12:01
  • 1
    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… – PseudoNeo Sep 07 '15 at 12:06
  • 1
    …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. – PseudoNeo Sep 07 '15 at 12:09
  • But what true is a "true" statement if it cannot be proven to be true? – skyking Sep 07 '15 at 12:15
  • @skyking There is the concept of 'truth' and the concept of 'provable'. In mathematical practice, through different, they coincide. But in Mathematical Logic the distinction is very important. The meaning of 'truth' in use isn't easily explainable. I suggest you study an intro to Mathematical Logic. – Git Gud Sep 07 '15 at 12:19
  • 1
    @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. – Carl Mummert Sep 07 '15 at 12:20
  • Typically, the consistency of Peano's arithmetic is a true statement is the usual sense of this word in mathematics: we can prove that the set $\mathbb N = {0, 1, 2, ...}$ with the usual addition and multiplication satisfy all of Peano's axioms, so they are consistent, but Peano's arithmetic cannot prove its own consistency because of Gödel's theorem. So the arithmetic statement $\mathbf{Con}({\mathsf{PA}})$ expressing the fact that Peano's arithmetic is consistent is a true fact, it is provable in the usual set theory $\mathsf{ZFC}$, but it's not provable in $\mathsf{PA}$ itself. – PseudoNeo Sep 07 '15 at 12:24

3 Answers3

3

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.

Mauro ALLEGRANZA
  • 94,169
0

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.

coproc
  • 1,538
  • 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. – Carl Mummert Sep 07 '15 at 12:05
  • @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? – skyking Sep 07 '15 at 12:20
  • 1
    @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). – Carl Mummert Sep 07 '15 at 12:22
0

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.

User0112358
  • 523
  • 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. – Carl Mummert Sep 07 '15 at 12:04
  • Can you please explain? I didn't realise that – User0112358 Sep 07 '15 at 12:05
  • 3
    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. – Carl Mummert Sep 07 '15 at 12:07
  • Thank you. They seem very similar, I will have to meditate on the difference! – User0112358 Sep 07 '15 at 12:09
  • 1
    If we can't decide on their truth value, how can we know they're false? – skyking Sep 07 '15 at 12:16
  • Study the proof of Gödel's incompleteness theorems. Ernest Nagel's book Godel's Proof is an excellent book and will answer your question. I wouldn't do it justice in 430 characters. – User0112358 Sep 07 '15 at 12:21