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

181–190 of 252 posts

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

#181

Post by machina_ex_deus »

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?

The Continuum hypothesis is independent of ZFC. It is the first of Hilbert's 23 problems.

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

#182

Post by red_trumpet »

mreid wrote: post #93
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

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…

What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no prove for S" (which includes the case that S is provably false), or do we mean "there is no proof for S and there is no proof for its converse"?

Because if you show that the converse of Goldbach's conjecture is not provable, you have actually proven Goldbach's conjecture (since you have shown that there is no counterexample!).

>Think of each statement about the natural numbers as a subset where each number in the subset makes the statement true. There are uncountably many subsets of the natural numbers (by Cantor's diagonalization argument).

Don't we only care about the countable set of statements that can written down in a given logical system? Say second order logic + ZFC.

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

#183

Post by bedman12345 »

cruegge wrote: post #180
bo1024 wrote: post #128

Earlier quoted context omitted.

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.

Yeah but second order logic itself is incomplete. ZFC doesn't have a single model, too, btw. In the end unprovable sentences exist because there are multiple models satisfying your axioms.

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

#184

Post by bmacho »

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?

Why not?

E.g.: if ZFC is consistent, then ZFC+~Con(ZFC) is consistent as well, where ~Con(ZFC) is the statement that there is a contradiction in ZFC.

Now, ZFC+~Con(ZFC), which is a perfectly good axiom system, consistent and can talk about anything, can prove that the Turing machine that searches for a contradiction in ZFC halts (just apply the axiom ~Con(ZFC)), but it doesn't make it true.

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

#185

Post by red_trumpet »

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?

Wikipedia has a list[1] of statements which are not provable in (or rather independent of) ZFC.

IMO the most weird thing is the following, intertwining consistency of ZFC with Diophantine equations[2]:

> One can write down a concrete polynomial p ∈ Z[x1, ..., x9] such that the statement "there are integers m1, ..., m9 with p(m1, ..., m9) = 0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). [...] the polynomial is constructed so that it has an integer root if and only if ZFC is inconsistent.

[1] https://en.wikipedia.org/wiki/List_of_statements_independent...

[2] https://en.wikipedia.org/wiki/List_of_statements_independent...

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

#186

Post by eternalban »

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…

Roger Penrose supposedly wrote Emperor's New Mind as a direct rebuttal of GEB from a physics point of view. These two books, ironically, seem to form an undecidable dual. One of them is true, but neither managed to prove its point.

p.s. GEB is ultimately arguing that mind arises from complexity in structure and algorithm. ENM counters that by noting (apparent) non-deterministic aspects of consciousness, proposing quantum effects as a possible source of consciousness. (That was my overall take on the these two books.)

p.s.s. What is not convincing about GEB's argument is the lack of a reasonable explanation for meaning. What it does argue well is how meaning unfolds (self-reference, recursion, composition) but just as Cellular Automatas (CAs) deceptively look like natural phenomena but entirely ignore the extra-CA substrate that simulates the CA world, GEB too ignores the missing mind that is supposed to traverse these layers of abstraction based on self-reference, recursion, and composition. So it is ultimately a purely aesthetic argument (even though the machinery of logic and mathematics are thrown in,) just like certain branches of modern theoretical physics.

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

#187

Post by theteapot »

skoodge wrote: post #175
a1369209993 wrote: post #140

Earlier quoted context omitted.

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

There are no paraconsistent logicians arguing for explosive inconsistency?! Outrageous.

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

#188

Post by wikfwikf »

machina_ex_deus wrote: post #181
adastra22 wrote: post #134

Earlier quoted context omitted.

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?

The Continuum hypothesis is independent of ZFC. It is the first of Hilbert's 23 problems.

This is the best example - before it was shown that the Continuum Hypothesis was unprovable, many people believed, like the GP, that only uninteresting and artificial statements could be shown to be unprovable.

The CH is undoubtedly meaningful, natural, and of huge interest to (a subset of) mathematicians.

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

#189

Post by wikfwikf »

memetomancer wrote: post #146
adastra22 wrote: post #134

Earlier quoted context omitted.

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?

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…

The Goldbach conjecture is of very little interest to mathematicians, unlike either Fermat's Last Theorem or the Riemann Hypothesis. Statistically it is clearly true, in the sense that there are way more prime numbers than you would need for it to be true. Finding a counterexample would be interesting in the sense that it would be very surprising (but not mathematically interesting).

It is fated to be proved as a trivial corollary to some more important mathematics; a corollary that no one would have bothered with if not for the historical importance.

The unsolved Twin Prime Conjecture, of roughly the same age, is expected to lead to much more interesting mathematics if it is proved.

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

#190

Post by wikfwikf »

didericis wrote: post #160
jhanschoo wrote: post #157

Earlier quoted context omitted.

> You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this For such proofs to be contained in a finite space, the verifying person or machine needs to be able to distinguish between arbitrarily minute differences between proofs.

You don’t need to go through every possible element in that infinite uncountable set to prove that relationship, though. You can create an arbitrary demonstration that you can then manipulate in your head. Once you see that water demonstration you can inuit how that relationship must persist at different sizes. Again, that doesn’t really count as a “proof” by modern standards, but it’s how the ancient greeks thought…

But your brain is, presumably, doing finitely many cognitive steps, so it seems that a proof you can understand can also be expressed finitely?
Post reply on HN