In simple terms, can someone explain Godel’s Uncertainty Theorem to me?

[LoganF]

Please note two things.

Number one; my training is not as a mathematician. Number two; I have been studying a book on mathematical logic.

Now although I can say that I have followed some parts of the book quite well (it says that specific segments can be understood equally well by non-specialists), it started to lose me when it introduced Kurt Godel’s incompleteness results.

Basically the book took me on a small ride of mathematical philosophy. Starting with Frege, who wanted to (as I understand it) expel intuitive appeals to arithmetic. He wanted to design a formal system for all mathematics that relied solely on the use of logic. It took me through Russel’s Paradox and a little bit of Formalism here and there. Then Hilbert.

Then it began explaining Godel’s Theorem. Godel proved that any consistent theory for arithmetic was incomplete; a sentence of the theory could be constructed which was neither provable nor refutable. Then it says that if the theory is not provable than this sentence is definitely true, so whoever recognized the theory as consistent must also recognize the sentence as true.

Okay, so I’m not following this very well. Now I know that sometimes for certain theories a lack of technical proficiency will expel any hopes of you learning or understanding that theory. However, there are still ways you can capture the essence of what is being said without having to know all the technical details. Like reading an explanatory book on relativity (e.g. The Elegant Universe by B.Greene).

I would like you to explain the essence of Godel’s theory to me. Namely, what it is and what exactly it signifies. Why does it have such a destructive effect on first- order theorems? I could not quite link the two together.

So if you could find a way to explain the significance of the theories in as simple a way as you can, I would be much obliged.
And could those of you familiar with Roger Penrose’s work/theories please explain how he uses it to prove that the capacity to understand arithmetical truths cannot be represented by any computer program?

I think I understand it in a basic way, since Penrose himself explains in The Emperors Mind how the human brain does not function in any way remotely similar to an algorithmic procedure. A (non-biological) computer system-based intelligence can only be contained in a formal system, which generates arithmetical truths. It is only consistent if the program is consistent. A human being who understands what is going on can recognize the truth of the undecidable sentence for that system, which the program cannot.

See, I only understand this stuff in patches, but I have no idea myself whether my understanding is consistent (no pun intended) with the rest of it.

[Giles]

Basically, what Godel proved was that if you have a consistent logical system which includes arithmetic, then you can always construct a proposition which can be neither proven nor dirpoved within the system. Therefore a consistent logical system must be incomplete. Of course, his method of contructing such a proposition might mean that it is extremely large, and extremely useless, so Godel’s theorem may have no real practical significance. However, it does prove that the old drem of comstructing a complete mathematical system is unattainable.

[Mathochist]

@LoganF

Now although I can say that I have followed some parts of the book quite well (it says that specific segments can be understood equally well by non-specialists), it started to lose me when it introduced Kurt Godel’s incompleteness results.

Which book?

Then it began explaining Godel’s Theorem. Godel proved that any consistent theory for arithmetic was incomplete; a sentence of the theory could be constructed which was neither provable nor refutable. Then it says that if the theory is not provable than this sentence is definitely true, so whoever recognized the theory as consistent must also recognize the sentence as true.

Okay, here’s the key: Gödel found a way of translating any formal system into arithmetic. That means that if the formal system includes arithmetic, then it can talk about itself.

For instance, the statement “Statement s is proven by proof p in formal system F” translates into some number, which is expressible in F itself, since F can talk about arithmetic. Let p be the number corresponding to a statement in F. Let q be the number of the statement “the statement with number p has no proof in formal system F”. Define f(p)=q. Now the tricky part is this: Gödel showed that the function f has a fixed point: a value g so that f(g)=g. Let’s see what that means.

g is the number of the statement “the statement with number g has no proof in formal system F”, or more succinctly “this statement has no proof in F”. Call this statement G.

Now either G has a proof in F or it doesn’t. If it does, then it must be true (within F), which means that it doesn’t have a proof, which is a contradiction. On the other hand, if there is no proof then our high-level interpretation of G (“this statement has no proof”) is true, but the system F isn’t strong enough to prove it’s true. Either F isn’t sufficiently strong to prove every statement in F that’s true or F contains a contradiction.

Dig?

