Hacker News Reader

Comment by ionfish | Hacker News Reader

"It's like an ill-designed jigsaw puzzle. No matter how you arrange the pieces, you'll always end up with some that won't fit in the end."

I really don't understand this analogy. The first incompleteness theorem shows that there are statements true of the natural numbers which aren't provable from any sufficiently strong recursive theory. It's more like Th(N) (the set of statements true of the natural numbers) being a jigsaw puzzle from which many pieces will always be missing if you start with a recursive set of pieces and try to lay down only those pieces which a provable from your initial set. Nothing "won't fit": there aren't inconsistencies or incompatibilities at work here, but incompleteness.

View on HN

I think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent.

See for example:

http://en.wikipedia.org/wiki/Consistency_proof#Consistency_a...

Moreover, Gödel's second incompleteness theorem shows that the consistency of sufficiently strong effective theories of arithmetic can be tested in a particular way. Such a theory is consistent if and only if it does not prove a particular sentence, called the Gödel sentence of the theory, which is a formalized statement of the claim that the theory is indeed consistent.

"I think the point is that if you try to add those unprovable theorems to the system to try to make it complete it becomes inconsistent."

Eh? No it doesn't! If you add Con(PA) to the axioms of Peano arithmetic you obtain a stronger system. That system can't prove its own consistency, of course, but if you have a proof that the system PA + Con(PA) is inconsistent then you're probably in line for a Fields Medal.

Alan Turing worked on precisely this issue, developing ordinal logics in his PhD thesis (with Alonzo Church) to try to overcome incompleteness. Soloman Feferman, who in the 1960s proved a stronger result than Turing obtained, has written about this extensively. An accessible paper is this one:

http://math.stanford.edu/~feferman/papers/turingnotices.pdf

Yes, but in your example the system is still incomplete and the moment you would add an axiom that would make it complete, it would become inconsistent (so either you never finish your puzzles or you finish them and exactly the same moment they fall apart).

From Wikipedia again: http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_t...

Gödel's theorem shows that, in theories that include a small portion of number theory, a complete and consistent finite list of axioms can never be created, nor even an infinite list that can be enumerated by a computer program. Each time a new statement is added as an axiom, there are other true statements that still cannot be proved, even with the new axiom. If an axiom is ever added that makes the system complete, it does so at the cost of making the system inconsistent.

Right, but the point here is that we're not just talking about extensions of the system, we're talking about true but unprovable statements—that is, statements that are true in the standard model of arithmetic but not provable in PA (or whatever other arithmetic theory strikes your fancy). This is why Turing looked not at single formal theories but at a hierarchy of consistency extensions of the initial theory. In other words, the game changes from formal provability to informal provability, and from provability relative to a set of axioms to absolute provability. Turing showed (very roughly) that given a tree of consistency extensions (which branches only at limit stages) every Pi_1 sentence was decided at some point a with |a| = ω + 1. Feferman then proved in the 1960s that there is a path through the tree of ordinal notations that decides every Pi_2 sentence. These are completeness results, albeit for progressions of formal systems rather than individual systems. So certainly the puzzle can never be completed within a single formal system, but by restricting to sentences of limited complexity, there is an ordinal-time operation which decides each sentence (obviously there are numerous philosophical problems with this, although I'm afraid my expertise in this area is extremely limited so I can only give a sketch of the issues involved).

But it really is mind-bending: if you, instead, add a theorem to the system (say, ZFC) which states, "ZFC is consistent", this system (ZFC+Con(ZFC)) is consistent! Even more strangely, if you instead add "ZFC is not consistent", this system (ZFC+notCon(ZFC)) is also consistent. We call these "self-hating theories."

Pieces of puzzle = true statements about the natural numbers.

Pieces already put together = proved true statements.

Pieces that won't fit = true but unprovable statements.

Of course every analogy breaks down somewhere but I thought this one was pretty good.

The point must surely be that one can add the these true-but-unprovable statements to the original axioms without contradiction. They fit just fine: they're all elements of Th(N). It's a poor analogy because the natural way of thinking of a jigsaw puzzle is of a set of elements (pieces) that are consistent (every piece has a place), so if a piece doesn't fit then it's not consistent with the others. But this is false if the pieces are statements in the language of arithmetic that are true of the natural numbers.

IIRC, In "The Emperors New Mind" Penrose mentions that Godel employed Cantor's "Method of Diagonalization" to show that within a system such as the natural numbers there can be true statements(uncountably infinite) not on the list of provable statements(countably infinite).

Reply on news.ycombinator.com