Godel's Incompleteness Theorem

[gsingh2011]

So Godel's Incompleteness Theorem states that we cannot prove all facts about the natural numbers. Are we still able to prove that those proofs are impossible? Or are we stuck not knowing whether it is possible to prove something?

The second part of the theorem says that any system that can prove certain facts about the natural numbers cannot proved to be consistent. I got this from wikipedia and the wording confuses me. What certain facts? Does inconsistent mean that any theorem you prove may not be true?

Thanks in advance.

 

[CRGreathouse]

An inconsistent system* can prove any proposition that can be phrased in its language. That makes them boring. Intuitively, they're systems that are "wrong" about something: they assert that 1 = 1 and that 1 ≠ 1, for example.

Goedel's theorem shows that we can't show that any reasonably strong system isn't so strong that it's actually inconsistent. (We can prove this from some other system, but then that system itself might not be consistent...!)

* which contains at least basic logic

 

[gsingh2011]

So does that mean that no system can be proved consistent? Doesn't that mean that we can trust that anything we prove won't be contradicted sometime in the future?

 

[Hurkyl]

So Godel's Incompleteness Theorem states that we cannot prove all facts about the natural numbers.

Slightly misstated (depending on what precisely you mean, either the theorem has a broader scope than what you stated, or you are being presumptuous)

Are we still able to prove that those proofs are impossible? Or are we stuck not knowing whether it is possible to prove something?

It is a corollary that any recursively enumerable theory containing integer arithmetic must have an undecidable proposition that cannot be proven undecidable within the theory.

It's a simple argument if you're used to computability-type arguments -- if you could decide if a proposition was undecidable, then there is an easy way to come up with a complete and recursively enumerable theory that would contradict Gödel's theorem: simply iterate through all propositions, and when you get to one that is undecidable, add it to your list of axioms.

(The little details are messy, but straightforward)

The second part of the theorem says that any system that can prove certain facts about the natural numbers cannot proved to be consistent. I got this from wikipedia and the wording confuses me. What certain facts? Does inconsistent mean that any theorem you prove may not be true?

Thanks in advance.

The usual natural language statement is "no sufficiently strong, consistent, (recursively enumerable) theory can prove itself consistent". One way to be sufficiently strong is to be able to talk about the algebra of integers.

 

[CRGreathouse]

The usual natural language statement is "no sufficiently strong, consistent, (recursively enumerable) theory can prove itself consistent"

I prefer to say that every (r.e.) system is weak, inconsistent, or incomplete.

 

[mathplease]

Moderator action: mathplease's thread merged into this ongoing discussion.[/color]

I recently read Godel's Proof by Nagel/Newman and realized I have some fundamental misunderstandings of mathematics which I hope to resolve. Any light or direction on the following questions would be much appreciated:

1. What makes a mathematical statement true or false?

2. Why must a mathematical statement be only either true or false?

 

[disregardthat]

I recently read Godel's Proof by Nagel/Newman and realized I have some fundamental misunderstandings of mathematics which I hope to resolve. Any light or direction on the following questions would be much appreciated:

1. What makes a mathematical statement true or false?

2. Why must a mathematical statement be only either true or false?

In my understanding; a mathematical statement in a formal axiomatic system (such as set theory) is true if it follows logically from the axioms, and false if it's negation follows from the axioms. That a statement must be either true or false is a logical axiom in classical logic, though alternative logical systems exist. For example in intuitionistic logic the law of excluded middle is not an axiom and is actually false in some formal axiomatic systems. Thus in classical logic a statement is true if and only if its negation is false, but in intuitionistic logic there is no such equivalence.

 

[mathplease]

In my understanding; a mathematical statement in a formal axiomatic system (such as set theory) is true if it follows logically from the axioms, and false if it's negation follows from the axioms.

If this is the case, how can mathematical statements be true yet also unprovable from the axioms?

 

[disregardthat]

If this is the case, how can mathematical statements be true yet also unprovable from the axioms?

It should be instructive to note that a formula is true if and only if it is a theorem.
The law of excluded middle only says that (P or (not P)) is true for any formula P, it does not state that there is a proof of either P or (not P). Hence it is only applicable if either P or (not P) has been proven. That a formula P is unprovable does not mean that it is false, it means that we cannot bridge the gap between the formula P and the axioms of our formal system by means of our given rules of inference.

It is not correct to say that P is true, nor that (not P) is true if P is unprovable. But it is correct to say that (P or (not P)) is true even if P is unprovable. You could say that the law of excluded middle gives us nothing when it comes to unprovable statements. A formula is not true by virtue of itself, but by that it can be proven.

 

[D H]

If this is the case, how can mathematical statements be true yet also unprovable from the axioms?

The canonical example is the continuum hypothesis. Despite many attempts to do so in the late 19th century, proving that the continuum hypothesis derives from some standard set of axioms of set theory (typically Zermelo-Fraenkel set theory) proved elusive. The problem was deemed so central to mathematics that Hilbert identified proving the continuum hypothesis as the #1 outstanding problem of mathematics back at the start of the 20th century. The best that could be done for a while was Gödel's 1940 proof that no (new) contradiction would arise in Zermelo-Fraenkel set theory by assuming the continuum hypothesis to be true. I said a while because in 1963 Paul Cohen showed that no (new) contradiction would arise in Zermelo-Fraenkel set theory by assuming the continuum hypothesis to be false. This moved Gödel's theorem from a puzzling back burner issue to the forefront. The #1 problem in mathematics turned out to be the first example of an unprovable statement.

 

