Live data from Hacker News

What Do Gödel's Incompleteness Theorems Mean?

quantamagazine.org

51–60 of 72 posts

Re: What Do Gödel's Incompleteness Theorems Mean?

#51
post #40
post #36

Earlier quoted context omitted.

> The key point of the incompleteness theorem is that it shows that (at least in first order logic, which is the logic in which the theorem holds) no set of axioms can ever pin down a single model. No, this was known before the incompleteness theorem, ref Löwenheim–Skolem theorem.

The Lowenheim Skolem theorem only applies to first-order axiom systems that have an infinite model. So it would apply to the axioms for the natural numbers, yes. The Godel theorems apply to any first-order axiom system, regardless of whether it has an infinite model or not.

He's right, the Godel theorems have nothing to do with existence of models satisfying this-or-that. Such would be "semantic" truths. The reason Hilbert's program survived Löwenheim–Skolem is that Hilbert was a formalist concerned with "syntactic" truth, that is, whether there are statements P such that neither P nor not-P could be proven by the axiom system.

You might think LS would trivially demonstrate as much---"Just take P = our underlying model is countable!"---but this is not formalizable within the system itself.

Re: What Do Gödel's Incompleteness Theorems Mean?

#52
post #17

It's much easier than it seems. * There are axioms, there are models, and there are theorems. * A model is a particular structure with objects and relationships. The "standard model of arithmetic" is just the natural numbers 0, 1, 2, ... with normal rules of addition and subtraction and so on. A different model could be the real numbers, or one that includes infinitesimally small numbers, or so on. * A set of axioms…

