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

161–170 of 252 posts

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

#161

Post by thayne »

DontchaKnowit wrote: post #149
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…

This is super interesting. Was not aware of this. Is there a proof that this is not provable?

Yes, Paul Cohen proved that the continuum hypothesis (that there is no set with cardinality between that of natural numbers and real numbers) was independent of the ZFC formulation of set theory (the most standard set of axioms used in today's set theory) in 1963.

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

#162

Post by galaxyLogic »

Certainly everybody believes that Godel's theorems are true. But I wonder if its' Achilles heel is the notion of "stepping outside" of the formal system.

Can we formalize what "stepping outside" means? How can we be sure we have done it correctly? When we step "outside" and do reasoning, are we doing it following the formal logic? Which logic? Are there rules as to what kind of inferences are NOT allowed when reasoning "outside of the system"?

In other words when we "reason outside of the formal system" we are using English. Can we trust the logic of English is "correct"?

Can a formal system really do self-reference? It's just strings. WE can give an interpretation to formal sentences but when we interpret a given sentence as referring to "itself" doesn't it really refers to the interpretation, not to "itself" but its interpretation?

When natural language refers to the formal system doesn't it really just refer to what the formal system "means" in the natural language, not to the formal system itself as such?

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

#163

Post by schoen »

thayne wrote: post #161
DontchaKnowit wrote: post #149

Earlier quoted context omitted.

This is super interesting. Was not aware of this. Is there a proof that this is not provable?

Yes, Paul Cohen proved that the continuum hypothesis (that there is no set with cardinality between that of natural numbers and real numbers) was independent of the ZFC formulation of set theory (the most standard set of axioms used in today's set theory) in 1963.

More about this on Wikipedia:

https://en.wikipedia.org/wiki/Continuum_hypothesis#Independe...

Also:

https://en.wikipedia.org/wiki/Axiom_of_choice#Independence

And thanks to Wikipedia for this elaborate list:

https://en.wikipedia.org/wiki/List_of_statements_independent...

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

#164

Post by lmm »

SkyBelow wrote: post #48
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…

Is there a distinction between saying a system has something that is provable and untrue and saying the system is self contradictory (and the more generalized layman interpretation that the system is wrong).

Yes, very much so. I think of the incompleteness theorem as saying that the language of mathematics is rich enough to express questions that are too complex to answer. That's a lot less worrying than there being contradictions (questions that we can prove are both false and true).

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

#165

Post by schoen »

thayne wrote: post #145
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?

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 they were initially less relevant to our interests and our day-to-day lives).

* We are actually ultimately thinking about one or the other of them, or are in some sense in one or the other mathematical universe, but we don't know enough about our intuition about the reals to be able to specify or explain which one. (Maybe we need other properties whose obviousness or relevance humanity is not smart enough to notice?)

* Some finitist or ultrafinitist approach is actually right: the real numbers are a formalism that, while reasonably motivated by historical attempts to "complete" mathematics in various ways, doesn't correspond to anything Platonically real or to anything intellectually relevant to humanity. (In this account, there is potentially no answer to the question because the real numbers don't exist at all. Neither CH nor ¬CH refers to a mathematical reality, just to games about formalisms.)

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

#166

Post by lmm »

galaxyLogic wrote: post #162

Certainly everybody believes that Godel's theorems are true. But I wonder if its' Achilles heel is the notion of "stepping outside" of the formal system. Can we formalize what "stepping outside" means? How can we be sure we have done it correctly? When we step "outside" and do reasoning, are we doing it following the formal logic? Which logic? Are there rules as to what kind of inferences are NOT allowed when reasoni…

We can absolutely reason formally from outside a formal system, by embedding it in a larger one, and this is a very standard and normal technique that anyone working seriously in this area does all the time. E.g. you work in ZFC + some large cardinal assumption that allows you to construct a model of ZFC inside that system, and then reason formally about ZFC there.

> WE can give an interpretation to formal sentences but when we interpret a given sentence as referring to "itself" doesn't it really refers to the interpretation, not to "itself" but its interpretation?

Indeed it can't - see e.g. Löb's theorem. A formal system can manipulate a set of rules that might happen to be its own rules, but it can never "know" that those are in fact its own rules. Which makes sense when you think about it.

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

#167

Post by danbmil99 »

danbmil99 wrote: post #2

An incredible piece of work. Shaped my life trajectory in many ways. Introduced me to thinkers like Daniel Dennett and Stanislaw Lem. Every generation or so a book comes along that, in retrospect, seems almost clairvoyant. This is one of those books.

Other posters correct, those authors were mentioned in the Mind's I, but I never would have read that unless I started with GDB

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

#168

Post by pfortuny »

quantum_state wrote: post #102
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…

what if the proofs cannot be described as finite or countable sets that does not render a straightforward application of diagonalization? What happens to Goedel’s theorem then?

That is not a “proof” in the statement of Gödel’s theorem.

A proof (there) is just a finite number of symbols which happens to have a specifix form (A=>B AND A), where A and B are sentences, which are finite sequences of symbols having a slecific form… Wait, I am telling you a half of what Gödel did to prove his result.

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

#169

Post by mjan22640 »

Kranar wrote: post #77
gerdesj wrote: post #69

Earlier quoted context omitted.

"This statement is false". GEB is a marvellous work that is accessible to anyone with reasonably good school grade maths. I chanced upon it by accident in the school library one day and was hooked after a few pages. Anyway the crux of the matter is that you can very carefully construct a statement about a system that can't be either proven or disproven by that system! I don't have anything like the formal knowledge t…

>"This statement is false". Close but not quite as that's an inconsistent statement. "This statement is unprovable." is the approach Godel takes and eliminates the inconsistency. Either that statement is true, in which case it's unprovable, or it's false in which case there exists a proof of a false statement.

It is still a paradox, a two step one, that drags the whole system into being a paradox. The false statements that have a proof do already abstractly exist.

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

#170

Post by layer8 »

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?

If the statement “This statement cannot be proven” cannot be proven in the system, does that make the statement untrue just because it cannot be proven in the system? Seems not.

Truth is defined by a model or interpretation of the system, not by the system. As TFA explains, the Incompleteness Theorem showed that truth and provability must be considered as separate notions.

Post reply on HN