[mathplease]

It is not correct to say that P is true, nor that (not P) is true if P is unprovable.

This seems to contradict what is implied in Godel's Proof by Nagel and Newman:

"In other words, given any consistent set of arithmetical axioms, there are true mathematical statements that cannot be derived from the set"

If mathematical statements are true by definition only if they can be proved from the axioms, mathematical statements could not be both true and unprovable. The book emphasises that this is not a mistake:

"Godel then showed (iii) that, though G is not formally demonstrable, it nevertheless is a true arithmetical formula... G is true in the sense that it claims that a certain arithmetical property defined by Godel is possessed by no integer -- and indeed, no integer possesses the property, as Godel shows"

 

[PhysDrew]

This seems to contradict what is implied in Godel's Proof by Nagel and Newman:

"In other words, given any consistent set of arithmetical axioms, there are true mathematical statements that cannot be derived from the set"

If mathematical statements are true by definition only if they can be proved from the axioms, mathematical statements could not be both true and unprovable. The book emphasises that this is not a mistake:

"Godel then showed (iii) that, though G is not formally demonstrable, it nevertheless is a true arithmetical formula... G is true in the sense that it claims that a certain arithmetical property defined by Godel is possessed by no integer -- and indeed, no integer possesses the property, as Godel shows"

I think this might be the same sort of argument Turing used, albeit from a different slant. I think the basics of it was as follows;
Imagine firstly we are dealing with letters. Consider the names Sayers, Atkins, Piquet, Mather, Belamy and Panoff. Now take the first letter of the first name and advance it by one place ('T'). Now do the same for the second letter in the second name, and so on. You end up with TURING, which can't have been in the original list. This idea carries over to numbers as well of course. Turing used this argument to demonstrate how a list of computable numbers could be used to generate uncomputable numbers. The argument linking the two esapes me at the moment, but still the idea is there.

 

[HallsofIvy]

Moderator action: mathplease's thread merged into this ongoing discussion.[/color]

I recently read Godel's Proof by Nagel/Newman and realized I have some fundamental misunderstandings of mathematics which I hope to resolve. Any light or direction on the following questions would be much appreciated:

1. What makes a mathematical statement true or false?

2. Why must a mathematical statement be only either true or false?

To answer the second statement first, in logic a "proposition" is, by definition, a statement that is either true or false, whether you know which or not. Logic only deals with propositions and the same is true of mathematics.

However, in my opinion, it is better not to use the words "true" and "false" when talking about mathematical statements. Rather, use the words "valid" (meaning that the proposition follows from the axioms) and "invalid"- meaning that the negation of the proposition follows from the axioms.

Godel's proof essentially says that, for any mathematical system, one of three things must be true (to use CRGreathouse's formulation):
1) Weak- not strong enough to include a definition of the positive integers.
2) Inconsistent- there exist propositions such that the proposition and its negation follow from the axioms.
3) Incomplete- there exist propositons such that neither the proposition nor its negation follow from the axioms.

 

[Hurkyl]

Godel's proof essentially says that, for any mathematical system, one of three things must be true (to use CRGreathouse's formulation):
1) Weak- not strong enough to include a definition of the positive integers.
2) Inconsistent- there exist propositions such that the proposition and its negation follow from the axioms.
3) Incomplete- there exist propositons such that neither the proposition nor its negation follow from the axioms.

For the sake of precision, there is a fourth:
4) Not recursively enumerable- there are infinitely many axioms, and there doesn't even exist an algorithm to enumerate them

 

[mathplease]

However, in my opinion, it is better not to use the words "true" and "false" when talking about mathematical statements. Rather, use the words "valid" (meaning that the proposition follows from the axioms) and "invalid"- meaning that the negation of the proposition follows from the axioms.

In what sense can neither valid nor invalid statements be "true"? I'm more or less struggling to understand:

"Godel then showed (iii) that, though G is not formally demonstrable, it nevertheless is a true arithmetical formula... G is true in the sense that it claims that a certain arithmetical property defined by Godel is possessed by no integer -- and indeed, no integer possesses the property, as Godel shows"

 

[mathplease]

This seems to answer my question:

"A string of TNT has been found; it expresses, unambiguously, a statement
about certain arithmetical properties of natural numbers; moreover, by reasoning
outside the system we can determine not only that the statement is a
true one, but also that the string fails to be a theorem of TNT.

The phrase "by reasoning outside the system" is crucial. Strangely enough, we should
only speak about truth when we interpret sentences, not when we use mechanical rules
of derivation. In the latter case, we should talk about "provability". When the proof of
a theorem is expressed inside the theory then that theorem is provable. As it turns out,
there is a better definition of "truth" than that of interpreting a phrase, but it seems to
be less general than the concept of truth every human being possesses."

source: http://www.lix.polytechnique.fr/~liberti/goedel.pdf