And could those of you familiar with Roger Penrose’s work/theories please explain how he uses it to prove that the capacity to understand arithmetical truths cannot be represented by any computer program?

I think I understand it in a basic way, since Penrose himself explains in The Emperors Mind how the human brain does not function in any way remotely similar to an algorithmic procedure. A (non-biological) computer system-based intelligence can only be contained in a formal system, which generates arithmetical truths. It is only consistent if the program is consistent. A human being who understands what is going on can recognize the truth of the undecidable sentence for that system, which the program cannot.

This supposes that a human being can understand what’s going on. Rog is a great guy and does some fantastic work, but he’s a little muddled on his philosophy IMHO.

Let’s consider Gödel’s theorem again: how did we analyze it? From outside system F. Remember that statement G is really a horrendously complicated formal string that we interpret as making a statment about itself and F. Our analysis to determine that G is true (to avoid contradictions) was only possible from a vantage point outside the system itself.

Yes, we have a great ability to recognize “loopy” behavior (working on a problem and going around in circles without getting anywhere, like you would if you tried to prove G within F) and can “jump out of” many systems, but I can construct computers that are pretty good at recognizing some loopiness themselves. Just because our minds can jump out of many systems and look at them from above doesn’t mean we can do that for all formal systems, and in particular this hardly constitutes a proof at all that our minds are not themselves operating within some formal system which is powerful enough to talk about many other formal systems and analyze them from outside. If he’s trying to say that our brains can do this something which no computer can do as a proof that our brains are not computers, he’s really begged the question (and screwed the pooch) this time.

[FriendRob]

A great (and fun) way to learn about Goedel is to read Goedel, Escher, Bach, by Douglas Hofstadter. He doesn’t actually prove the undecidability theorem, but he gives you enough tools to see how it could be proved.

[aahala]

Logan, don’t feel bad. I’m still struggling how to type his name in so it will appear properly on the boards. I don’t have those two dots on my kepboard.

[wolf_meister]

aahala

Here’s a good chart for learning all those special characters:
http://www.1728.com/altchar.htm
ö is made with ALT 0246 and the uppercase character
Ö is made with ALT 0214

[Capt.Ridley_s_Shooting_Party]

Has any proposition been found that can be neither proven or disproven?

[Small_Clanger]

@FriendRob

A great (and fun) way to learn about Goedel is to read Goedel, Escher, Bach, by Douglas Hofstadter.

I second this. I recon that this book will raise your IQ by ten points if all you do is look at the the pictures. I usually have a bit of a mental block with maths but followed the reasoning in this book fine.

[ultrafilter]

@+MDI

Has any proposition been found that can be neither proven or disproven?

Yes. Greg Chaitin’s work in algorithmic information theory has led to several, and also leads to a deeper understanding of Gödel’s theorem.

In short, Chaitin showed that no suitably complex system contains enough information in its axioms to prove all statements that are true in that system. I want to say that his condition were the same as Gödel’s, but I’m not 100% sure on that.

He defined [symbol]w[/symbol] to be the probability that a program chosen at random halts on an input chosen at random*, and showed that the value of [symbol]w[/symbol] is not calculable. So any statement along the lines of “[symbol]w[/symbol] = p” for p in [0, 1] is undecidable.

*Of course, his notion of “at random” is well-defined.

@FriendRob

A great (and fun) way to learn about Goedel is to read Goedel, Escher, Bach, by Douglas Hofstadter. He doesn’t actually prove the undecidability theorem, but he gives you enough tools to see how it could be proved.

GEB’s an entertaining read, but it’s a mistake to walk away from it thinking that you actually know anything.

[Shalmanese]

Isn’t the Turing Halting Problem the classic example of a unprovable theorem?

Simply stated, it says that it’s impossible to construct an algorithm that, when fed in another algorithm, will say if it stops or not.

The proof that it’s impossible gets a bit invovled but thats the gist.

[ultrafilter]

@Shalmanese

Isn’t the Turing Halting Problem the classic example of a unprovable theorem?

Simply stated, it says that it’s impossible to construct an algorithm that, when fed in another algorithm, will say if it stops or not.

The proof that it’s impossible gets a bit invovled but thats the gist.

