> 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 prefer to have true things that can't be proven rather than provable things that are untrue. But either is possible.
> > 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 cannot distinguish statements of Peano Arithmetic (eg, 1+1=2 and 1+1=3 are both provable), and hence is not sufficiently rich.
That's a somewhat unintuitive way of looking at it in practice, though.
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.
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 integers.
A *proof* of Goldbach's conjecture consists of a finite number of formal reasoning steps that start with some axioms and end up at the statement of the result.
To this day, it seems as though Goldbach's conjecture is true. It holds for every number we've been able to test. However, no one has proved it is true or false yet (or proved that it is unprovable).
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.
It's kind of confusing at first, but there is an easier way to get an intuition why there might be true statements that cannot be proved. 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). Proofs are finite chains of finite statements so there are only countably infinitely many of these. Therefore there must be subsets/statements that are true that do not have a matching proof.
The approach that Gödel's proof takes is not too different to the above argument – it is essentially a diagonalization argument – the complexity is in making the encoding of statements are numbers very precise.
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 mathematicians (including the likes of Euler) that have applied themselves to this problem. An odd contradiction!
I do believe this opinion places you very high on the 'confidence' axis, but not especially far along the 'competence' axis.
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.
> 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. Parent comment which I was replying to talks about both.
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...)
I understand precisely what adastra22 meant from the moment I read it. Unfortunately two people now have rushed to unkind characteristics of what that (perfectly sensible) meaning was.
sure, what was written was sensible but has no bearing on the proof. speculation isn't critical thinking, as adastra22 says, be careful to what you are responding to. my point is the lack of rigor and understanding because the proof isnt being discussed, hand waving about an unread and very important mathematical work is irresponsible. thats MY point
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, time flowing backwards, or magnetic monopoles. But that doesn't mean tachyons, time machines, or fundamental magnetic particles exist--they don't, so far as we know. So I'm trained to actively disregard non-physical, not relevant mathematical implications. I'm sorry if this offends a pure mathematicians sensibilities, but pragmatically it is very useful.
Or take a different field: in computational semantics, a branch of formal linguistics, there are many models for inferring a formal logical statement from an example written sentence or spoken utterance, and then determining the validity (truth) of the statement. These models get caught up on stuff like "This sentence is false." What's the truth value for that sentence? If it is true then it must be false, and if it is false then it must be true. Error, validity of this statement can't be determined! But hey, it turns out that in practice this basically never happens unless the speaker is really confused, misspeaks, or deliberately evasive. Real sentences don't have this self-referential, circular logic structure because that's not how people think or communicate.
Now "this sentence is false" goes back to the greeks, IIRC, and Gödel's theorem is slightly different. Gödel's main work is in the formalization of proofs and proof systems, and I don't want to take away from that in any way. But the incompleteness theorem always seems to be explained through these sorts of self-referential examples and I have yet to ever see it reduced to a practical problem with real-world implications. Hence my question. Does Gödel's incompleteness theorem actually constrain a real world application of proof systems, where we tend to be interested in non-cyclical logical arguments?
> 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 with the physical world.
Also, the physical world doesn't confirm whether the math is "right". Math is deductive, not inductive. As long as the math is derivable from the axioms, it is right. The physical world/experiments determine whether the mathematical model aligns with the physical world. The physical world has no say in math. Not anymore.
> So I'm trained to actively disregard non-physical, not relevant mathematical implications.
In the past, when a mathematical model predicted something ( relativity to quantum physics to elements ), experiments were conducted to determine whether the models aligned with the physical world. If the mathematical models make predictions that physicists currently can't verify with experiments, should we disregard it? Do we need technology to advance to where we can conduct experiments. Do we need physics to become more abstract? Perhaps model the physical world in the virtual world. Would experiments in the virtual world be applicable to physics? Seems like physics is both at a dead-end and on the cusp of a revolution.
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.
If your question is "does Gödel Incompleteness have practical applications", my answer is "probably". Not necessarily directly, but indirectly it has inspired much other work.
One of the things it inspired was Turing's work on uncomputable numbers. It turns out that computability and incompleteness are intertwined, which at least I find interesting. And without the "uncomputable numbers" malarkey, I wonder if the Turing Machine formalism would exist (answer, "probably, but maybe looking different and with another name"). And, well, the Halting Problem is essentially Gödel Incompleteness (imagine handwaving here).
As for proof systems, again, the answer is "probably". Knowing that there are true, unprovable, statements in a formalism is something that informs how you approach it, you need to put a limit on how far to go before you say "I don't know" and taht is in and of itself important.
still doesn't sound like you have ever read the proof, nor about it. so aren't you engaged in this discussion strictly by speculation? logical fallacy? just because you have some point to make has no bearing on the work you are adjacent to and not actually discussing. making your own points and arguments about logical gotchas is great, has nothing to do with critically understanding a work you haven't read. asking for giving the 'benefit of the doubt' to speculation informed only by a comment section is ridiculous. do your homework before asking for generous responses to your internet quibbling
I'm late to the party, so I'm not sure you'll see this. Hope you do. Different people will each have their own contexts and their own concepts of "useful" or "interesting". I'm making assumptions about yours ... apologies if I misrepresent you.
The proof of Gödel's result uses the paradoxical statement "This statement is false", but that's being used to prove this very general result about all systems. So the hunt is then on to find "natural" statements that are True but Unprovable.
But the "unprovable" bit should more completely be stated as "unprovable in a specific axiomatic proof system". If we want to prove that statement S is "True but Unprovable" then we must actually prove that it's true. So if we've proved it's true, what does it mean to say it's unprovable? We just proved it! What's going on?
So let's take a specific example.
Peano Arithmetic (PA)[0] is an axiomatic proof system intended to capture Natural Numbers and their behaviour.
The "Goodstein Sequence" G(m) of a number m is a sequence of natural numbers ... you can find the definition here[1]. It's not hard, but it's longer than I want to reproduce here.
Goodstein's Theorem (GT) says that for every integer m greater than 0, G(m) is eventually zero.
It has been proven that GT cannot be proved in PA, but it can be proved in stronger systems, such as second-order arithmetic.
So the statement of GT is not self-referential, along the lines of "This Statement Is False" sort of thing. It's an actual statement about the behaviour of integers, so it's not a self-referential trick.
Your question now is: What's the point? How is this useful or relevant?
Much of modern (pure) mathematics is chasing things because the mathematicians find them interesting. The vast, vast majority will never, of themselves, be useful by (what I expect are) your standards.
But it was once thought that factoring integers was of no practical use, and only pursued or investigated by cranks. Imaginary Numbers were thought to be bizarre, useless, and dangerous. Non-Euclidean Geometry was thought to be utter nonsense, and held up as part of the "proof" that the fifth postulate was unnecessary and was deducible from the other four. All three of these now form critical components in modern technology.
Even more, to the average person on the street, anything to do with algebra is completely pointless.
For you, Gödel's theorem is completely pointless and useless and probably of no interest at all, but it helps us understand the limitations of formal systems. The techniques that have been developed in the time since it was proved have helped us understand more about what computer verification systems might or might not be able to accomplish.
Of itself, Gödel's theorem might not be of direct, immediate, and practical use, but the work it has inspired has tangentially been useful, and may yet be moreso.
But not for everyone. After all, some people don't care about the Mona Lisa, or Beethoven's Fifth Symphony, or Michaelangelo's David, or the fact that people have walked on the Moon, so why should people care about results in Pure Mathematics?
That's the thing about Pure Mathematics. Sometimes it ends up being useful in ways we never expected.
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 those statements as an axiom), but you will still have other statements that you can't prove.
> 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.)
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`.
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.
My understanding is this: Gödel proved his earth shattering result in the 1930s. Then the dust settled and mathematicians thought it might be “academic” and that mathematics might not come tumbling down after all. Then in the 1960s Paul Cohen proves that the continuum hypothesis is undecidable. That is, we will never know whether an infinite set can have a cardinality between the natural numbers and the real numbers.
My understanding comes from Keith Devlin’s wonderful book “Mathematics: A new golden age”.
Harvey Friedman, one of the most renowned contemporary logicians, has a research program devoted to finding such examples as those you seem to be looking for.
This article presents his views: https://nautil.us/this-man-is-about-to-blow-up-mathematics-2...
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.
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.
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.
At this point I feel like you're going from a reasonable question about Godel's theorem to cranky person unwilling to see how any math that doesn't explain how to fly a 747 is relevant to the world.
There are huge branches of mathematics that don't find immediate practicality in physics. Often these end up being practical in cryptography or quantum mechanics, but sometimes they don't. But to dismiss the entire field that relates to the cardinality of real numbers as uninteresting if someone can't give you a practical application of it shows a simple disregard for other fields of study.
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.
> What do we actually mean by saying "statement S is unprovable"? Do we mean "there is no [edited:] proof 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"?
By “converse” I think you mean “negation”.
A statement being unprovable means we will never know whether it is this or false.
> 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!).
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.
> 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 primes smaller it to check for.
So basically, if Goldbach's conjecture turns out to be false it IS going to be PROVABLY false.
Only if Goldbach's conjecture is actually true will it be the case that it is impossible to prove its negation. But if it is ALSO unprovable (but STILL true) you will NOT be able to prove that the negation is unprovable, because that would mean that there doesn't exist ANY number N that disproves the conjecture, so would prove the unprovable original conjecture....
Consider the statement "All swans are white", but you live in a universe with an infinite number of swans.
Lets assume that there exists at least one black swan. Proving the statement false is trivial once you find the first black swan.
However, if all swans in the given universe ARE white, and you have no way of inspecting every one, you can never PROVE that they are all white. Also you can NOT prove that it is impossible to prove the negation.
> 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.
> 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!).
Lets hypothetize that Goldbach's conjecture is true and unprovable (let's call it S1). In that case, the following statments are both true:
C1) It is impossible to prove S1.
C2) It is impossible to prove the converse of S1. (since in this case S1 is true, the converse is actually false, so cannot be proven).
Now, if we go into meta-proofs, we may be able to prove C1 (whether or not S1 is true). But we will never be able to prove C2 (if S1 is true and unprovable, C2 will also be true and unprovable).
Now, if S1 is actually false, We may actually at some point find a proof of that. But that's not really so interesting.
The interesting part is that there DOES exist statements like this that ARE true AND unprovable (even if we don't know which statments), we just don't know WHAT statments those are.
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.
Any visual geometric proof. You can build an uncountably infinite set of different sized variations proving the same underlying relationships like this: https://youtu.be/CAkMUdeB06o
Whether or not a visual demonstration like that is actually a “proof” is a separate question. It definitely wouldn’t satisfy Hilbert, and doesn’t meet this definition:
> A proof of a statement S is a finite sequence of assertions S(1), S(2), … S(n) such that S(n) = S and each S(i) is either an axiom or else follows from one or more of the preceding statements S(1), …, S(i-1) by a direct application of a valid rule of inference.
I also don’t know of any visual “proof” like that which can’t be explained much more rigorously and powerfully with a formal set of assertions. But pulling threads like this and really asking what makes a proof a “proof” are some of the deepest questions I think a person can ask. It’s worth doing if only to appreciate what an incredible accomplishment all of the formal set theory work is in unifying and attempting to define meta concepts like “proof” itself.
> 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 (they used more than just visual intuition/they also used more rigorous and formal propositions than that water thing, but they were visual and didn’t involve finite sets)
That’s a really deep question. If our brains are like digital computers, then yes, that’d be true. But they could be like analog computers, quantum computers, or something we don’t yet have the ability to describe.
The problem with this theory is: what is the part of a geometric proof which cannot be described or validated using a classical, discrete computer? There is no such step. All parts of mathematics which mathematicians are able to agree on can be so described. There is no scope for our brains taking in an analog measurement, doing an analog measurement step on it, and using it to confirm the truth of a mathematical statement.
Of course, this is not an argument that our brains are absolutely finite and classical. Perhaps analog computations is required for an appreciation of beauty, or quantum physics is necessary for us to fall in love. But we seem to be able to check math proofs without them.
I think mathematical intuition might be some kind of weird analog calculation, but yes, I can’t think of an actual visual proof that cannot also be described in discrete formal terms and validated with a computer. There might be examples out there somewhere, but I don’t know of any.
Not aware of how to provide one due to constraint of the discrete nature of the language would have been used to describe the example … however, imagine entities that are able to communicate via continuous means … they would be able to … but would we be able to find ways to get it?
At 13:46 it gets into the "is there a way to prove every complete statement?" and furthermore goes into the Godel math for "there is no proof for the statement with Gödel number g" where that statement itself has a number "g".
The entire video is a good watch though.
And the related problem is that with Godel we don't know if math is consistent either.
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 to really get to grips with it and the discussions on infinities and so on are pretty mind blowing. However, you feel that DH is imparting glimpses into the sheer beauty of the ideas he covers.
Wait 'til you discover what ricercar and quining is all about - bloody lovely. Just read it but take your time. There is something in there for everyone. You often get told by clever people about the links between maths, music and art. Mr H easily gives the best argument I've ever seen that attests to that being true, whilst giving your brain a right good kicking.
There was a Dutchman, a German and an Austrian who walked into a book ...
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 obeys all the "laws" (OK vagaries) of English grammar. There is nothing in the rules of grammar that requires a statement in English to actually be self-consistent. The problem only surfaces once you attach the associated meanings to the various components.
I just picked a classic to start off my prior comment which morphed more into praise for GEB than Goedel's brain breaker.
I have dim memories of a cracking constructive argument starting off with some very basic axioms where one was written as S, and two as SS and so on, then it all went a bit mad but the genius of Hofstadter is to make all that impenetrable palava nigh on accessible to the layman (with a bit of effort from the reader).
The horrendous thing about Goedel is that the final flourish is clearly correct (I assume that responsible adults have filled in the formal bits, I'm sticking to the lies to children version). It is both terrifying and perhaps obvious at the same time. I can imagine the sense of dread when mighty edifices such as Herr Hilbert's suddenly looked a bit shady and then anger, followed by disbelief and finally acceptance as the big hitters really got to grips with it. The world hasn't come to an end because of Goedel but it certainly got a bit more interesting.
I think that it is almost comforting that we have a system that can be complicated enough be to capable of saying things about itself that can't be proven within itself. I think that there is a good chance that our system of mathematics will eventually become complicated enough and no more. Obviously there will always be spherical cows and some absolutely mad numbers and when I say eventually - that will take forever (nearly).
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.
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.
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.
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.
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 more general conditions.
Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?
"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 more general conditions." I can't give a clean rebuttal for this, but I believe this to be profoundly mistaken. It might be technically correct though, depending on how you'd formalize this statement.
To formalize math you need a logic that has some properties: it should be decidable whether a proof is correct, you should be able to write it down, it should not be contradictory. If you take these together the only way a statement is unprovable, is if it is independent from the axioms, i.e. there exist multiple models.
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 that fit the conditions you listed, unprovability is indeed due to multiple models. Does that make sense?
Edit: however, consistent second order theories don't always have a model. In first order, if S is an undecideable statement in theory T, then both T+S and T+!S have models, both of which are models for T, so undecideable statements always come from multiple models. But that does not need to be the case in second order, so your claim "it is independent from the axioms, i.e. there exist multiple models" is not neccessarily true, i.e. there may be cases when decideability of some statement fails in a theory with a unique model. Or is there another argument for your claim?
Forgive me for spamming questions, I just try to understand how these things fit together. But maybe we should just stick to first order, since everything else is too weird anyway.
Good question! In this context, we're relating a system of proofs to the properties of a desired model. If you start from a sufficiently expressive model and try to design a proof system where valid proofs correspond to true properties, then you will either miss some properties (an unproveable truth) or you will have too many proofs (proveable falsehoods).
Without biasing for a particular model, we could simply say that every sufficiently expressive proof system admits either zero models or more than one model.
We can define a notion of complexity for any given integer as being the size of the smallest program that returns that integer. Obviously, I'm being imprecise here, but it should hopefully be clear that it is possible to get the details right and the precise nature of those details aren't going to be relevant for what follows.
Now suppose we have a program that can find the complexity of a given integer. Then, we can write the following program:
for (i = 0; ; i++) {
if (complexity(i) > 2*K) {
return i;
}
}
(where K is the size of this program). Now we have a contradiction: we've constructed a program of size K that computes an integer i, but the smallest program that can do so is of size 2*K. This means that one of our assumptions is wrong, and the only one that can be wrong is that we could write a program that computes complexity.
As a result, we have some integer that has a complexity--it's still well-defined (at least if you have the axiom of choice, but I'm not sure if that axiom is necessary)--but we can't necessarily prove that any integer has a given complexity.
Any statement that can be made from the Peano axioms that is provable in ZFC is provable in ZF without C. So the axiom of choice should be irrelevant.
However we can write a program that does a brute force search through all proofs from ZF looking for the complexity of i. As you just showed, this program will not establish the complexity of all integers.
But how does it fail? It fails because there are programs which do not halt, that it can't prove don't halt, which if they halted COULD return i.
And therefore the complexity cannot be determined from ZF.
The prevailing philosophy of mathematics says it is well-defined. But there are alternate (entirely consistent!) philosophies under which complexity is not well-defined at all.
I feel like I'm missing something here - wouldn't the shortest program that returns the integer i just be "return i"? The length of that seems pretty easy to compute.
If you are a platonist and believe in some preferred model where every statement is decided this makes perfect sense. For the rest of us, this just means that in a sufficiently complex system there will be undecided statements. Which is not such a big surprise – but a rather awesome technical exercise!
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.
> 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.
The term "standard model" is interesting, because it pushes the problem a bit. So, let us take the natural numbers. Sure, we can prove in set theory that some of the undecided statements of Peano arithmetic are true for the standard model. But seen from the outside this means that we have changed our axiomatic system from Peano arithmetic to set theory. But there are still undecided statements – even arithmetic ones – in this new system! These will hold in some models of set theory, while being false in some other.
So, saying “Oh, I mean the standard ℕ, not any of those other ones” does not get us off the hook, because it raises the question: “The standard ℕ... in which model of ZF?”
So "famous" undecidable statements, which is what you mention, are an example of statements that strongly opinionated people believe enough that are probably true but unprovable. You are probably familiar with the Continuum Hypothesis or the Axiom of Choice, the latter being so "probably true" in the model that the axioms for set theory try to capture that it's usually added as another axiom.
Kruskal's tree theorem is a more interesting example, you should look into that. You can prove it undecidable, so you can add either it or it's negation like you say, in Peano's arithmetic, but you can prove it ZFC or I think even less expressive axiomatic systems for set theory.
Yes, you can add more axioms and produce a more powerful system which can resolve more questions. In some cases you actually have a choice about whether to assume that something is true or that it's false (for example you can assume the continuum hypothesis or its negation!), and neither choice on its own produces an inconsistency, but either choice makes a different set of conclusions provable.
However, Gödel made explicit in the very first statement of his incompleteness theorem that assuming more axioms cannot ever eliminate incompleteness (except by the extremely undesirable event of eliminating consistency). Gödel shows that, if a set of axioms (including additional axioms on top of your original set) doesn't allow you to prove everything (by virtue of being inconsistent, something called the "principle of explosion"), then there are necessarily statements that those axioms can't resolve the truth of.
So you can add more axioms and that will either make your system more powerful or inconsistent (depending on whether you chose inconsistent axioms to add), but you still can't get rid of the incompleteness phenomenon that way!
True, but if you add too many axioms, the resulting set of axioms will not be computable anymore. If you allow your set of axioms to not be computable you can of course just use the set of statements that are true for whatever model of the natural numbers you have in mind. The whole point is that it's not possible to write down any sensible definition of what natural numbers are supposed to be.
Because as soon as you have a system that includes that new axiom, _new_ true statements can be created that are not provable. It's true for every formal system with any finite number of axioms.
The caveat is that it's a rule of _formal systems_. Any formal system that can represent multiplication can be shown to have unreachable truths or provable falsities.
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).
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.
Wouldn't the 'truth' of a statement be depending upon the axioms of where you are making the statement. Thus something proven is true and if the negation is proven it is false, and thus a system able to prove both is self contradictory and even basic logic no longer applies, thus we lose any real world application.
The opposite a system which has true statements we can't prove is still useful, even if there might be some problems we won't ever be able to solve. But a system which can prove both a statement and its negation loses meaning.
Or does it? Naïve set theory, despite Russel's paradox, and language in general, despite the local equivalent of "This statement is a lie." is still a useful tool, so maybe the same applies even to more formal systems?
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.
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.
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.
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).
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 that system. But can someone sum up how this connects to consciousness beyond the obvious way in which consciousness plays the role of the interpreter? Or is that itself the thesis of the book? Or maybe that consciousness is the originator of self-reference?
Bottom line is that I think the thesis can be summed up in a few sentences, but apparently it takes a whole 800 page book to get to the point. Would love other people's thoughts on what that point is ultimately. By the way, as salty as I sound about it, I love GEB. So don't get me wrong :).
I think of it more as a survey of a bunch of disciplines, and some hopeful hypothesis of future AI research.
He writes in an accessible way and touches DNA, poetry, fractals, video feedback, topographical systems, just... a whole bunch of things.
It is for sure reaching, but his core conceit is about pattern recognition and emergent behavior and he throws everything he's got at the wall there through the eyes of his interests because he KNOWS there is something there, even if Godel could describe it in a 19 page paper decades before.
That some of this is obvious in hindsight almost 50 years later does not discredit the bizarrely singular nature of his effort, maybe the same way Seinfeld seems corny now.
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?"
It is interesting to me that the author would start at the materialist assumption. Most people take it as a “given”, but I have softened to the idea that maybe it is not a correct or complete way of viewing things.
The author's favorite topic, as described by him in the final Dialogue, is 'indirect self-reference'. This has a double meaning. Indirect self-reference can mean what it says such as Godel numbering which is a method of referring to a self indirectly but it can also mean that the whole book is an indirect way of referring to the question of 'what is a self?' He is approaching the topic of consciousness indirectly.
I disagree that most people would take materialism as a given (I think most people in the world are at least slightly religious or spiritual), nor do I think it's necessarily a correct reading to say that Hofstadter actually assumes materialism must be true (though I believe he does), rather Hofstadter starts from the premise that it is and then tries to see if that premise can be logically consistant.
In the forward of which, Hofstadter says he could have called the book, "I" is a Strange Loop referring to the concept of "I-ness", but he found it too clunky.
Haven't read it in a decade (and only once!), but I'd say its about how self-reference, and roles + perspectives are consciousness. The exception proves the rule, getting into the mind-bending edge cases exposes the typical mental framing. A bit like Leonardo exploring his eye muscles with a blunt pin.
Godel, quines, the phonograph ship of theseus stuff, Bach harmonies, all the self-aware dialogues. He's looking for the vital spark, the thing that makes us greater than the sum of parts. But he can't capture the essence (who can?), and settles for running around
the outskirts.
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.
Penrose's issue is that most mathematicians have disagreed with his understanding of Godel's theorem. He basically wants to say "A computer by definition can't know that a "Godel statement" is true, and yet I do, and therefore my mind can't be a computer."
Yet Godel's theorem is entirely formal and understandable by a computer, which can draw the same conclusions about any such statement as a human.
Metamagical Themas is worth checking out for that style of reading as it is a compilation of his essays. One can pick and choose any to read but there's overarching themes that bring them together too.
100%, not just the collection of columns, but that he has postscripts for it. He manahes to keep things accessible over a few columns rather than the overly sprawling GEB (which I've read a few times, and still revisit pieces) or his later personal works, which involve a lot of personal grief in the guise of discussions of cognitive studies.
He's said he wasn't great at conveying the thesis in GEB. If you want the thesis of GEB, you can read "A Strange Loop." It's a bit more narrative, less technical but still pretty good book, imo.
Others have pointed out what the core argument of the book is, so I'll point to the spot where I believe the thesis is stated most clearly (p. 709 in my copy,
the 1980 Vintage Books paperback edition):
"My belief is that the explanations of 'emergent' phenomena in our brains--for instance, ideas, hopes, images, analogies, and finally consciousness and free will--are based on a kind of Strange Loop, an interaction between levels in which the top level reaches back down towards the bottom level and influences it, while at the same time being itself determined by the bottom level. ...The self comes into being at the moment is has the power to reflect itself."
The book is about... should I call it golemization? the emergence of a being from a summation of non-being things.
Few people get it like that and I think it's a problem with the book. It's taken as more of a funny and poignant popular science dive into some aspects of logic and computability. Hofstadter expands on "I Am a Strange Loop" which I think you should read if you are interested into what was his take with GEB.
I think his "specific thesis" is an argument that intelligence (and he includes consciousness) are algorithmic. I think he fails to make that case; but the journey he leads us on is extremely entertaining. The book's a masterpiece.
Am I the only one who did not find this book that interesting? I studied CS so it just felt like reading my class textbooks again, except with random trippy stories in between that try to shoehorn theory into a poor metaphor.
The fundamentals of CS (strings, automata, graphs) are elementary building blocks. This is by design. You can apply them to almost anything. Almost everything "is a graph", or "recursion" if you formulate them to be so.
The point isn't that everything is recursive - the point is that systems that are recursive / self-referential cause breakdowns in logic (they are incomplete).
This is a deep philosophical insight - it rhymes with the Buddhist idea of no-self - the problems that arise because we hold onto a false sense of self.
I read it before studying cs and I thought it was fascinating and made me want to study it. After studying it at the grad school level I re read it and found the book somewhat pedantic. It’s a bit like the black swan in the regard: it package advanced under grad level stem topics with colorful anecdotes and musings.
Some of the comments here make me want to read it again, but the first time through I got bored. It kept geeking out about recursion for so laboriously long that I felt like maybe it was written in a different time for people who hadn’t already studied thunks and y-combinators and quines in school. I’m sure it was a journey of discovery in the 70s, but it felt like a lot of the ideas that made it famous had already seeped into my education and spoiled the book for me. I’m not sure exactly how much of it I read, I thought maybe two thirds, and it sounds like I either didn’t read or didn’t understand some of the themes in the book.
Middle ground opinion here. I found roughly the first third of GEB interesting. It's mind-expanding to think about self-reference and recursive structure in the context of all the other fields besides computer science, like natural language, music, art. GEB is a fun exploration of that for the first few chapters... but it doesn't get better after that, after a while it just keeps doing the same things and repeating the same stuff, and becomes a chore rather than fun to get through.
I plowed my way through about two thirds of it. Lots of interesting stuff, but I finally gave up because it seemed just too self-involved and self-referential. Building up this enormous edifice, just to be able to say "Hey! Check out my edifice!"
I guess I'm just too much of an applied engineering kinda guy.
After several unfortunate book purchases I finally realized that the more enthusiastic comments there are about it on HN the more likely I am to not make it past the first three pages.
I started GEB a couple of weeks ago and I have to agree to some extend (I also have a CS background). The information density is low and the authors style of writing feels very self-indulgent and even pretentious. In the foreword of the recent edition he portrays himself as a very petty, narrow-minded and unpleasant person.
But at the same time, when it really gets going I can't help but being swept away and entertained by the unfiltered enthusiasm he displays and the work he has done to put it to paper. It's like a conversation with a very exhausting but at the same time very interesting person. It's like trying to put that tingling in the back of the brain when some kind of insight looms in words.
I feel like it's probably best read as a curious psychograph of a nerd in the seventies who is deeply interested in theoretical computer science and its implications on awareness and (artificial) intelligence. Not as a scientific non-fiction-book which is trying to educate the reader or trying to make a strong argument for something
I think you have to be in the right mindset. Not to say its beyond anyone's level, but I think you have to be in the "mood" to learn about the material. I can assure you, there's been times where I would have hated reading it and times where I wouldn't have been able to put it down.
When I'm more focused on the here and now, I think I would find it a chore to get through. When I feel like I have less on my plate and looking for "interesting observations" it would work really well.
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've never understood why people think it's pretentious. It joyous and innocent. It's someone laying out the shiny baubles they love and inviting anyone passing to take a look.
It is for sure pretentious, he's a cloistered academic classic music nerd that appreciates art exclusively through rigid structure. He's also aware of that and tries to explore that.
The second half is weird too, because it describes the academic work he does in the future, but is a stab in the dark compared to the documentarian aspect of the first half.
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.
You can skip the alternating socratic parts and it is much lighter :P
I think Zen and the art of motorcycle repair has a similar structure with Socratic dialogs interspersed.
I was introduced to both Dennett and Lem through 'The Mind's I: Fantasies And Reflections On Self & Soul', an anthology edited by Hofstadter and Dennett that I chanced upon in the university library. I recognized Hofstadter from GEB. I found 'I' very digestible, I admit that I still haven't finished GEB. It beckons me from the bookshelf.
Intellectually poor man's attempt at a summary of the summary:
Part 1 - math proof that a formal system when evaluated by an agent "breaking out of the system" can use that system to prove itself inconsistent. ("f* up" the internal logic of that system by feeding it into itself)
Part 2 - ironically, to be conscious you have to have an awareness of your own system (a "strange loop") but you'll never be able to understand yourself as proven in part 1.
Every socially awkward person who obsesses about their intellect is an in-depth explainer of Goedel, Escher, Bach. It's a fun read, and clever enough, but the relation between the work of the three is pretty shallow, and if you understand only what the book contains, you haven't gotten very deep into their valuable work. The book is more an act of self-indulgence on the author's part, or at best a tribute to the brilliance of his subjects, than a profound intellectual achievement in itself.
> The book is more an act of self-indulgence on the author's part
That's precisely what it is. And what makes it valuable too: such works of blatant self-indulgence are not very common in mathematics (at least, while remaining enjoyable to read).
> than a profound intellectual achievement in itself
Sure. I would call the book an artistic achievement in the intellectual realm: it talks about ideas, but is art. To put it another way: everyone knows "mathematics is not a spectator sport" — this is usually said in the sense of "you can't learn mathematics unless you do it yourself", which is true enough, but it's also a loss in the sense that there's no equivalent of sitting back and watching a game, watching someone play with ideas and do mathematics. This book comes close. How good the quality of the game is, and whether you'll learn anything from watching the game, is debatable (probably not much), but the experience itself is unusual, which makes the existence of this book a happy circumstance.
IMO, to read GEB for its content would be missing the point: what I think is the greatest thing about the book is that it's simply, purely, Hofstadter having fun. The linked post says "GEB is really idiosyncratic in a way no one can imitate", but I'd put it as: it's a deeply personal book. The author's personality shines through in a way I had not encountered before in a mathematics text, and so the book was a revelation for me.
Hofstadter's actual thesis/intent with the book, and what he has to say about Gödel numbering (note: the book goes over Gödel's theorem and some implications, but Hofstadter's real interest is less in Gödel's theorem than in the proof technique—Gödel numbering—that Gödel used, because he is tickled by the self-reference), or Escher or Bach for that matter, are not really what make the book most worthwhile. What matters is the marriage of form and content, the perfect puns that seem to be set up several hundred pages apart, the way you'd be reading another dialogue before suddenly realizing that the lines are spelling out an acrostic, the satisfaction of things working themselves out perfectly (even the puns) (a feeling similar to the satisfying tying-together of the plots of certain novels, some of Wodehouse's included), and so on.
Very few authors can write about technical topics in a way their personality shines through. (Knuth is another IMO, except with the personality staying in second place to the technical content, while with Hofstadter it's the other way around!)
The original review post focuses on Gödel, but you cannot truly review GEB without Escher and Bach. Yes, self-referentiality is a key theme of Hofstadter, but also recursion, symmetry and the foreground/background ambiguity in visual arts and music, after all the whole book is essentially a recursive, self-similiar poem (alternating chapters with prose and dialogues, one dialogue has palindrome form).
Despite that I disagree about his fundamental view of AI, namely that AI is an emergent epiphenomenon, it is still the most-read and most-appreciated book ever for me. I read it first in German and then in English, and given the playfulness with form versus function/content, it is also the best-translated work that I have ever encountered. I'm grateful that I bought it when I was sixteen, simply because it was mentioned in a computer magazine and in a completely different context, so I got curious. I know many people that deeply appreciate it, or that went into AI careers because of it.
I've never read it, but I can tell it has something deep to say, due to have channeling the knowledge learnings into the production of the knowledge object has brought so much joy and intrigue and life-changing epiphanies to readers. I mean, there must be some deep truth to the content, if the execution of said content (in the form of the book) is so touching to so many people... :)
For one thing, I read GEB and found it difficult to follow. No doubt there is more in GEB than in this article, but without this less lengthy summary I couldn't get at it, life and attention being what they are. If I returned to the book now, I bet I'd understand more of what was already in it.
The ideas and what a modern reading brings to them can be difficult to disentangle. A more charitable take might be that because emergence is fractal that there are uncountable ways not involving Hegel to arrive at and express a similar underlying idea.
Hegel and Hofstadter seem to be trying to find "spirit". To keep it simple, spirit can be defined by the "I" aka self-consciousness (but it could also be an ant colony, the Church, the State, the biosphere, etc... all the way up to "God").
Hegel tries to notice the becoming of the notion of the Concept (which could be noticed as the basic thought-tool) into (and through) the notion of the "I".
Hofstadter is trying to do something similar but instead of the Concept as the base (or starting point), he uses the Axiom. Hofstadter then tries to discover if "I" (or "spirit") can emerge from a system of axioms.
Please Note: In order to keep it short I gloss over about 1500 pages of Hegel's & Hofstadter's works.
GEB is one of the best works of modern philosophy, I don't think the reviewer gets the point, the story of formal systems and the structures that determine them are used as an analog for other systems that aren't formal to try and shed light on the process of ontological emergence of intelligence. If you are at least a bit interested in philosophy and computation, you should read GEB at least once.
General definition (courtesy of the wiki): A fixed point (sometimes shortened to fixpoint, also known as an invariant point) is a value that does not change under a given transformation.
So x is a fixed point of a function f if f(x) = x. This can be generalized to various kinds of things in mathematics, but as an algebraic example:
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?
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.
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 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?
> 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.
GEB is art, in the sense that it's really literary. In this sense an "explainer" cannot really capture what it is about and why it's interesting. Reading a summary of the story of Hamlet, no matter how "in-depth", is not interesting.
There was a very good (charitable) takedown of some of the content of GEB referenced on Hacker News a few months ago, but I can't find it :-( Can anyone help please?
The book is not just about the ideas, it is about the tapestry of how it was presented. It was a new form of literature. The whole document was its own strange loop.
It's not an insult. Psychedelics can profoundly change how someone perceives things. GEB has that sort profound shift in POV that many would associate with psychedelics.
Getting hit in the head can also change how someone perceives things. I think the above commenter was expressing frustration with the popular notion that taking drugs is some sort of shortcut to understanding consciousness, dynamic systems, etc
Note that I said "profound change" not "arbitrary change". What a faithful argument you've blessed us with.
If you think drinking alcohol or taking cocaine has the same mental effects as psychedelics, then, I guess all I can say is don't talk about what you don't know.
For someone who is complaining about someone supposedly not reading the exact words you wrote - you're awfully quick in putting words in their mouth. I don't see "alcohol" or "cocaine" mentioned, and yes, the public does put psychedelics in the generic term 'drugs'.
"Shortcut" is overstating it. It can steer one's thinking in a direction that makes those topics seem more relevant or interesting. This in itself can be very valuable.
> Getting hit on the head
Well - there are recorded cases of brain damage unlocking abilities and aptitudes (albeit with great rarity). So probably not recommended.
But rest assured, psychedelics are less painful, cause less damage and have a higher probability of beneficial effects.
The insult is the implication that thinking like this is somehow due to use of and exposure to psychedelics. Maybe some people need assistance in thinking deeply, Hofstadter certainly is not one of them.
Do you think that you feel better than others for not taking drugs, and that this superiority is assailed when people who take drugs find common ground with one of your favorite thinkers? Because that's the only explanation I can think of for this blatant assholeishness and gatekeeping.
Hofstadter doesn't own thinking about consciousness, thinking deeply, or thinking philosophically. As a matter of fact these sorts of things, to many people - many more than who have even heard of Hofstadter - associate them with psychedelics. So it's not unreasonable, it's not an insult, to think Hofstadter going pretty deeply into questions of meaning, putting mind-bending Escher works in his book, referring to the person that wrote GEB as different from Hofstadter himself, etc... is psychedelic. These are things that most people find eccentric, and what psychedelic users find psychedelic.
The only way I could find insult in such comparisons is if I felt psychedelics themselves were morally inferior or insulting. I would examine that.
Oh, to be clear it has nothing to do with morality. Similar to someone elses comment above, having the experience of thinking you can salsa dance while drunk and actually being able to salsa dance are very different. In the same way, Someone might gain some understanding of H's thinking by taking psychedelics, but that does not lead to the same understanding as actually processing, imagining and writing the material does. I also think you might be devolving a little into flamebait here, as it seems you have taken my statements personally but they were not directed in any way at you.
I took a lot of psychedelics in my life, and in that period I also read GEB quite religiously. And in my experience, I think it could have taken me a lot longer to empathize with the book than if I weren't taking psychedelics; not because of a false sense of understanding but because of a similarity in mental context. I felt like on LSD, I could look behind the curtain, so to speak. This isn't the same feeling as when you're drunk. Nothing else triggered my 'looking behind the curtain' sense as reading GEB. FFS Hofstadter had a place for the non-things - Tumbolia. To a sober person, it's obviously very silly. But on psychedelics, it's quite fantastical and intriguing. Imagine if, there was a place where non-things are. You begin to follow that thought more closely if you've taken psychedelics. You might leave it as nonsense if you haven't.
So from my point of view, it devolved into flamebait the moment you said comparing GEB to psychedelics is insulting. Because to me, it makes sense on a lot of personal levels.
As I've said in another comment. If you think drinking alcohol and taking psychedelics have similar mental effects. Then I suggest you stop talking about what you don't know.
I truly am not intending this upcoming statement as an insult:
I did not struggle with 'looking behind the curtain' while reading GEB, nor did I find the concepts silly - I was rapt with curiosity the whole reading and came to many profound conclusions about the book and it's ideas - and I was not on LSD. Whatever helps you personally understand the world in a more meaningful light is wonderful, but it certainly was not needed for me and I doubt (based on what I know about the author) it was needed for him when writing this book.
You explicitly "wondered" if H was "experienced" with psychedelics, implying that you thought so since you found it "trippy". Go back and read your original comment. No one here is saying psychedelics are morally suspect, they're saying that your explicit suggestion that H was "experienced" is insulting.
Because it is. And your trying to move the goalposts after the fact is just digging that hole deeper.
That's really quite funny. Tell me again how I should read 'my' original comment - after you've compared my username with the one who made it.
The suggestion that Hofstadter has tripped isn't insulting because GEB is a trippy book. Even if it weren't it wouldn't be insulting, only confusing, unless you think that trippy is a bad quality. Examine that.
GEB is whimsical, fun and mind-bending. If it were written any other way it wouldn't be trippy. There is nothing wrong with that.
(upvoted!) can you say more about this sensibility of yours? I'm genuinely intrigued, as I haven't heard a take like that before :)
At risk of asking a leading question: is it some idea that deep truth should come from reason rather than the noise and chaos of psychedelics? (I don't do them myself, but hold them in very high regard as a force in the world)
Your question is loaded in a different way than you might have anticipated, it presupposes that truth DOES come from psychedelics as well as from reason.
It's true that many people feel a deep connection to and understanding of consciousness during a psychedelics trip. Did they actually gain any knowledge about how their own brains work in the same way that a neuroscientist or ML expert might understand it? I contend that they did not, even if they feel that they did.
In a similar way a drunk might suddenly feel that he has the ability to dance. That's hardly a replacement for salsa classes.
Of course there are exceptions. Many brilliant people take psychedelics and credit them with breakthroughs in their fields, that can't be ignored. But you'll notice that its always _in their field_, ie they were already thinking about a problem and psychedelics offered them a new perspective.
I have no problems with psychedelics or their use. I took issue with the implication that they are needed in order to think in the way Hofstadter does - it's kind of like asking what flippers Michael Phelps uses when he swims in the olympics.
I didn't mean to imply that and certainly don't think it is required. My question had little to do with the content and much more to do with the style, and the author's intended effects upon the reader.
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
He doesn't say it was written while high. He is wondering if H knew the effects of psychedelics and maybe tried to replicate the feeling in the reader.
In large doses over extended periods of time, they do change how someone thinks and perceives the world, perhaps for the worse. See stories of amphetamine psychosis. Those somewhat mirror a type of extended bad experience after using psychedelics, often called dark nights.
It just shows you can be an avid drug user and still make enormous contributions to STEM. It only takes n=1 to provide a counterexample to an absolute like "drugs never produce anything substantial."
That's quite the strawman, I don't know anyone who says that. And if they did I would ask them if they drank coffee or if they were aware that a good chunk of young professionals are on ADHD medication
Yes that is an absolute statement (and maybe an incorrect one!) but it's scope is psychedelics in relation to GEB, not all possible drugs in all possible situations
Like the Zen Masters the author thinks DH has a problem with, I rather think that the point of GEB is to be read by a person at a certain point in spacetime who experiences it a certain way, though I appreciate the logic, it misses the strange loop.
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.
While I'm not sure it requires "less maturity", DH released a subsequent book titled "I am a strange loop" which is an attempt to condense his ideas from GEB.
Zen and the Art of Motorcycle Maintenance comes to mind immediately. It works on several levels and is very accessible as a result. If you wanted to stray from the spirit of GEB into narrative prose, there are a number of books I could recommend, especially in science fiction.
ZMM is a great philosophy intro book. It's captivating and will get you in that "deep thinking mode" while never getting too overly dense. The actual core philosophy is a bit meh, but it really doesn't matter since the book is loaded with general good insight.
Sophie's World, which is about the history of Western philosophy (well, at least on one level. On another level, it's a story about a girl who starts to receive mysterious letters).
Try Raymond Smullyan. He has books at a range of levels of accessibility; I'm not sure if there's anything great for your 8th grader, but I remember first getting into The Lady or the Tiger? as a teen.
Smullyan's "Forever Undecided", and Ernest Nagel's "Gödel's Proof" are the best explanations available, to my mind. I find GEB to be bloated, if all that one is interested in is Gödel. (There is much more to recommend GEB, but if all you want is Gödel's proof, see one of the above.)
Not mathy, more where philosophy is coming from, but the books I remember from about the same timeframe as GED were
Penrose's The Emperor's New Mind
Timothy Ferris Coming of Age in the Milky Way
and the Zen and the Art of Motorcycle Maintenance, previously mentioned.
Maybe not the most current thinking (but perfectly fine as an introduction), but the writing is more accessible than GED.
I read the book for the first time at that age, and I definitely enjoyed it. While I knew some things were over my head, a lot of concepts are actually explained well enough that a 14 year old can grasp it, and the dialogues are a lot of fun.
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.
It depends on what you mean by "a similar spirit" I suppose. One thing Hofstadter didn't like about GEB was he felt too many people didn't see his central theme among the many other ideas there.
His 2007 book, "I Am A Strange Loop" is a bit of an answer to this. It's mostly the same ideas in GEB about the self and strange loops, but without all the meandering and interludes. It's been a while but I remember it being less logic/mathy than GEB. I did enjoy it.
But the meandering and the interludes are part of the enjoyment of GEB. So if you're looking for another book to capture that spirit of GEB, I'm drawing a blank, hopefully someone else knows one.
Barely related recommendation, but I remember reading "A Brief History of Time" around that age. Very doable for a young teen if they have a passion for that sort of topic.
Ah - interesting. It took me several readings to tease-out what I thought the central theme was. As it happens, it led to a position that I objected to (and still object to). So discovering that central theme brought the book down a peg or two in my estimation.
I still think it's one of the most entertaining books of popsci that I've ever opened.
I have read the book. But if your concern is a simple explanation of Gödel, read Nagel and Newman. I spent an afternoon on that in undergrad and woke up the next morning content. Went on to learn much more later, of course.
Thanks for pointing me towards this fantastic book. About the review, it says nothing about Bach (once only) or Escher (just the figures), so how does it capture clearly or comprehensively the book?
The real neat thing is if you compare the full series from the author of GEB to the famous math person named Penrose as they both cover different sides of the same argument and at times beautiful math as well.
Short take...our reality is a mesh between two different math desc, one is micro and one is not. The only problem is we still have no idea how nature bridges between those two different mathematic systems and that leads us down some very interesting rabbit holes:
1. String Theory and multiple worlds, except they are on micro basis, i.e. you cannot see them even with an electron microscope.
2. Tim travel at electron part level but not atom level.
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 prefer to have true things that can't be proven rather than provable things that are untrue. But either is possible.