Could someone explain Godel’s Incompleteness paradox to me? As I understand it, the paradox goes something like this:

There are two kinds of sets: those that contain themselves as subsets (Type A), and those that don’t (Type B). Now make a set of all type B sets. This set could not contain its self, since it is composed of type B sets and if it contained its self as a subset it would not be type B. But if it doesn’t contain its self, it would also HAVE to contain its self. A paradox seems to emerge.

Apparently Godel was so bothered by this that he gave up on mathematics. I don’t see what the big deal is. To me, the ‘paradox’ only seems to prove that you can’t have a set of all sets that don’t contain themselves. But apparently I’m missing something, because people who are well-versed in set theory always make a big deal out of it. Am I missing something? Or do I just not understand it properly?

Thanks.

Actually, that paradox was first mentioned by Bertrand Russell.

Godel did something a little different. He proved mathematically that any system of mathematics complex enough to contain basic arithmetic must always be either inconsistent or incomplete.

In this context, "inconsistent" means you would be able to prove two contradictory statements using the system - not a good thing for a mathematical system. "Incomplete", on the other hand, means that there are true mathematical statements which are impossible to prove using the system.

Since this theory applies to all mathematics, it means that there will always be true statements which we cannot prove using our mathematics. There can never by a complete system of mathematics which allows all true mathematical statements to be derived.

I think that's pretty deep.

Thanks for the information! Apparently I had my paradox names mixed up.

I have been trying to resist (honest) but I cant resist a rant.

Start of RANT.

Godel showed that no mathematical system can be complete. No argument there. But I do take exception to the conclusions people, the press even Penrose argue from that.

If you look at Goedels proof you can show that the system can ALWAYS be extended to resolve any incompleteness. Not that the extension is always practical.

One argument that anoys me goes like this.

Goedels proof, no single system can be complete - true

Intelligence can solve things that cant be done mathematically. - True

There for inteligence can not be logical - False.

All the first two means is that we have not yet got a big enough system or enough different mathematcal systems, to solve the problems intelligence can solve. No big deal.

End of Rant.

Another side bar here on understanding Goedels proof. Goedal imposed the contraint that his proof be expressed in the same math system as the problem. If we relax this rule it gets easier.

Consider the Logic stuff

B = TRUE
A = B

No paradox can prove A is true.


A = A

Not paradox but If a is true then A is True and vice versa - an undecidable proposition.

A = Not A

If A is true then A is False and vixce versa. The system contains a paradox (contradiction).


Expending a bit of brain power on the above will show that the second problem has a self referential aspect. Not that this is not sufficient on its own as

A = B and FALSE
B = A and TRUE

is non paradoxical and still self referential and

A = B and TRUE
B = A and TRUE

is undecidable.

The third problem includes the concept of negation. This plus self referential allows problems to be outside the logic system ability to solve. Effectively negation or not allows a kind of Not in the system to creep in the back door.

Logic works on the set { TRUE, FALSE } The Not and self reference allows problems that have solutions that are outside this set such as Neither or Both. But this is still incomplete as if you add these you find you need to extend it to include new entries like "TRUE and BOTH" ....

For an example of one way to extend logic to solve it. Add a time/State to it.

A = Not A

Becomes

A(n+1) = Not A(n)

Assume at T = 0 A is false. Then at T= 1 it is true at T = 2 it is false. Ie at each period it changes from True to False. The logic used before becomes a subset of this new logic where the value of each variable is (becomes) the same for all T.

If wired A = Not A with electronic logic you would have an Oscillator. You might also recognise the previous two problems as being a latch (flipflop) in hardware jargon.

This statment is false. Is it not ?

<i>If you look at Goedels proof you can show that the system can ALWAYS be extended to resolve any incompleteness.</i>

Yes, but then you have a new system which is also incomplete.

Originally posted by James R
<i>If you look at Goedels proof you can show that the system can ALWAYS be extended to resolve any incompleteness.</i>

Yes, but then you have a new system which is also incomplete.

True!

For a very good presentation of Godel see: http://www.cs.toronto.edu/~hehner/God.pdf
Start reading at page 5.


This presentation uses a more natural coding of theorems than Godel did (strings vs numbers).

First incompletenesstheorem: if consistent then incomplete
Second incompleteness theorem: adding unprovable statements as axioms does nog lead to a complete system.


Greetings,


Han.

Originally posted by Nasor
There are two kinds of sets: those that contain themselves as subsets (Type A), ...


Hold it right there! How can a set possibly contain itself?? This is infinite regression, is it not? That in itself is a paradox and an impossibility, mathematically like dividing by 0. Sure, you can derive other paradoxes from this paradox, but what's the point?

