Hacker News Reader

Comment by andrewcooke | Hacker News Reader

i'm not a mathematician, but his final point about the continuum hypothesis seemed odd to me. the CH is "outside" ZF, but that just means (afaik) that it contains some extra "information" that is not in ZF. adding it to ZF doesn't force any kind of contradiction, in the way that adding "this system is consistent" would. so CH is (just) an example of an independent axiom - it doesn't illuminate what is so weird about the completeness theorem.

(mathematicians: is that right?)

View on HN

His example is to do with the first theorem. There are two incompleteness theorems. The one most people think of when they hear Godel is the second even though the first is key. The first one has to do with decidability - for any given statement from a theory is it algorithmically verifiable given the axioms of the theory? If you can encode the natural numbers with its axioms and pose <handwave>certain relations</handwave> with that encoding then no. This ties Godel's work to Turing. http://www.scottaaronson.com/democritus/lec3.html

Here is a list of undecidable statements in ZFC: http://en.wikipedia.org/wiki/List_of_statements_undecidable_...

I think the CH was used just to provide an example of an undecidable statement, not actually demonstrate something weird about the incompleteness theorem. Since the CH cannot be proven to be true or false within ZF (or ZFC), then you are correct, appending it would just provide an addition axiom.

So it is a weird example, since it NOT an example of a statement that is undecidable in every model.

Well, the CH IS an example of a statement that is undecidable in ZF. Once you include is as an axiom, you essentially bypass the need to use ZF to justify it (or prove it). So, just because you are able to include the CH as an axiom, doesn't mean it is not an example of a undecidable statement within a given set of axioms. Does that make sense?

This is not a weird example for that reason. For a given model, every statement is either true or false. Godel's Completeness Theorem says that a first-order theory is consistent if and only if it is true in some model. Therefore, for every undecidable statement there will be a model where it is true and a model where it is false.

These models can look very strange. For example, if ZF is consistent, then by the Second Incompleteness Theorem so is ZF + "ZF is inconsistent". By the Completeness Theorem, a model for this theory must exist. In this model ZF is inconsistent, so there is a 'proof' of a contradiction from the axioms of ZF. However, since we have assumed the consistency of ZF, such a 'proof' must necessarily involve nonstandard integers.

Yeah that was a tangent. The author got a bit overexcitrd and overshot.

Also not the OP's reply (paraphrased): "Thanks, but I wasn't interested in the understanding logic or math. I am thinking more along the lines of [metaphysical gobbledygook]. What can you say about that? "

The situation with Goedel sentence (let's call it G) is actually not very different. As neither G nor negation of G is provable, you could also say that it contains extra information, and add negation of G as a new axiom to PA, just like you could add CH to ZF.

If you do that, you could wonder what your new arithmetic looks like. This is actually very interesting question. Since "not G" says basically "it's not true that there's no proof of me", or, more specifically, "it's not true that there's no number that represents the proof of me", it's clear that "not G" asserts the existence of a certain "natural" number being the proof of G, which is not one of the natural numbers we know (since no "regular" natural number represents the proof of G). In our new universe there are "natural" numbers that you cannot reach by counting. Because of that, one can construct many different nonequivalent "implementations" (models) of PA + not G, which are necessarily different than the standard implementation of artihmetic we know (1, 2 = S(1), 3 = S(S(1)), ..., n = S(S(...S(1)...)), with + and *).

What is interesting about incompleteness theorem is that no matter if we add arbitrarily large number of axioms to PA, or even infinite number of axioms generated by computer program we write, the resulting system will still be incomplete, and each will have its own (many of them, actually) Goedel sentence.

Reply on news.ycombinator.com