Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What Do Gödel's Incompleteness Theorems Mean?

quantamagazine.org

Post reply on HN
Print view View original

41–50 of 72 posts

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

#41

Post by bananaflag »

svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

The undecidability of the halting problem yields an easy proof of Gödel's "zeroth" incompleteness theorem:

Statement: Every sound (i.e. not just consistent, but sound) recursive theory of arithmetic is incomplete.

Proof: Assume it is complete. List all its theorems by a program. Then one can decide the halting problem as follows: for any instance, look whether "the program halts" or "the program does not halt" shows up in the list of theorems (since the theory is complete, one of them must show up; and since the theory is sound, the theorem is true).

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

#42

Post by [deleted] »

pdonis wrote: post #22
danbruc wrote: 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…

[deleted]

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

#43

Post by Maxatar »

oulipo2 wrote: post #35
svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

Halting problem concerns decidability, not completeness

Sure but that's fairly pedantic. You can derive Godel's first incompleteness theorems strictly as a consequence of undecidability of the halting problem.

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

#44

Post by Epa095 »

pdonis wrote: post #40
Epa095 wrote: 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.

I don't understand what you mean by this. Gödels two incompleteness theorems are about theories of natural numbers, so their models are infinite. I don't understand what you could mean by them applying to finite models.

I stand by my claim. The key point of Gödels incompleteness is NOT that no single theory can pin down a single model, that was known before.

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

#45

Post by cyberax »

svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

The proof of the first incompleteness theorem is a very technical way of constructing the statement: "The truth of this statement is unproveable".

In the software form, it can be restated as: "there is no finite program that outputs the sequence with this property".

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

#46

Post by kkylin »

alan-crowe wrote: post #30

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…

I really do think the incompleteness theorems deserve the attention they get, not just because of what they say about efforts to formalize mathematics and because of the historical context -- remember Gödel numbers came (just) before Turing and the first recognizably modern electronic computers. That numbers can represent things that are not numbers was (IMO) a revolutionary idea.

Having said all that, I'd taken mathematical logic in college to learn about incompletenss, but the most interesting things I got out of it were completeness and compactness. Non-standard models really can be quite interesting.

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

#47

Post by jojomodding »

bananaflag wrote: post #41
svantana wrote: post #7

Of all the incompleteness-style theorems, I find the Halting problem to be the most approachable and also the most interesting. Maybe it's because I'm a software dev that dabbles in math rather than the other way around. But that makes me wonder if all of Gödel's theorems can be stated if 'software form', so to speak.

The undecidability of the halting problem yields an easy proof of Gödel's "zeroth" incompleteness theorem: Statement: Every sound (i.e. not just consistent, but sound) recursive theory of arithmetic is incomplete. Proof: Assume it is complete. List all its theorems by a program. Then one can decide the halting problem as follows: for any instance, look whether "the program halts" or "the program does not halt" shows…

This also makes it obvious that at some point, the halting problem becomes "unprovably hard." There must be Turing Machines for which it is independent of the accepted axioms of mathematics whether or not they halt. And indeed, constructing such machines is not too difficult.

There is current research into finding the smallest such Turing Machine. Here is one with 748 states: https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

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

#48

Post by joe_the_user »

Epa095 wrote: post #21
bo1024 wrote: 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…

No. Godel's completeness theorem can not be understood without bringing in first order logic, because it is a statement of the expressitivity of the language(relative to its semantics). Other more expressive languages, like second order logic (with its usual semantics) is not complete. Trying to explain Godel's completeness theorem without bringing in the language is a path to confusion. And your explanation of the f…

Actually, I think your statement muddies the waters a bit and the parent gives a clearer picture for those looking for a simple statement of what's going on. The background is the fellow comment: https://news.ycombinator.com/item?id=48224739. Godel's simplest (and roughly original) statement is any system of axioms strong enough to encode arithmetic is either consistent or complete. You can "Or the set of axioms is not enumerable" (as in Second Order Logic and other systems). But when one says that, one has jumped from what would be normally recognized as logic (finite axioms and process) to a mathematical construct with some similarities to naive logic but which "my gran pappy" would not see as logic.

I mean, you can formally construct an axiom system defined to include (via axiom of choice) and assign a truth value to each of the independent propositions of first order arithmetic logic. There, you have consistent and complete system but not one that's a whit closer to being in usable by anyone.

I'm not even a finitist but I think being clear what's going on with these claims is important. It's like saying "the halting problem can't be solved by finite computers but my infinite-foo hypothetical computer can solve it, gotten mention that..."

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

#49

Post by joe_the_user »

marojejian wrote: post #2

Interesting points in here. e.g. that Godel didn't think this scrapped Hilbert's project totally: >Gödel believed that it was possible to redefine what we mean by a formal mathematical framework, or allow for alternative frameworks. He often discussed an infinite sequence of acceptable logical systems, each more powerful than the last. Every well-formulated mathematical question might be answerable within one of them…

I think the combination of Godel's completeness theorem and Godel's incompleteness theorem stakes out a position in between "truth absolutism" (everything certainly knowable etc) and "truth nihilism" (nothing is truly knowable with any certainty). Which I think is great. Thing, however, is that a lot of philosophers and mathematicians fall into one of these views of truth and so you see people constantly fighting, chaffing at the bit against, this middle ground, claiming it "satisfies nobody" etc. Well, it satisfies me quite a bit.

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

#50

Post by voxl »

cobbal wrote: post #37
lacewing wrote: post #9

Earlier quoted context omitted.

Right, if you're a software engineer, the realization that the two theorems are nearly-equivalent really takes the air out of a lot of the existential philosophizing around Gödel's incompleteness. Gödel's argument basically says that any system of mathematics powerful enough to implement basic arithmetic is a computer. This shouldn't be surprising to software engineers because the equivalency between Boolean logic an…

I think that's selling the theorems a little short. A math system with arithmetic is equal to, or more powerful than, a computer. For an example, even classical logic comes with the law of excluded middle that can say (internally) if a program halts or not. Incompleteness applies to all the stronger systems as well.

There is no logic that is more expressive than a Turing machine. In fact, just about every logic you know can only expressive necessarily terminating programs. There is a bit of an issue on what exactly someone means by expressive, but if we're talking programs that compute outputs from inputs (without caring about the invariants imposed on said programs) then this holds.
Post reply on HN