Not quite. Turing’s theorem on the halting problem is that there is no program that can decide, given a program and its input, whether the given program will halt on the given input. Because it’s been proven true, it’s not undecidable. Note also that an “unprovable theorem” is a contradiction in terms-- a statement is only a theorem if it has a proof.

However, the statement “Program P halts on input Q” is in general undecidable. In general, when you have a theory K with a non-random (in the Kolmogorov sense) axiom set, the theorems of K form a recursively-enumerable language. This is a pretty simple proof if you’re familiar with the proof of Gödel’s theorem.

[RevCo]

@aahala

Logan, don’t feel bad. I’m still struggling how to type his name in so it will appear properly on the boards. I don’t have those two dots on my kepboard.

Are you looking for an ASCII 148? ö? Make sure caps lock is on, hold down the ALT key, and press 148 on the numberpad. Works on all Windows OS’s. ASCII 128 to 168 are all international type characters - ¿I think? - good luck!

[ultrafilter]

The Windows character map is an invaluable utility. You can get to it by opening the Start Menu, hitting “Run”, and typing “charmap”.

[Chronos]

Has any proposition been found that can be neither proven or disproven?

Assuming that the standard construction of number theory is self-consistent, then Gödel’s string g (the one which loosely translates to “this statement cannot be proven”) is just such a proposition.

There are numerous other statements which are suspected to be undecideable, such as the Goldbach conjecture, but that one can’t be proven to be undecidable, either.

[ultrafilter]

@Chronos

Assuming that the standard construction of number theory is self-consistent, then Gödel’s string g (the one which loosely translates to “this statement cannot be proven”) is just such a proposition.

As I saw the proof, the lemmas that go into GIT do guarantee that such a sentence exists, but it’s not specified at any point. IIRC, the first constructive proof of undecidable sentences in number theory wasn’t given until the 1970s.

[tim314]

@ultrafilter

As I saw the proof, the lemmas that go into GIT do guarantee that such a sentence exists, but it’s not specified at any point. IIRC, the first constructive proof of undecidable sentences in number theory wasn’t given until the 1970s.

I’m not sure I understand precisely what you mean when you say “exists” but “is not specified.” Following along with what Mathochist said above, doesn’t the statement have to be “This statement has no proof”? Is that not a specification?

I mean, if g satisfies f(g) = g, and f(x) is “Statement x has no proof”, then how could g be anything but “This statement has no proof”? But maybe I’m misunderstanding how Gödel’s theorem works – I’m not really familiar with it. Or, maybe I’m misunderstanding what you mean by “is not specified.”

At any rate, further explanation would be much appreciated.

[ultrafilter]

@tim314

I’m not sure I understand precisely what you mean when you say “exists” but “is not specified.” Following along with what Mathochist said above, doesn’t the statement have to be “This statement has no proof”? Is that not a specification?

Mathochist is simplifying his explanation. Trying to keep some of this stuff straight and explain it clearly is enough to try the patience of a saint. What the theorem actually says is that there is some sentence G such that G is true iff G has no proof. But that’s not what G actually says, because self-reference is disallowed in first-order predicate logic.

I’ll use my current signature as an example:

