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

[Cabbage]

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.

That should read:

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-0.

[Mathochist]

@Cabbage

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

This is misleading: CH plays a very different logical role than a Gödel sentence. CH is undecidable by ZFC because it is axiomatic with respect to ZFC. The Gödel sentence of a system F is undecidable by F, but is decidable within a metasystem.

That is, ZFC has two consistent extensions: ZFC plus CH and ZFC plus not-CH. A formal system F only has the one: F plus G(F). F plus G(F) is inconsistent.

[ultrafilter]

@Mathochist

F plus G(F) is inconsistent.

You sure about that? I thought I remembered reading somewhere that taking ~G(F) doesn’t necessarily produce an inconsistent system. Maybe [symbol]w[/symbol]-inconsistent, but that’s another beast entirely.

[Mathochist]

@ultrafilter

You sure about that? I thought I remembered reading somewhere that taking ~G(F) doesn’t necessarily produce an inconsistent system. Maybe [symbol]w[/symbol]-inconsistent, but that’s another beast entirely.

It’s subtle, really. Okay, F+ ~G(F) is not an inconsistent system itself, but it makes using that system to talk about F inconsistent. Still, vastly different from proving that a statement is axiomatic.

[tim314]

@ultrafilter

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:

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

Is this clear?

Yeah, I think that makes sense.

Except, in your example, wouldn’t the existence of [symbol]a[/symbol] only be given by the fixed point theorem if we knew that the mapping from a statement y to the statement “Anyone who can read y is overeducated” is continunous? (Although I’m not totally sure what I mean by continuous in this case. I guess I mean that the function that maps the number corresponding to a statement y to the number corresponding to the statement “Anyone who can read y is overeducated” is continuous.)

[tim314]

@Mathochist

F+ ~G(F) is not an inconsistent system itself, but it makes using that system to talk about F inconsistent.

OK, now you’ve lost me. If ~G(F), then G(F) has a proof in F, right? But if G(F) has a proof in F, it must have a proof in F+ ~G(F), right? So we can prove G(F) in F+ ~G(F). How is that not a contradiction?

[Mathochist]

@tim314

Yeah, I think that makes sense.

Except, in your example, wouldn’t the existence of [symbol]a[/symbol] only be given by the fixed point theorem if we knew that the mapping from a statement y to the statement “Anyone who can read y is overeducated” is continunous? (Although I’m not totally sure what I mean by continuous in this case. I guess I mean that the function that maps the number corresponding to a statement y to the number corresponding to the statement “Anyone who can read y is overeducated” is continuous.)

Wrong fixed-point theorem. Don’t think analysis; think formal logic or category theory (gee, is there anything in math that categories don’t make simpler? )

[Mathochist]

@tim314

OK, now you’ve lost me. If ~G(F), then G(F) has a proof in F, right? But if G(F) has a proof in F, it must have a proof in F+ ~G(F), right? So we can prove G(F) in F+ ~G(F). How is that not a contradiction?

This is partly where things even get fuzzy for me, so bring out your NaCl in 0.0648g doses.

Remember that G(F) isn’t “G(F) has a proof in F”, but rather some number-theoretic statement which we interpret at a high level as having that meaning. I’d have to go back and actually dig up the original papers to see what’s really going on and how this works.

Still, it’s all as maybe: either way my point is that it’s much different from a statement which is undecidable in the sense that CH is.