I think what this "proves" is that no set can possibly contain itself because if it did then its cardinality could not be determined and I thought cardinality was a key property of sets. This restriction should even be part of a definition of a set. That's the only thing that really "follows".

As for Godel's incompleteness, I could use some help myself. If a mathematical statement cannot be proven within a given framework, then how could it possibly be regarded as true (James R)? Are not truth and derivation idempotent? If it can't be proven then it could at best be viewed as a conjecture or a heuristic (e.g. "God exists"), and at worst as meaningless gibberish (e.g. "this sentence is false".) Right?

As far as I understand, "incompleteness" consists of the result that using any system of formalism you can compose statements of indeterminate validity or even utter gibberish. :eek: Well, by golly, whoopty doo. :bugeye:

overdoze,

<i>If a mathematical statement cannot be proven within a given framework, then how could it possibly be regarded as true (James R)? Are not truth and derivation idempotent?</i>

We're talking about statements which make perfect sense in the system - i.e. the system allows the statements to be expressed - but which the system cannot be used to generate a proof or a disproof of the statement.

The Godel proof generates a mathematical statement in a formal system which essentially says (in English) "The system cannot prove that this statement is true."

Consider the statement. Either it is true or false. If it is true, then the system cannot prove it, and therefore we conclude that the system is incomplete. If, other the other hand, it is false, then the system must be inconsistent, since the system could prove that the statement was true, but the statement asserts the opposite.

Originally posted by James R
The Godel proof generates a mathematical statement in a formal system which essentially says (in English) "The system cannot prove that this statement is true."

Consider the statement. Either it is true or false. If it is true, then the system cannot prove it, and therefore we conclude that the system is incomplete. If, other the other hand, it is false, then the system must be inconsistent, since the system could prove that the statement was true, but the statement asserts the opposite.

Right, except I cannot for the life of me characterise such as statement as either true or false. I would rather call it meaningless. It lacks an aboutness characteristic of the more typical true or false statements. For example, the statement "P = Q" relates two distinct things. The types of statements Godel comes up with are ultimately self-referential so they can't tell you anything about anything.

What does it mean, "this statement is true"? What is it that is claimed to be true, actually? How can "this statement" be either true or false, without actually making any claim about anything? I'd say the use of "this statement" in the sentence is a logical inconsistency, because there is, in fact, no statement being made. It's equivalent of saying "this sequence of symbols is true". Not applicable. Meaningless.

You seem to claim that such 'statements' "make sense" just because they can be composed using the system. However, I fail to see the necessity of such an implication. Just because a statement can be formed using a formal system, doesn't have to mean that the statement must make sense. Linguistically, a statement can be well-formed but carry 0 new information, or self-contradictory information, or inconsistent assorted information. Take XML as an example. Just because a piece of XML is well-formed doesn't necessarily mean it is valid.

You (and all the various logicians) seem to equate "makes sense" with "well-formed". I disagree.

Found at http://mail.gnu.org/pipermail/gnu-misc-discuss/1996-August.txt:

["The system cannot prove that this statement is true."] is not valid logic. It implies the existence of only two states, by omission. The book "Fuzzy Logic" calls this an "excluded middle," and it is on the same order as the yes/no question "have you stopped beating your wife?"

The fallback position is a fuzzy system: it is a system which claims that a contradiction of one element of a set of elements does not necessarily therefore contradict other elements of the set.

Can someone help me resolve a problem I am having understanding godel's theorem? Thanks:
tinku99: theorems are true if they can be proved from axioms
tinku99: non theorems are false
tinku99: mathematics is trying to figure out how to fit all statements into either theorems or non-theorems
tinku99: so its easy to say for a non-theorme that I am provable "spell out a proof"
tinku99: but its not that easy to say "I am not provable"
tinku99: 3+3=7 does not mean 7 is not provable
tinku99: 7 might still be provable...
tinku99: 2+5=7
Vinuipe: i dont understand his theroem enough to be of help..
tinku99: now even if 7 represented a proof such as 1+4=5
tinku99: or even if 7 represented a statmetn 1+3=5
tinku99: it doesn't say I am not provable
tinku99: it just says I am not a proof
tinku99: which doesn't mean there can't be a number like:
3400+ 4399= 7
tinku99: my point is you can't say I am not provable... that statement is not defined in number theory
tinku99: the other problem is that meta number theory statements are not theorems
tinku99: they may be non-theorems
tinku99: and arithmetic on non-theorems is not defined
tinku99: so you can't do this loopy deal of representing a

