Kevin's Watch

Posted: **Sun Aug 12, 2007 12:47 pm**

I wish I understood Gödel's proof. Maybe someone who knows it well can explain it to me. But I probably need a broader understanding of mathematics, and maybe more things.

I understand the "strange loops" that Hofstadter is talking about. Unfortunately, I've never come close to finishing his book, so I don't understand what it all proves. I mean, I can see the problem with Self-swallowing and Run-of-the-mill sets. But I don't see the "truth" that the set of all Run-of-the-mill sets is, itself, Run-of-the-mill, and simply can't be proven by the rules of sets. I only see that it defies being either true or false.

And I don't see that the following pair of sentences or either individual sentence is necessarily true:
The following sentence is true.
The preceding sentence is false.
I just see that they contradict each other.

I do not know of any statement that's true in any system, but cannot be proven by that system. Is there an example that I can understand - meaning, I guess, a relatively simple one - of a mathematical statement that is true but cannot be proven true under the rules?

Posted: **Mon Aug 13, 2007 5:25 pm**

Your questions have answers that are too technical for me to rattle off in my own words. After reading many different variations of Godel's Theorem written by many different people, I've come to understand it--and then forget the details of the reasoning time after time. It's very complex reasoning.

Constructing a "Godel sentence," or a statement which is true within a system but unprovable within that system, involves the actual proof itself. You can't just look at the sentence and see how it's both true and yet unprovable. The best I can do at this time is to quote Wikipedia.

link

Gödel's first incompleteness theorem shows that any such [sufficiently complex] system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false. Or one might say, no formal system which aims to define the natural numbers can actually do so, as there will be true number-theoretical statements which that system cannot prove. . . .

The existence of an incomplete system is in itself not particularly surprising. For example, if you take Euclidean geometry and you drop the parallel postulate, you get an incomplete system (in the sense that the system does not contain all the true statements about Euclidean space). A system can be incomplete simply because you haven't discovered all the necessary axioms.

What Gödel showed is that in most cases, such as in number theory or real analysis, you can never create a complete and consistent finite list of axioms, or even an infinite list that can be produced by a computer program. Each time you add a statement as an axiom, there will always be other true statements that still cannot be proved as true, even with the new axiom. Furthermore if the system can prove that it is consistent, then it is inconsistent.

It is possible to have a complete and consistent list of axioms that cannot be produced by a computer program (that is, the list is not computably enumerable). For example, one might take all true statements about the natural numbers to be axioms (and no false statements). But then there is no mechanical way to decide, given a statement about the natural numbers, whether it is an axiom or not.