Godel's Theorem: Discuss and Explain

[drag]

Greetings !

I bet the "2" got the attention of all
the people this is mainly intended for...

But, it's not what you might think, it's
just that I have a similar thread (without
the "2" ) in the Philosophy Forum and
I invite you people, aspecialy the experts,
who may've not visited it for a while(like
Hurkyl for example) to make your comments
and ASPECIALY explanations there.

Of course, in order for this thread not to
be wasted as a mere announcement I'd like to
hear your opinions here too. Maybe a more
technical and expert duscussion can start here.
(In which my humble role will probably only be
to read the words of wisdom of other members.)

Thanks !

Live long and prosper.

 

[damgo]

Which one? He has a Completeness Theorem and two Incompleteness Theorems?

 

[drag]

Originally posted by damgo
Which one? He has a Completeness Theorem
and two Incompleteness Theorems?

Really ?!
Let's hear'em !
(Completeness Theorem ? Sounds fascinating... )

 

[damgo]

Defs: A "theory" is the set of sentences derivable from some set of (not necessarily finite) axioms. For example, the theory of arithmetic contains the basic axioms of addition, multiplication, etc, and all sentences provable from them. A "model" is a particular 'real' mathematical entity or structure, such as the normal natural numbers. The natural numbers are a model of the theory of arithmetic; but there are other models (nonstandard natural numbers.)

Godel's completeness theorem states that a sentence S in part of some theory T if and only if S is true in all models of T. So, if we can't prove some statement S from our axioms, there exists a mathematical structure modelling the axioms where S is true, and a different one where "not S" is true.

This leads to the question, well, can we pick our axioms/theory cleverly enough so that we can always prove either "S" or "not S"? In other words, make it so that we are fully specifying the model we want and don't leave any questions undecided? Godel's Incompleteness Theorem says that under certain conditions, no. There is always some statement that can't be proven or disproven.

The conditions require that the set of axioms be reasonable, and the theory be strong enough -- it has to include 'Q', a subset of the axioms of arithmetic.

---

Two examples of this sort of thing are the continuum hypothesis and the axiom of choice. Neither are provably true nor false in standard ZF set theory. We could choose to add them as axioms, of course, and get the theory ZFC+CH; but Godel's Incompleteness theorem assures us that we can't ever get rid of these types of undecidable statements. No matter how many you add as axioms, there will always be more.

 

[drag]

Originally posted by damgo
The conditions require that the set of axioms
be reasonable, and the theory be strong enough
-- it has to include 'Q', a subset of the
axioms of arithmetic.

Could you elaborate on those 2 points a bit,
please, damgo ?
Does "reasonable" mean that the axioms mustn't
conflict with each other ?

Thanks !

 

[Alex]

Thats especial :)

 

[damgo]

Actually, that whole blurb I gave assumes the theory is consistent, ie the axioms don't conflict with one another. If your axioms are inconsistent, then you can prove every statement and the theory is worthless.

OK, 'Q' is just a slightly watered-down version of arithmetic: you have the number 0, a successor function, addition, multiplication, and most but not all (eg there is no commutativity of addition) of the axioms of arithmetic. Oftentimes people just say Godel's IT applies to any theory that includes arithmetic, which is true, but technically you need slighly less than all of arithmetic.

The reason for this condition is that the proof of Godel's IT makes use of a "Godel numbering," a way of assigning a unique natural number to any sentence in the theory. If our theory can handle enough of arithmetic, then we can manipulate Godel numbers and use them as a way to 'talk' about the theory inside the theory. For example, there is a formal logical sentence that defines (all the sentences that are true of their own Godel number.)

---

The 'reasonable' condition is one of those technical ones that are confusing to formally explain but rather intuitive. We could 'go through' all possible sentences S, decide which of S or (not S) we want to be true (when consistency does not choose for us), and imagine adding those to our axioms. Then we would have an infinite set of axioms -- in fact our axioms would include every true statement (ie everything in the theory) -- and the theory would be complete, Godel's IT would not apply.

But obviously this is dumb. Axioms are supposed to be something we explicitly specify, not that we pull in via cheap nonconstructive definitions. The formal condition usually used is that the set of axioms be 'recursively enumerable'; this corresponds to the intuitive notion of being able to explicitly define them through some function, computer program, method, etc. IIRC there are various strengthenings and versions of the incompleteness theorem that use slightly different conditions here -- sigma-consistency comes to mind -- but I don't remember them well, and anyways, that's a rather tangential point.