Gödel -- What Does this Mean (DrMatrix)

In this thread:

http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=185649

DrMatrix said:

What does that mean? If it is consistent, it is not consistent?

http://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html

[Aside]

“A “complete” system will generate all true statements.
A “consistent” one will not generate contradictions.”
-Michael Macrone

Anyways, what an ironic post.

[/Aside]

An inconsistent system can prove any statement, whether the statement is true or false. So, if a system in not consistent, it can prove that it is consistent. What Gödel showed is that if system can prove that it is consistent (by demonstrating that say 1=0 has no proof) then it can prove any statement and is therefore not consistent.

He also showed that number theory is incomplete. That is, it cannot prove every true statement. He did this by showing that it is possible to construct a statement that asserts that it has no proof. If number theory is consistent, then this statement cannot have a proof and is therefore obviously true, but number theory cannot produce a proof.

It can take a while to wrap your head around these two results. I recommend Gödel, Escher, Bach, an Eternal Golden Braid by Douglas Hofstadter.

GEB is a great book!

Thanks. I will check out the book, but it is probably beyond me.

You’d be surprised how much of it is accessible to the mathematically challenged :slight_smile:

Its an excellent book. Don’t worry - its pretty understandable. And the few parts that aren’t you can generally skip over without losing anything :slight_smile:
Anyway, I guess I understood wrong because I thought that that premise was a formal system cannot be consistent AND complete. It can be one or the other, but not both.

His Metamagical Themas is good stuff, too.

GEB is a good book, but it’s a layman’s treatment. You can get a rough idea of the things he’s talking about, but to do any work with them, you need a more specific treatment.

There are some systems that can be proven to be consistent, but they are not complex enough to be interesting.

Once you are able, within a system, to prove two things that are inconsistent, then–logically–you can prove anything. So, for inconsistent systems, you can indeed “prove” that they are consistent.

>> There are some systems that can be proven to be consistent, but they are not complex enough to be interesting.

Define “interesting”.

I used to know this one girl who was quite simple and yet very interesting. At least parts of her were very interesting. To me at least.

“Interesting” means powerful enough to prove the common known results in Number Theory (or Math in general). Quantified Boolean Algebra is complete and consistent, but is too weak to express many standard theorems in Number Theory.

(BTW, I strongly recommend against reading GEB. It’s horribly long winded and boring. A better writer could have done a better job in a 100 pages. An awful, awful book. His Scientifc American column didn’t last at all long for the same reason.)