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

Gödel and the limits of logic

plus.maths.org

Post reply on HN
Print view View original

51–60 of 80 posts

Re: Gödel and the limits of logic

#51

Post by stiff »

ionfish wrote: post #42
stiff wrote: post #25

Earlier quoted context omitted.

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 on…

"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 T…

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.

Re: Gödel and the limits of logic

#52

Post by IsTom »

lmkg wrote: post #39
rgower wrote: post #27

Earlier quoted context omitted.

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

If you want to understand just Godel's theorem, you probably want to focus on Logic more than Math or CS. Godel's proof involves qualifying over first-order logic statements and logical properties of numbers much more than it involves computation or numerics. The most nitty-gritty part is Godel encodings, but it's not that computationally intensive, and the details actually aren't that relevant. If you want to unders…

Actually Godel's proof is important to CS, it's an analogue of Turing's Proof concerning undecidable problems.

Re: Gödel and the limits of logic

#53

Post by omaranto »

vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

My favorite book about incompleteness is Raymond Smullyan's Godel's Incompleteness Theorems.

Re: Gödel and the limits of logic

#54

Post by haliax »

ionfish wrote: post #49
haliax wrote: post #31

On a related note, does anyone know where I would look to understand reducibility of formal systems to one another? I'm really interested by questions like: Why is second order logic irreducible to first order logic if I could use first order logic to reason about the behavior of a turing machine running a second order logic theorem prover with whatever inputs I like? How do I get something that can do what I can do,…

'Reducibility' in general is an informal notion, and as such there are many different technically precise ways of capturing aspects of it. Mutual interpretability and bi-interpretability are two of these, but they apply to formal systems with the same underlying logic (that is, the same semantics and proof theory). There are also many other notions of translation between different logics like Gödel–Gentzen negative t…

> Second order logic does not have a complete proof theory

Is this different from saying that second order logic contains unprovable true statements / that the incompleteness theorem applies?

Also thanks for the really well informed response!

Re: Gödel and the limits of logic

#55

Post by praptak »

vbtemp wrote: post #28
rgower wrote: post #27

Earlier quoted context omitted.

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

At the very least a good course in discrete mathematics is a good start (it's also a good start for anything technical as well - one of the most valuable math classes anyone can ever take, as far as I'm concerned) Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under…

> At the very least a good course in discrete mathematics is a good start

I believe that the best starting point to get to incompleteness is formal logic. This is the basic set of concepts that lets us make terms, statements and finally proofs the subject of formal mathematical study, thus tying the loop (formally mathematically defined reasoning about formally mathematically defined reasoning :-) ) that leads to Goedels proof.

Discrete mathematics is helpful but it is rather low level, the core concepts in incompleteness come from formal logic.

Re: Gödel and the limits of logic

#56

Post by zerostar07 »

rgower wrote: post #27
vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

I think it's best to go directly at the source. Wikipedia has a very understandable sketch of proof (which in itself is quite unconventional) that helps understand the motivation and the content of the theorem: http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s...

Re: Gödel and the limits of logic

#57

Post by ionfish »

stiff wrote: post #51
ionfish wrote: post #42

Earlier quoted context omitted.

"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 T…

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 numb…

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

Re: Gödel and the limits of logic

#58

Post by mcguire »

rgower wrote: post #27
vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

Whatever approach you take, be sure it includes Torkel Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. Although it's pretty good, it may not be where you want to start. But there are a lot of bogus conclusions made by people with a superficial understanding of Gödel and that is the best thing I know pointing out the flaws.

Re: Gödel and the limits of logic

#59

Post by ionfish »

haliax wrote: post #54
ionfish wrote: post #49

Earlier quoted context omitted.

'Reducibility' in general is an informal notion, and as such there are many different technically precise ways of capturing aspects of it. Mutual interpretability and bi-interpretability are two of these, but they apply to formal systems with the same underlying logic (that is, the same semantics and proof theory). There are also many other notions of translation between different logics like Gödel–Gentzen negative t…

> Second order logic does not have a complete proof theory Is this different from saying that second order logic contains unprovable true statements / that the incompleteness theorem applies? Also thanks for the really well informed response!

One of the features of first order logic is that the provability relation is recursively enumerable: given any recursive first order theory, there is a Turing machine that can list every theorem of that theory (although of course it will run forever).

Additionally, first order logic is complete: for every statement true in all models of a theory, there is a proof of the statement from the theory.

These two constraints cannot both be satisfied in a sound deductive system for second order logic. To see that this is so, consider that in second order logic we can prove Dedekind's categoricity theorem: there is only one model (up to isomorphism) of the second order Peano axioms (PA2). Let's assume that the provability relation for second order logic is recursively enumerable. We know from Gödel's incompleteness theorem that the set of first order sentences true of the natural numbers is not recursively enumerable. So take a sentence of the form "If PA2 then _" for some sentence _ which is in that set but not in the extension of the provability relation (this is a legitimate statement since the PA2 axioms are finite so we can just take their conjunction). This should be a logical truth of second order logic, but it's not provable (by the argument just given), so second order logic is incomplete: there are statements which are logical consequences yet are unprovable. So in other words, yes, the incompleteness theorem is very much at play in this limitation of second order logic.

For the technical details I very much recommend chapters 3 and 4 of Shapiro's book; it's not terribly expensive, and any decent university library should have a copy.

(A small footnote to my earlier post: Shapiro's book originally came out in 1991, not 2000—that's just the date of the paperback edition, and I'm unsure as to whether there are any substantial differences between the two.)

Re: Gödel and the limits of logic

#60

Post by ionfish »

rgower wrote: post #27
vbtemp wrote: post #10

When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics as well). These are a…

I have no background in CS or Math, but a lot of philosophy. In other words, I'm a highly interested layman. What's my best plan of action to understanding Godel's theory? Maybe the best approach would be an entry level book on CS?

Do you have a decent understanding of first order logic? If not, sort that out first. Peter Smith has a good list of books to choose from:

http://www.logicmatters.net/2012/05/teach-yourself-logic-1-f...

Then get Smith's book An Introduction to Gödel's Theorems. It explains Gödel's results in great detail and doesn't assume too much background knowledge. A certain amount of perseverance will, of course, be required…

There's some supplementary material on his website: http://www.logicmatters.net/igt/

Post reply on HN