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

Gödel, Escher, Bach: an in-depth explainer

alignmentforum.org

Post reply on HN
Print view View original

171–180 of 252 posts

Re: Gödel, Escher, Bach: an in-depth explainer

#171

Post by divbzero »

mav88 wrote: post #36
davesque wrote: post #10

I've read GEB over many years rather in the way someone would read the Bible. I pick it up from time to time and enjoy chewing on one or two chapters of material. But I've yet to figure out if the book actually has a specific thesis. I know it's all about the power of interpretation and the way in which interpreting a formal system as self-referencing has the effect of completely blowing up the intended design of tha…

The central thesis of GEB is this: what is a self? From the preface of the 20th anniversary edition: "GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter. What is a self, and how can a self come out of stuff that is as selfless as a stone or a puddle?"

Someday—when we have all this figured out—someone should write What Is Self? as the sequel to Schrödinger’s What Is Life?

Re: Gödel, Escher, Bach: an in-depth explainer

#172

Post by thayne »

schoen wrote: post #165
thayne wrote: post #145

Earlier quoted context omitted.

I don't know if it is quite what you are looking for, but with the normal mathematical axioms, it isn't possible to prove whether or not the there are any sets with a cardinality between the cardinality of the natural numbers and the cardinality of the real numbers. But one of those two must be true, you just can't prove it. Of course you can add a new axiom that allows you to prove one or the other (or accept one of…

