4 ms·

"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 under

by ionfish 14y ago

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

te_platt 14y ago
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.
- ionfish 14y ago
  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.
stiff 14y ago
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_and_completeness_in_arithmetic 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.
- ezyang 14y ago
  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."
  - deleted 14y ago
    [deleted]
- ionfish 14y ago
  "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 http://math.stanford.edu/~feferman/papers/turingnotices.pdf
  - stiff 14y ago
    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_theorems 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.
jhart3333 14y ago
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).

by ionfish 14y ago

te_platt 14y ago

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.

ionfish 14y ago
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.

stiff 14y ago

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

ezyang 14y ago
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."
- deleted 14y ago
  [deleted]
ionfish 14y ago
"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 http://math.stanford.edu/~feferman/papers/turingnotices.pdf
- stiff 14y ago
  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_theorems 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.

jhart3333 14y ago

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