goedel's theorem

[johan01]

Can anybody help

 

i have been reading up on goedels incompleteness theorem, and still am not able to grasp its true meaning and implication.

 

Is there somewhere , where i can try and understand it , in its simplest form with a simple example or application.

 

regards

[D H]

There are two incompleteness theorems. The first says that any sufficiently powerful mathematical system cannot be both consistent and complete. The second says that any sufficiently powerful that contains a proof of its own consistency and completeness is inconsistent. To understand these theorems you need to understand what is meant by "sufficiently powerful", "consistent", and "complete".

• "Sufficiently powerful". A simple mathematical system can be consistent and complete. Gödel's incompleteness theorems pertain only to systems that can reproduce the natural numbers and their properties: addition, multiplication, and induction. Remove induction from the Peano axioms and you still get an incomplete theory because the numbers are defined recursively. You have to get rid of induction and at least one of the concepts of zero, one, addition or multiplication to get a consistent, complete (and completely boring) theory.
   
   
  
• Consistent. While "a foolish consistency is the hobgoblin of small minds" (RWE), mathematicians are sticklers that a mathematical body of knowledge be consistent (or minimally, not provably inconsistent). A mathematical system is inconsistent if it contains a contradiction. Suppose some mathematical system allows a proof of some logical statement P made in that system and another proof of the logical negation of P. With these two contradictory statements at hand, one can prove any statement in that system is true. This is not good. Mathematical systems must be consistent or they are absolutely worthless.
   
   
  
• Complete. A mathematical system is complete if every statement that can be made in that system is either provably true or provably false. Completeness is a very "nice to have" feature. Unfortunately, consistency and completeness together are possible only for mathematical systems of rather limited capability (and hence limited use).

 

One of the first practical applications of the incompleteness theorems was that they put the kibosh on one of the key goals of early twentieth century mathematics. In 1900, the mathematician David Hilbert presented a list of 23 problems in a keynote speech at the International Congress of Mathematicians to kick off the new century. The second problem was to prove that the axioms of mathematics are consistent. A mathematical system can be proven to be consistent, but not within itself. The proof can only lie in a larger system.

 

Another practical application is Hilbert's first problem, to prove the continuum hypothesis. Gödel himself proved that the continuum hypothesis is consistent with the Zermelo-Fraenkel axioms (specifically, he showed that the negation of the continuum hypothesis is not provably true). Paul Cohen later proved that the negation of the continuum hypothesis is consistent with the Zermelo-Fraenkel axioms plus the axiom of choice. Both Gödel and Cohen assumed that the axioms are consistent.

[johan01]

I still cannot see the light.

 

is there a simple example of a " consistent" " complete" mathematical system.

 

if i throw some numbers and symbols randomly onto a peice of paper

am i making a statment that is false proving that the mathematical system is complete.

 

i think the definitions of "consistent" and "complete" are confusing for me wrt a mathematical system.

 

Q1

are binary numbers "consistent" -- i dont know, consistent with what?

 

Q2

are binary numbers "complete"-- i dont know, why would they not be?

Q3

are binary numbers considered as a mathematical system - i think so.

 

How does one come to an incompleteness theorem - how do you even prove such a thing?

[the tree]

I still cannot see the light.

That's okay, it's not easy.

 

Consistent is easy' date=' let's say I make a formal system of two symbols

 

[b']a[/b] and b - so any (ordered) string of as and bs is a statement in this system.

 

and two axioms.

 

i) a

ii) if ax then axb (x here represents anything - any string of as and bs)

 

So a, ab, abb, abbb, abbbbb are all provably true statements. It's definitely consistent because there's nothing to say when a statement is false.

 

It's not complete because b, bab and aa are neither true nor false.

 

It's certainly not sufficiently powerful because there is no way that it forms an analogue with the natural numbers.

 

Now if we introduce another couple of axioms.

 

iii) a must always be the first symbol in it's string.

iv) the first symbol in a string must be a.

 

Then our system is complete (and still consistent). Note that (iv) doesn't make (i) redundant, because without (i) you would only be able to prove statements to be false.

 

And now I cannot extend the system to create anything that looks like the natural numbers.

 

are binary numbers considered as a mathematical system - i think so.

No, binary is just a means for notation. Mathematical systems are a lot lower down in the workings of logic.

Edited December 17, 2008 by the tree

[johan01]

okay im beginning to get the picture, but why axiom (iii) is axiom (iv) not the same thing?

[npts2020]

okay im beginning to get the picture, but why axiom (iii) is axiom (iv) not the same thing?

 

My mathematics prowess is abyssmal but I will take a stab at this. Axiom iii only states that "a" will appear at the beginning of any string of numbers it is in. Axiom iv further implies there are no strings of numbers without an "a" in them by stating "a" is always at the beginning of any string.

[the tree]

Yes. Although there are no numbers involved, these are just meaningless strings of as and bs.

[bascule]

I still cannot see the light.

 

Godel's theorems work because they allow a statement about a formal logic system to be encoded into the language of the formal logic system itself. Godel was originally working within the formal logic system of Principia Mathematica, and in the language of that system managed to encode a statement which effectively says "This statement is unprovable."

 

It's similar to the Liar's paradox, which effectively says "This statement is false". However, in the case of the first Incompleteness Theorem Godel came up with numbers which represent statements in PM by mapping the logic language of PM to numbers (i.e. Godel Numbers).

 

By encoding the statements as numbers he was able to make a statement which was self-referential. So rather than the statement being simply "This statement is unprovable", it said "The statement represented by the Godel number of this statement is unprovable."

 

And in his second incompleteness theorem, Godel extended his proof that incompleteness stands for any system with the expressive power of basic arithmetic, not just for the logic language of Principia Mathematica.

 

Incompleteness stems from the expressive power of self-referential statements.

[bascule]

Slate has an awesome article on this, by the way:

 

http://www.slate.com/id/2114561/