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

231–240 of 252 posts

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

#231

Post by cruegge »

cruegge wrote: post #215
bedman12345 wrote: post #208

Earlier quoted context omitted.

You simply use "intuitive mathematics", in other words: no formalization. That's at least what I got when I read books on set theory. Löwenheim-Skolem implies the existence of a countable model of ZFC. https://en.m.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skole... "What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in mor…

I see. Checking the formulation of the incompleteness theorem again, I noticed that I probably misunderstood something here: it indeed essentially requires proofs to be verifyable, which second order theories do not provide. So second order PA can (and in fact does) have a proof of every statement or its negation, without contradicting incompleteness, but provability is somewhat useless in this case. For theories tha…

Ok, the more I try to understand this, the more confused I get. Probably just scrap everything I said, I'll need to do some more reading.

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

#232

Post by bo1024 »

cruegge wrote: post #215
bedman12345 wrote: post #208

Earlier quoted context omitted.

You simply use "intuitive mathematics", in other words: no formalization. That's at least what I got when I read books on set theory. Löwenheim-Skolem implies the existence of a countable model of ZFC. https://en.m.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skole... "What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in mor…

I see. Checking the formulation of the incompleteness theorem again, I noticed that I probably misunderstood something here: it indeed essentially requires proofs to be verifyable, which second order theories do not provide. So second order PA can (and in fact does) have a proof of every statement or its negation, without contradicting incompleteness, but provability is somewhat useless in this case. For theories tha…

This was all a helpful/interesting discussion!

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

#233

Post by danbmil99 »

danbmil99 wrote: post #167
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

G. E. B.

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

#234

Post by Kranar »

mjan22640 wrote: post #169
Kranar wrote: post #77

Earlier quoted context omitted.

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

There is no paradox in the statement "This sentence has no proof."

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

#235

Post by adastra22 »

thrwycct123 wrote: post #230
adastra22 wrote: post #202

Earlier quoted context omitted.

Please try to give the people you talk to the benefit of the doubt, and read carefully what you are responding to. My training is as an applied physicist. We physicists have an interesting relationship with math. Obviously math is essential to the work that we do, but the physical world decides whether the math is right, not the other way around. Our mathematical models technically permit things like negative mass, t…

> Obviously math is essential to the work that we do, but the physical world decides whether the math is right, not the other way arounnd That was the belief before the 1800s. But with the discovery of non-euclidean geometry, math has been divorced from the physical world. Math is simply a system of axioms and proofs. Math is purely abstract and logical. Whatever math that physicists use just simply happens to align…

The question “does this have relevant applications?” Is still well formed and answerable. That’s all I’m asking! I find it odd that so many are taking offense.

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

#236

Post by lmm »

galaxyLogic wrote: post #229
lmm wrote: post #166

Earlier quoted context omitted.

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…

Yes, very interesting point. It can not know that they are its own rules. BUT we can know that. Therefore we the meta-level can reason about the subject more than it can of itself. For example the subject-system can not mechanically prove that it is looking at its own ruleset. So the term "unprovable" should probably best be always qualified with: in which system. There are facts about systems which the system itself…

> There are facts about systems which the system itself can not prove. Statements like that can be expressed in some formalized subset of English and proven following the rules of that formalized English. What is that "formalized English" that we use in our reasoning? Or does it not matter?

Again, the normal, routine thing is to just use a slightly larger formal system to work with them. But it really doesn't matter.

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

#237

Post by trashtester »

black_knight wrote: post #213
trashtester wrote: post #205

Earlier quoted context omitted.

Undecided is not quite the same as true. My understanding is that there can be statements that are necessarily true within a given set of axioms, but still unprovable using a proof of limited length.

Not sure what you are thinking of here. In first order logic if something is true in all models it is also provable. This is called completeness. And is one of the sanity requirements of a semantics.

I was thinking that something could be true and undecidable (as for the halting problem).

I'm somewhat on thin ice on the mathetematical formulation, but I suppose something could be undecidable but true with respect to all standard models of a theory, while not true for some non-standard model.

For instance, there may be statements acting on infinite sets (such as N) that may not be compressed into a recoursive formulation, which means that a proof of the valididity of the statement (if it is true) would require an infinite number of steps.

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

#238

Post by trashtester »

kubanczyk wrote: post #209
trashtester wrote: post #204

Earlier quoted context omitted.

> Nope: demonstrating that (the opposite of Goldbach’s conjecture) is unprovable is logically equivalent to demonstrating that (Goldbach’s conjecture) is unprovable. It means we’ll never know either way. I think this is false. If you find a number N that is not the sum of two primes, you did disprove Goldbach's conjecture. Any such number would be smaller than infinity, and so there would only be a finite set of prim…

> if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE Yes, you can. Math is not physics. Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe. The trick is that "the universe" is not the physical universe, it's just a choice of axioms.

> Pythagoras was able to prove his theorem about every triangle in the universe without inspecting every triangle in the universe.

My understanding is that statements about members of infinite sets can be decidable if there exists a method to set up use recoursion/induction to cover all of them. For the set of right triangles, this is relatively straight forward (if we ignore the complexity introduced by real numbers).

For statements on infinite sets where it is not possible to reduce a proof to such recoursion/induction, you quickly end up needing an infinite number of steps to cover all cases, meaning the problem is undeciable/uncomputable.

See the Church-Turing thesis: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

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

#239

Post by gerdesj »

BurningFrog wrote: post #112
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" My take on that statement is that it is not saying anything about the world. It only refers to itself, making it a self-contained mini-universe with no relation to the real world. So, since it's not saying anything, it's neither true nor false. Only something confusing that feels like it should have some meaning.

There are several levels that you can analyse this. Firstly: Is it English and is it grammatically correct? Seems OK but we can allow English to be a bit slack.

Now, how do we attach meaning to the actual statement. Do the English words actually mean the same thing to me as they do to you? Probably.

Should any statement be applicable to anything - world or otherwise? It is just a statement and not my best man's speech at my brother's wedding 25 odd years ago, which I'm sure you can appreciate that I consider that being rather more important.

So here we have a statement that is unable to be consistent and as you say, it sounds like it should have meaning but doesn't.

So we have a way of saying things with spoken language that are logically inconsistent that are also grammatically correct and that is a sort of flavour of what Goedel proved with his incompleteness theorem.

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

#240

Post by patcon »

widowlark wrote: post #103
patcon wrote: post #99

Earlier quoted context omitted.

thanks for responding! i might feel a bit differently, but I think I hear where you're coming from: that it does a disservice to great people when we flippantly imply their greatness originates from simplistic things outside themselves (if I'm still way off, feel free to correct, but pls don't feel obligated to engage :) )

That might be a good way of putting it. I think also that the question to me implied a cynicism about how people can be curious and creative while also being scientific, but the original commenter has already clarified they did not intend this interpretation at all

i like you. that is all
Post reply on HN