Godel's Incompleteness Theorem

[gib65]

Can somebody please explain to me, in plain English, what Godel's Incompleteness Theorem is. I read it on wikipedia and I couldn't understand a word of it.

[matt grime]

Do you understand what an axiomatic system is? It is simply a set of (not inconsistent) rules.

 

A model for the axioms is a mathematical gadget in which the rules are true. There are many such ways of realizing the rules.

 

If the list of rules to satisfy is finite, and if it requires you to have a copy of the natural numbers in any model of it, then godel states that there are statements that are true in the model but cannot be deduced from the rules alone, and that there will be some other model of the rules in which this statement is false.

 

Here's a psuedo example.

 

Let R be the axioms for Groups, a model of R is just a group (note this doens't force us to define the natural numbres as a subset of G, but that is not important).

 

Suppose that the model is the integers, then the statement "G is abelian" is true in that model. Yet in the model "invertible 2x2 matrices" the statement is false. Thus the statement "G is abelian" is independent of the axioms.

[gib65]

Do you understand what an axiomatic system is? It is simply a set of (not inconsistent) rules.

 

A model for the axioms is a mathematical gadget in which the rules are true. There are many such ways of realizing the rules.

 

If the list of rules to satisfy is finite' date=' and if it requires you to have a copy of the natural numbers in any model of it, then godel states that there are statements that are true in the model but cannot be deduced from the rules alone, and that there will be some other model of the rules in which this statement is false.

 

Here's a psuedo example.

 

Let R be the axioms for Groups, a model of R is just a group (note this doens't force us to define the natural numbres as a subset of G, but that is not important).

 

Suppose that the model is the integers, then the statement "G is abelian" is true in that model. Yet in the model "invertible 2x2 matrices" the statement is false. Thus the statement "G is abelian" is independent of the axioms.[/quote']

 

I think I understand. Is it similar to the idea that certain things can be said about some instances of some class, but not other instances? For example, if you take the class "animals" and you consider an instance of "mammals", then you can make statements about this instance (like no members of this instance lay eggs) that you would not be able to make about other instances like "reptiles" (which do lay eggs).

 

I understand this is oversimplified, and I'm sure there's more to Godel's Incompleteness Theorem than this, but am I on the right track?

[matt grime]

I don't think you're on the right track, but that's because you are needlessly trying to reason by analogy. if you're not a mathematician, fine, but this is a theorem about/in mathematics and only applies to mathematics. I don't like analogies: there is no such thing as a good one.

 

Perhaps if you phrased it as "forms a class of animals" and then took as models "mammals" and "reptiles" it might look better. There are things that can be said about one but not the other, call one of these a phenomenon. Thus merely being a class of animals is not sufficient to force that phenomenon, nor its negation to be automatically satisfied.

[cosine]

I don't think you're on the right track' date=' but that's because you are needlessly trying to reason by analogy. if you're not a mathematician, fine, but this is a theorem about/in mathematics and only applies to mathematics. I don't like analogies: there is no such thing as a good one.

 

Perhaps if you phrased it as "forms a class of animals" and then took as models "mammals" and "reptiles" it might look better. There are things that can be said about one but not the other, call one of these a phenomenon. Thus merely being a class of animals is not sufficient to force that phenomenon, nor its negation to be automatically satisfied.[/quote']

 

1st Post:

It applies in a sense to soley mathematics in that it applies when a system contains arithmetic. But aren't there plenty of systems in our world today that usilize arithmetic, and would thus have this theorem applied to them?

 

2nd post:

Also, Goedel's theorem is stronger in that it says that you can prove a system is complete iff it is inconsistent.

[gib65]

I haven't replied to this thread in a while, but I'm back at it because I just heard a certain translation of Godel's Incompleteness Theorem that clarifies what I don't understand about it - not that I now understand, but that I now understand what I don't understand (i.e. I now know more precisely what the question I should ask is).

 

The translation goes "Godel proved that you could have a formal system that yeilds true statements that cannot be proven within the confines of that system."

 

So then what I wonder is how could it not be provable by the system if it is yeilded by the system? I mean, doesn't the fact that it was yeilded by the system mean it was proven by the system?

 

For example, if my system consisted of the two statements:

 

If A then B.

If B then C.

 

then the statement "If A then C" would be yeilded by the system because it is proven by the system. There must be something wrong with my understanding.

[matt grime]

The statements are true in some larger model (and also false in another larger model), if this is the thing I'm thinking of. The notion of 'constructed' but not provable simply means that the statement that cannot be proven is made up from statements (constructed) in the system. (if it were made of statements not in the system it would be a silly result!)

 

the statement is a little like the liar's paradox: this theorem is not provable from the axioms of the system.

 

or at least that's what it is supposedly like. by the liar's paradox, if that is a theorem it is not a theorem, and if it is not a theorem it is a theorem...