> But one of those two must be true, you just can't prove it. Three alternative accounts: * Both the CH and ¬CH mathematical universes really exist, so we just have to choose which one we're more interested in at a given time. Like one might say there are the "reall numbers" and the "realle numbers", both valid and interesting constructions which humanity was just slow to recognize the distinctions between (because t…

sure, but if you ignore any connection to the real world or platonic truth and are just talking about within the ZFC formalism, then `CH ∨ ¬CH` is a true statement, even though it is impossible to prove either `CH` or `¬CH`.

Re: Gödel, Escher, Bach: an in-depth explainer

#173

Post by dudeguy3301 »

adastra22 wrote: post #158
memetomancer wrote: post #146

Earlier quoted context omitted.

Interesting take. You have casually dismissed the Goldbach Conjecture (perhaps the deepest centuries old problem in number theory) as 'trite, trivial and uninteresting'... Suggesting that you are only minimally familiar with the issue... then toss about an inapplicable phrase 'self-referential recursive logic' as if you are deeply immersed in such matters, perhaps even _much_ smarter than the thousands of mathematici…

I was talking about Gödel, not Goldbach: > The proof of Gödel's result's involves very carefully formalizing what statements and proofs mean so that they can be encoded as statements about arithmetic. He then shows there is a statement with encoding G that says "The statement with encoding G cannot be proved" – if it is true, then it cannot be proved. Sorry I meant to quote this bit at the beginning of my comment. Pa…

wait, so you are casually dismissing Gödel's work as a logical "gotcha"? don't premise opinions about complex proofs on other peoples woefully impoverished and misrepresented explanations of said proofs

that is disrespectful and very very very short sighted.

also, go read up (...on Gödel, Cantor, Turing, Tarski, etc...)

Re: Gödel, Escher, Bach: an in-depth explainer

#174

Post by edanm »

teawrecks wrote: post #117
layer8 wrote: post #73

Earlier quoted context omitted.

See https://en.wikipedia.org/wiki/Consistency . Under the syntactic definition of consistency, a self-contradiction simply means that a particular statement and its logical negation can both be proved in the system. That doesn’t say anything about the truth of the statement.

But isn't something defined as true in a system iff it can be proven in said system? So the only way "proven but untrue" makes sense is if there is a contradiction, no?

> But isn't something defined as true in a system iff it can be proven in said system?

No. You can build a really trivial system and know things about it "from the outside", so to speak, even if they can't be proved within the system itself.

Godel's work is exactly about showing the difference between something being actually true, and something being provable within a system.

Let's take a not-real example: we know there are infinitely many primes. If you define arithmetic formally, you can fairly easily prove that there are infinitely many primes. But, in theory, it could be something that isn't provable, but is still true; true because you can always actually generate more primes, but unprovable because there is no way to build a proof out of the axioms of arithmetic to show this.

Now, this isn't true about the infinitude of primes, because it can be proved within arithmetic. But there are lots of other statements that we have't proved yet - and theoretically, any one of them could end up being unprovable. E.g. Goldbach's conjecture or the 3n+1 theorem - they might be actually true but something we can't prove within the way we've defined arithmetic.

Re: Gödel, Escher, Bach: an in-depth explainer

#175

Post by skoodge »

a1369209993 wrote: post #140
jstanley wrote: post #39

> Gödel's Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable. This is only half of it! Gödel's Incompleteness Theorem states that any sufficiently rich formal system, together with an interpretation, either has strings which are true but unprovable or has strings which are provable but untrue. Either is possible! In practice people p…

> > Gödel's Incompleteness Theorem: any sufficiently rich formal system, together with an interpretation, has strings which are true but unprovable. Somewhat oddly, this is actually technically correct - a "sufficiently rich" system is one that can distinguish true versus false statements of Peano Arithmetic, and a inconsistent system, by the principle of explosion, can prove any statement, so can not distinguish sta…

That's only true for systems where the principle of explosion actually holds though, isn't it? So it wouldn't apply to paraconsistent systems.

In the end, Gödel is actually giving us a choice: Either accept incompleteness or accept inconsistency. Of course it's true that historically incompleteness has been perceived as the only viable choice, but at least a few paraconsistent logicians like Graham Priest have argued for (non-explosive) inconsistency instead.

Re: Gödel, Escher, Bach: an in-depth explainer

#176

Post by martopix »

kenjackson wrote: post #7

Is there a good book that is similar in spirit, but doesn't require the maturity of GEB? I know an 8th grader that would be a great target, but I don't know if they have the mathematical/logical maturity to get through it.

I read GEB at about 18 and it changed my view of things. I loved it deeply and studied even the formulas. But not everyone is like that I guess. And even my self today wouldn't be.

Re: Gödel, Escher, Bach: an in-depth explainer

#178

Post by polytely »

craggyjaggy wrote: post #3

Maybe one day I'll try reading it again and actually finish it, but so far I couldn't do it. Everything is fascinating and mind blowing don't get me wrong, but I feel like there is always this weird pretentious atmosphere going on. I don't know how to describe it, but by the end of the first half reading GEB was not fun anymore.

I don't really get why it would be pretentious, like it's not pretending to be smarter than it is. It doesn't seem to me that the author is showing off for the sake of showing off, but rather that he is not hiding his joy and love for the themes discussed in the book.

Re: Gödel, Escher, Bach: an in-depth explainer

#179

Post by Tainnor »

adastra22 wrote: post #134
mreid wrote: post #93

Earlier quoted context omitted.

It might be easiest to give a sense of what "unprovable but true" means by way of an imagined example. Goldbach's conjecture is that "every even number bigger than 2 is the sum of exactly two prime numbers", so 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, etc. For this statement to be *true* it just means that every even number there must exist two primes that add to that number. This is a statement about infinitely many integer…

I’ve only ever seen examples like the one you give here, which seem like trite, trivial, and uninteresting middle-school level logical gotchas. Are there actually interesting properties which are true but can’t be proven? Or is it just a statement about self-referential recursive logic being unprovable?

There are examples of "natural" sentences which are unprovable in Peano Arithmetic (which is one of the simpler systems for which Gödel's theorems apply): https://en.m.wikipedia.org/wiki/Paris%E2%80%93Harrington_the...

But in general, Gödel applies to all formal systems that satisfy certain properties, it's just that the exact unprovable sentences will be different (since you may just add that sentence as an axiom) that's why the general example is very abstract. It shows that sufficiently rich theories are not only incomplete, but also incompletable.

Re: Gödel, Escher, Bach: an in-depth explainer

#180

Post by cruegge »

bo1024 wrote: post #128
red_trumpet wrote: post #51

Earlier quoted context omitted.

How can a statement that is unprovable be true? I always had the impression that unprovable means you could add either the statement or its negation as an axiom, and both resulting systems are as consistent as the system you started with

Oof @ many of these answers. The reason is that there are multiple "models" of the natural numbers that satisfy the axioms, and the statement is true in the usual model that we all know, but in some other models the statement is false. See https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... and https://en.wikipedia.org/wiki/Peano_axioms#Nonstandard_model... Godel's "completeness" theorem gives a converse.…

That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.
Post reply on HN