My understanding is that for any system of axioms strong enough to encode arithmetic, you can have at most two of these three properties: 1. Complete (for any well formed statement, the axioms can be used to prove either it or its negation) 2. Consistent (can't arrive at contradictory statements ~ arriving at a both a statement and its negation ) 3. The set of axioms is enumerable ~ you can write a program that lists…

It's also important to point out that if we cant prove a statement or its negation (one of which must be true) [...]

Is that true, could it not be neither, i.e. independent of the axioms? Or is this assuming completeness which rules out independent statements?

Re: What Do Gödel's Incompleteness Theorems Mean?

#53

As a child, I noticed that the proofs of mathematical theorems were esoteric knowledge, known only to a few adults. I struggled to follow even the simplest proofs, and hoped that one day I might learn to create a proof or two of my own. This was not only a high aspiration, but a dangerous one. I saw no reason why certain knowledge of a true fact would be accessible to humans via proof. Any-one who embarked on the que…

> Gödel completeness theorem is the really big deal. Except it isn't. That computer program turns out to be one of those wretched tree search ones that soon bogs down. The real problem turns out to be the combinatorial explosion inherent in unstructured search through the Herbrand universe. Yup. Incompleteness is sort of a red herring. P≠NP (even though unproven) yields the real, practical, painful incompleteness.

P versus NP could be a red herring too.

If P=NP, but the best asymptotic solution is n^7, and it has so much overhead that the best practical solution is n^9, then it doesn't really matter that it isn't exponential. It's still unsolvable for easily accessible problem sizes.

Re: What Do Gödel's Incompleteness Theorems Mean?

#54
The best way to understand the theorems is to try to understand the proofs, and the short book “Gödel’s proof” by Nagel and Newman is excellent for that. Just like Douglas Hofstadter wrote in the foreword, I found the book an absolute page turner and finished in one afternoon.

Re: What Do Gödel's Incompleteness Theorems Mean?

#55
post #22
post #19

Earlier quoted context omitted.

That is interesting, I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. But if it that is not the case and there always exist models where the theorem is true and false, that makes it sound to me, like the incompleteness theorem is not really about proving things. With that it sounds more like the inability of a sufficiently c…

> I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. As the GP points out, that's not what Godel's incompleteness theorem actually shows. Although it's a common misconception (one which unfortunately is propagated by many sources that should know better). The key point of the incompleteness theorem is that it shows that (at le…

I think you’re right that "true in all models but unprovable" is not accurate. By Godel’s completeness theorem if a FO sentence is true in every model of the axioms then it is provable from those axioms.

But I don’t think incompleteness is best described as saying "no first-order axioms can pin down a single model" That’s more about non-categoricity/compactness/Lowenheim–Skolem.

Re: What Do Gödel's Incompleteness Theorems Mean?

#56
Gödel's Incompleteness means that formal systems that are sufficiently expressive can be used to write down new kinds of statements that can neither be derived nor contradicted from their existing axioms. Those statements can be adapted as new axioms.

Unfortunately, Gödel's proof method per se only shows an example that is not so meaningful, involving self-reference. He builds a number-theoretical formal system which can talk about its own formulas, by encoding them as integers (something we do with computers now as a daily matter: all computer program text and other data is arithmetically encoded into binary, which has an interpretation as a number). In the context of Gödel's work, we call this arithmetic encoding "Gödel numbering".

Whether a proposition is true is reformulated as a number-theoretical property: instead of asking, is this proposition or equation true, we ask, is the arithmetic encoding of this proposition an integer which belongs to the set of theorem-integers; is it a theorem-number?

Within this framework, Gödel shows that a proposition can be made which says "G is not a theorem-number", such that this very propostion's own Gödel number is G! In other words, a kind of Quining is going on, whereby the proposition embeds a coded reference to itself. Essentially, Gödel introduces the idea that we can make a statement which says "I am unprovable", in formal, rigorous way. If that statement can be derived from the axioms, then a contradiction results: it was derived, yet it asserts the falsehood that it is not derivable, and so a falsehood was derived from the system's axioms. If it is true, then it points to incompleteness: there is a truth that can be expressed in the syntax of the system, yet cannot be derived.

Thus if we have any system expressive enough to encode the "G is unprovable" statement where that statement itself is G, that system is either inconsistent (allows a falsehood to be derived) or incomplete (allows true statements to be written which cannot be derived).

Re: What Do Gödel's Incompleteness Theorems Mean?

#57

Gödel's Incompleteness means that formal systems that are sufficiently expressive can be used to write down new kinds of statements that can neither be derived nor contradicted from their existing axioms. Those statements can be adapted as new axioms. Unfortunately, Gödel's proof method per se only shows an example that is not so meaningful, involving self-reference. He builds a number-theoretical formal system which…

> formal systems that are sufficiently expressive

One of the more interesting bits about this is understanding what "sufficiently expressive" means. The Naturals are incomplete, the Reals aren't.

Re: What Do Gödel's Incompleteness Theorems Mean?

#58

As a child, I noticed that the proofs of mathematical theorems were esoteric knowledge, known only to a few adults. I struggled to follow even the simplest proofs, and hoped that one day I might learn to create a proof or two of my own. This was not only a high aspiration, but a dangerous one. I saw no reason why certain knowledge of a true fact would be accessible to humans via proof. Any-one who embarked on the que…

Universe is the Godel sentence in the limit of all possible mathematics. Hence it exists and is True.

Fix axioms, we get a Godel sentence G1. Add G1 to axioms, we get G2. So on and so forth. In the limit of this process, we have our Universe.

Re: What Do Gödel's Incompleteness Theorems Mean?

#59
post #17

It's much easier than it seems. * There are axioms, there are models, and there are theorems. * A model is a particular structure with objects and relationships. The "standard model of arithmetic" is just the natural numbers 0, 1, 2, ... with normal rules of addition and subtraction and so on. A different model could be the real numbers, or one that includes infinitesimally small numbers, or so on. * A set of axioms…

My understanding is that for any system of axioms strong enough to encode arithmetic, you can have at most two of these three properties: 1. Complete (for any well formed statement, the axioms can be used to prove either it or its negation) 2. Consistent (can't arrive at contradictory statements ~ arriving at a both a statement and its negation ) 3. The set of axioms is enumerable ~ you can write a program that lists…

I just want to be a bit pedantic here (but this is logic after all...), and point out that in point 1 above you are talking about syntactical completeness, and not semantical completeness, which is the kind of completes Gödel proves in his first completeness proof. I think people are often confused because of this overloading of the word. And it is about sentences(a formula withouth free variables), not any well formed formula.

Re: What Do Gödel's Incompleteness Theorems Mean?

#60
post #22

Earlier quoted context omitted.

> I always thought that the incompleteness theorems says, there are theorems that are true or false in all models but cannot be proved to be so. As the GP points out, that's not what Godel's incompleteness theorem actually shows. Although it's a common misconception (one which unfortunately is propagated by many sources that should know better). The key point of the incompleteness theorem is that it shows that (at le…

I think you’re right that "true in all models but unprovable" is not accurate. By Godel’s completeness theorem if a FO sentence is true in every model of the axioms then it is provable from those axioms. But I don’t think incompleteness is best described as saying "no first-order axioms can pin down a single model" That’s more about non-categoricity/compactness/Lowenheim–Skolem.

> I don’t think incompleteness is best described as saying "no first-order axioms can pin down a single model"

Well, it's an obvious implication of the two theorems (completeness and incompleteness) combined: if a FO sentence is not provable from a system of FO axioms, it can't be true in all models of those axioms. And if an FO sentence is not provable, its negation can't be either (since proving its negation true would prove the sentence itself false). So the negation also can't be true in all models. That means there must be at least one model in which the FO sentence is false, and at least one in which its negation is false (so the sentence itself is true). Which means there must be at least two models of that set of FO axioms--i.e., the axioms can't pin down a single model. And the incompleteness theorem proves that there is such a sentence in every system of FO axioms.

I agree that the Lowenheim-Skolem theorem has similar consequences, since it says there must be models with different infinite cardinalities.

Post reply on HN