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

31–40 of 80 posts

Re: Gödel and the limits of logic

#31

Post by haliax »

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, which is to say take any formal system and prove theorems with it? How do you determine what formal systems are "valid" logics? (Leading to sensible conclusions rather than nonsense like A & ~A)

Re: Gödel and the limits of logic

#32

Post by haliax »

vbtemp wrote: post #18
ChrisHugh wrote: post #15

What I get out of Goedel is this: There are some things that are true that cannot be proved.

Be careful. That's a naive view, and drawing more conclusion than I think you mean. This it more like it: For any consistent, finite axiomatized formal system that is sufficiently expressive (such as the Principia Mathematica), you can construct a sentence in the language of that formal system that asserts its own un-provability. Therefore, there does not exist a mechanistic method for enumerating over all true state…

> humans don't reason based on mechanistic principles

Do you support an empiricist view of logic then (http://en.wikipedia.org/wiki/Is_logic_empirical%3F) ? That we justify logical rules because they so strongly correspond with our own experiences?

Re: Gödel and the limits of logic

#33

Post by Rickasaurus »

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

Godel Escher Bach is a great book (it's entertaining and informative) for learning about formal systems. There are general rules (rules of inference) for their construction from axioms that will keep you from going wrong.

Re: Gödel and the limits of logic

#34

Post by vbtemp »

haliax wrote: post #32
vbtemp wrote: post #18

Earlier quoted context omitted.

Be careful. That's a naive view, and drawing more conclusion than I think you mean. This it more like it: For any consistent, finite axiomatized formal system that is sufficiently expressive (such as the Principia Mathematica), you can construct a sentence in the language of that formal system that asserts its own un-provability. Therefore, there does not exist a mechanistic method for enumerating over all true state…

> humans don't reason based on mechanistic principles Do you support an empiricist view of logic then ( http://en.wikipedia.org/wiki/Is_logic_empirical%3F ) ? That we justify logical rules because they so strongly correspond with our own experiences?

Not really. I'm just saying we don't go around all day doing logic-algebra in our head and saying only true, consistent things :)

Re: Gödel and the limits of logic

#35

Post by haliax »

vbtemp wrote: post #34
haliax wrote: post #32

Earlier quoted context omitted.

> humans don't reason based on mechanistic principles Do you support an empiricist view of logic then ( http://en.wikipedia.org/wiki/Is_logic_empirical%3F ) ? That we justify logical rules because they so strongly correspond with our own experiences?

Not really. I'm just saying we don't go around all day doing logic-algebra in our head and saying only true, consistent things :)

Ahh, fair enough. I'd have to agree with you there. My guess is that that plus being able to inductively generate axioms from experience are largely what let us escape that particular weakness of formal systems.

Re: Gödel and the limits of logic

#36

Post by haliax »

Rickasaurus wrote: post #33
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,…

Godel Escher Bach is a great book (it's entertaining and informative) for learning about formal systems. There are general rules (rules of inference) for their construction from axioms that will keep you from going wrong.

I've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!

Re: Gödel and the limits of logic

#37

Post by VMG »

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?

If you want to start off easy listen to this: http://www.radiolab.org/2011/oct/04/

Re: Gödel and the limits of logic

#38

Post by JamesLeonis »

haliax wrote: post #36
Rickasaurus wrote: post #33

Earlier quoted context omitted.

Godel Escher Bach is a great book (it's entertaining and informative) for learning about formal systems. There are general rules (rules of inference) for their construction from axioms that will keep you from going wrong.

I've read it, but clearly didn't digest enough (a common problem I'm told :P). I will take another look, thanks!

If you didn't already know about it, there's a Reddit group that's doing a weekly readthrough and discussion. They're on chapter 13 currently.

http://reddit.com/r/GEB

Re: Gödel and the limits of logic

#39

Post by lmkg »

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?

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 understand the ramifications of Godel's theory, it impacts math more directly than CS. The most directly impacted branches of math are the more "fundamental" ones like Set Theory. Limitations of CS has a lot more to do with Turing's theorems than Godel's.

Re: Gödel and the limits of logic

#40

Post by malingo »

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've always liked GW Flake's writing on the topic.

http://mitpress.mit.edu/books/FLAOH/cbnhtml/excerpts1.html

Post reply on HN