Overdoze - you made a point about Goedel statements that also still bothers me. When written in English (as in 'this statement cannot be proved true... etc ') Goedel's statement appears entirely self-referential and rather trivial. However I am informed that in its proper mathematical form this statement (as formulated approriate to the system being used) is actually not self-referential but makes a meaningful statement using subject and object.

Unfortunately as a non-mathematician I cannot delve any further. JAMES - can you comment on this? I suppose my question is whether the popular form of a Goedel sentence (as above) is really a good representation of its mathematical form or just a poor approximation that everyone uses for convenience.

Most days I believe Goedel's theorums to be the most important pieces of theoretical knowledge we have. But other days I find them trivial (for reasons Overdoze outlines - and even after much reading). This is very disconcerting.

canute-

you should really stop writing "theorum". theorem. please.

Damn. Thanks. I should have seen that. Please point out all such errors as soon as you see them. Any comment on the question?

How can "this statement" be either true or false, without actually making any claim about anything? (overdoze)

holy cow!
well? how can it?

ps: how cool! p&m's very own spellcheck!

The fact is that we know nothing. For no thing is truth, and it cannot be proven false, thus knowledge is consequently irrelevant.

what did i tell you about projecting? "we" is not me

Haha, please. "We", is anyone who assumed(s) that logic is absolute and irrefutable.

Whatever you "told" me means nothing, for I will take heed only to suggestion, never command. That is what is wrong with society as a whole, not enough people think like me....haha.

However, if you believe that you are in fact exclusive of the "we" that I have defined above, then you are still in agreement with me.

We know nothing as you know nothing..., and a great man once said...

"Denial is the most predictable of all human responses."

damn those quotes are annoying

;)

Whatever you "told" me means nothing, for I will take heed only to suggestion, never command.

does "told" have to imply command? is it not a neutral term?
cackle away. wallow in your professed ignorance. your loss not mine.

Doesn't Godel's Incompleteness Theorem also apply to Godel's Incompleteness Theorem? Meaning that this theorem is either incomplete or inconsistant, by it's own rules?

As a side note: I went to look at the Godel paper, and am almost completely lost. I only recognize half of the symbols, and can't even find the rest in my book on logic.

Originally posted by Persol
Doesn't Godel's Incompleteness Theorem also apply to Godel's Incompleteness Theorem? Meaning that this theorem is either incomplete or inconsistant, by it's own rules?
Never thought of that. But not quite. It shows that his theorems are not completely provable within the system within which he completely proved them. Which is odd.

Doesn't Godel's Incompleteness Theorem also apply to Godel's Incompleteness Theorem? Meaning that this theorem is either incomplete or inconsistant, by it's own rules?

As a side note: I went to look at the Godel paper, and am almost completely lost. I only recognize half of the symbols, and can't even find the rest in my book on logic..

This makes no sense. Goedel said nothing about a THEOREM being incomplete or inconsistent. In fact, it makes no sense to talk about a theorem BEING incomplete or inconsistent.

As has been stated repeatedly, a SET OF AXIOMS is "inconsistent" if it is possible to probe a statement AND its negation. A set of axioms is "incomplete" if there exist some statement such that NEITHER it nor its negation can be proved from those axioms.

What Goedel said was that any set of axioms, large enough to encompass the natural numbers, must be either incomplete or inconsistent.

He also said that it is impossible to prove that a set of axioms was consistent using only those axioms. That says nothing about the ability to prove a specific theorem.

(Of course, if a set of axioms is INCONSISTENT, then it is possible to prove that using only those axioms!)

True but a bit nitpicky. The system within which G proved his theorems is either incomplete or inconsistent. This seems to mean that the theorems have the same rather dodgy foundation as the rest of our knowledge. In this case they cannot be proved completely true as the axioms from which they are derived cannot be proved completely true.

Another post that makes no sense.

It is, by definition, impossible to "prove" that axioms are true or false. I have commented before that it would be much better to use the terms "valid" and "invalid" for logical derivations rather than "true" and "false".

What Goedel showed was that IF the axioms for number theory are consistent, then they cannot be complete. Obviously, if the axioms he used for that proof (the axioms for number theory) are not consistent then his theorem is trivially true! On the other hand, if the axioms are consistent, then his proof is valid.

This seems to repeat what I said.

On Russell's paradox, the natural numbers are abstractions on the cardinalities of the finite sets, so set theory is implicitly the foundation of all mathematics. At the time, the treatment of set theory allowed the construction of the contradictory set in question, so it was possible that a flaw at the very foundation of mathematics had been discovered. Thankfully, a more rigorous and axiomatic treatment of sets has resolved this. Russell's paradox arose in a discourse between Bertrand Russell and Georg Cantor (a set theorist who eventually quit maths due to the backlash over some quite brilliant results).