Let [symbol]a[/symbol] be the sentence such that [symbol]a[/symbol] [symbol]«[/symbol] ([symbol]"[/symbol]x)(R(x, |[symbol]a[/symbol]|) [symbol]®[/symbol] O(x)), where R(x, y) is interpreted as “x can read the sentence with Gödel number y” and O(x) is interpreted as “x is overeducated”. The existence of [symbol]a[/symbol] is guaranteed by the fixed point theorem.

So there is a sentence [symbol]a[/symbol] which satisfies that statement, but [symbol]a[/symbol] could say anything.

Is this clear?

[Mathochist]

@Chronos

Assuming that the standard construction of number theory is self-consistent, then Gödel’s string g (the one which loosely translates to “this statement cannot be proven”) is just such a proposition.

There are numerous other statements which are suspected to be undecideable, such as the Goldbach conjecture, but that one can’t be proven to be undecidable, either.

It should be emphasized that the Gödel statement of a formal system cannot itself be proven undecidable within the system itself.

[astro]

Gödel’s incompleteness theorem - From Wikipedia, the free encyclopedia.

In mathematical logic, Gödel’s incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. Somewhat simplified, the first theorem states:

In any consistent formalization of mathematics that is sufficiently strong to axiomatize the natural numbers – that is, sufficiently strong to define the operations that collectively define the natural numbers – one can construct a statement that can be neither proved nor disproved within that system.
This theorem is one of the most famous outside of mathematics, and one of the most misunderstood. It is a theorem in formal logic, and as such is easy to misinterpret. There are many statements that sound similar to Gödel’s first incompleteness theorem, but are in fact not true. These are discussed in Misconceptions about Gödel’s theorems.

Gödel’s second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

No consistent system can be used to prove its own consistency.
This result was devastating to a philosophical approach to mathematics known as Hilbert’s program. David Hilbert proposed that the consistency of more complicated systems, such as real analysis, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic arithmetic. Gödel’s second incompleteness theorem shows that basic arithmetic cannot be used to prove its own consistency, so it certainly cannot be used to prove the consistency of anything stronger.

Misconceptions about Gödel’s theorems
Since Gödel’s first incompleteness theorem is so famous, it has given rise to many misconceptions. They are summarized here:

The theorem does not imply that every interesting axiom system is incomplete. For example, Euclidean geometry can be axiomatized so that it is a complete system. (In fact, Euclid’s original axioms are pretty close to being a complete axiomatization. The missing axioms express properties that seem so obvious that it took the emergence of the idea of a formal proof before their absence was noticed.)
The theorem only applies to systems that allow you to define the natural numbers as a set. It is not sufficient that the system contain the natural numbers. You must also be able to express the concept “x is a natural number” using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example, both the real numbers and complex numbers have complete axiomatizations.

[Cabbage]

Perhaps the best known example of an undecidable proposition is the continuum hypothesis.

The axiom of choice implies that every set has a cardinality, which is basically the “size” of the set. The cardinality of a finite set is simply the number of elements in it. The cardinality of the natural numbers is the smallest transfinite cardinal, generally called aleph-0. The next smallest cardinalities are alehp-1, aleph-2, and so on (indexed by the ordinals).

It’s known that the cardinality of the real numbers is strictly greater than aleph-0. Cantor, who first developed the notion of cardinality, hypothesized the cardinality of the reals was aleph-1, the next cardinal above aleph-1. He was never able to prove this, but his hypothesis came to be known as the Continuum Hypothesis (CH).

In 1900, David Hilbert proposed what he considered to be the biggest unsolved mathematical problems of the time. CH was number one on the list. Since so much mathematics is done in the real numbers, the cardinality of that set is of fundamental interest.

When Goedel first published his incompleteness theorem, many expected it was to be nothing more than an oddity. Sure, undecidable propositions exist, but surely nothing of interest would be found to be undecidable.

In 1940, Goedel himself proved that CH was consistent with the standard (ZFC) axioms of set theory. Maybe CH was true after all?

In 1963, Paul Cohen proved the negation of CH was consistent with ZFC set theory, as well.

And so a fundamentally important problem was found to be undecidable in ZFC set theory.

Many set theorists now believe that CH is probably false; the cardinality of the reals could be huge, much larger than aleph-0. To quote Cohen himself,

A point of view which the author [Cohen] feels may eventually come to be accepted is that CH is obviously false. The main reason one accepts the Axiom of Infinity is probably that we feel it absurd to think that the process of adding only one set at a time can exhaust the entire universe. Similarly with the higher axioms of infinity. Now aleph_1 is the set of countable ordinals and this is merely a special and the simplest way of generating a higher cardinal. The set C [the continuum] is, in contrast, generated by a totally new and more powerful principle, namely the Power Set Axiom. It is unreasonable to expect that any description of a larger cardinal which attempts to build up that cardinal from ideas deriving from the Replacement Axiom can ever reach C. Thus C is greater than aleph_n, aleph_omega, aleph_a , where a = aleph_omega, etc. This point of view regards C as an incredibly rich set given to us by one bold new axiom, which can never be approached by any piecemeal process of construction. Perhaps later generations will see the problem more clearly and express themselves more eloquently.