Hacker News Reader

Comment by jimhefferon | Hacker News Reader

> The high-level, slightly handwavey description of this theorem is that, for any sufficiently expressive mathematical proof system, there are more true facts within the system than there are proofs for facts, which in turn means that not every fact can be proved

No, no, no. The proof is not by cardinality. The proof is constructive. That is the point of the book, or at least a major theme of it. For example, that is the point of the record player analogy.

View on HN

If I recall, the point is that if you have a record player that can play _every record_, then it can play _a record that breaks it_.

I think the piece's statement is supposed to relate to the "enumerating all deductions" bit of the Godel-numbering

The author also wrongly asserts that this metaphor is supposed to illuminate the incompleteness theorem when really it's just teasing some ideas that he explains in more detail later in the book.

> "the proof"

As if there can only be one. (And it seems OP is describing the theorem, not a proof)

It's just plain wrong to say that there are more facts in a theory than proofs of facts. Both of these sets are countably infinite. Godel's theorem proves that provable facts are a strict subset of all facts.

While I agree with you, in the context of a "hand wavey" explanation, "more" is not rigorously defined and so saying "plain wrong" is silly. A strict subset relationship is a reasonable interpretation of "more" in the context of an informal discussion.

Yes, but the use of "which in turn" suggests that was not meant; it suggests that what follows is a real deduction and not a mere rephrasing.

Leaving aside the fact that talking "informally" about infinities easily leads to wrong conclusions, the OP wasn't even talking about a strict subset relationship. The comparison was between a set of proofs and a set of facts, which are sets of different mathematical objects. So at best you can say that each proof proves a fact (a fact can have several proofs) and the set of facts that have a proof is a strict subset of all facts. Or, informally, there are more facts than facts which can be proved. Oh, wait, this just restates the theorem we're trying to prove in the first place and doesn't give any insight into why it's correct.

>It's just plain wrong to say that there are more facts in a theory than proofs of facts. Both of these sets are countably infinite.

Some infinities are larger than others. This was proved by Georg Cantor, who created set theory.

And if you read about Cantor you will find he defined a term called 'countably infinite'. No 'countably infinite' set has a higher cardinality than any other.

Reply on news.ycombinator.com