Hello, sorry to bother you, but I’m not sure I completely understand Godel’s Incompletenes Theorem(s). Could you please explain it to me in simple terms that someone with very few brain cells could understand?
Thank you
Read this:
phil.pku.edu.cn/cllc/archive … elThms.pdf
…and get back to me.
I’ll be waiting for a small eternity.
Any system of logical propositions rich enough to do interesting things can formulate in the language of the system propositions that may be true, but cannot be proved true by the postulates of the system. That’s the first theorem. The logical consistency of the system is one of these propositions. That’s the second theorem.
This is a very rough summary, but it’s enough to get started with. I think the wikipedia article on “incompleteness theorems” has the exact language of the theorems, if you’re interested in pursuing it farther.
Thank you for your responses. Could you give me a good example of a Godel sentence that would help me to grasp the theory more solidly?
What you have asked for here is both easy and difficult. The easy part first: “The system of mathematical logic is both complete and self-consistent.” The second theorem is virtually a demonstration of the first; you cannot prove the consistency of the system using only the propositions in the system.
The difficult part is that it’s hard to give other examples in a context like this because the factual statement differs from system to system. There are some statements that may be true but cannot be proved within the system, and if you add a postulate to the system to prove the proposition you have in mind, that very fact generates other true-but-unprovable statements.
And that is about as much short, rule-of-thumb that can be given in a context like this. For a deeper understanding, you have to read the original arguments and the good explications – and talk it over with the experts.
The best explanation I’ve ever read is in a book called Godel, Escher & Bach by Dave Hoffstaeder. It’s a great read (a little lengthy though).
GIT has toppled logical positivism. Philosophy was once tha major discipline of academia…not any more.
If you look at the big picture you see that it reveals ALOT about what is going on.
In the world of physics it tells us that mathematics is unprovable. The standard model rests upon mathematics.
It also proves the Universe to be perpetual, by the way…
You’re making far too much claim. Goedel’s theorem did make a major contribution to the movement in about the middle third of the 20th century to re-basing philosophy in language studies – but that was already well under way by the time the Incompleteness Theorem was enunciated in 1931, and can be traced back through Wittgenstein, Russell and Whitehead to Dewey and James, going all the way back to Nietzsche, writing in the 1880’s (a little before then, but most of the stuff that feeds into that tendez is in his explications of Also Sprach Zarathustra.
Hi to all,
I have just begun rereading Godel Escher Bach and I can not state strongly enough what a great book that is! On my first reading I told my wife that it was the best book written in fifty years and, if I recall correctly, Polemarcus has stated that it was his favorite book.
On the subject of completeness I would make just one small note of caution. There are a number of smaller axiomatic systems that are complete. Predicate Calculus and Hilbert’s axiomatic restatement of Euclidean Geometry are examples. To my great surprise Twiffy has claimed that the Reals, a larger axiomatic system, are also complete. I have not verified this claim but his background in foundational math carries enough weight for me personally to be cautious about drawing overly broad conclusions concerning the Godel Theorems.
I’d like to agree with Ed3, it’s a fantastic book. I also want to throw in a word of caution - it is a fantastic book and does exactly what it says on the tin. However, it’s not a very philosophical approach, which is also fair enough as it was not presented as such, but for anyone approaching this from a “ramifications to philosophical logic” sort of angle, you would be advised to read it with the knowledge that it is not considered to be particularly philosphical.
I’m only saying that, because many keen philosophy students pick it up hoping it will be philosophical, when it isn’t.
Hi Obw,
I too have found Hofstadter, somewhat disappointing when it comes to his near dogmatic beliefs in AI and when he was editor at Scientific American. (I missed the good old days when rigorous mathematical problems and puzzles were the order of the day). Though, he was the first one to introduce me to Thai symbols.
The main reason that I am rereading Godel Escher Bach is to do the preparation for my next post on models. This one was intended to critique Hofstadter’s model of meaning. Basically, I was going to define an equivalency class using a homomorphism analogously to Hofstadter. And I do have some reservations, which still need to be worked out, but I think that the concept is interesting.
Do you have some insight, or objections on this particular subject?
Hi Ed,
That sounds like an interesting idea. I do not have anything of value to suggest to you, as I cannot claim to know enough about the subject. It is something I would enjoy learning more about, however. Perhaps you will be able to reconcile what I felt was a twinge of self indulgency running through his thinking- I felt some of it was like theology (accept my assumption or do not, if you don’t, you might aswell put the book down) and therefore did become angry with him sometimes.
Apollo,
What Bill Patterson has said so far is exactly correct, but - no offense, Bill - I think I can explain it in a more intuitive way. Please excuse me if at any point I speak beneath your level.
Mathematics, of course, is the study of far more than just numbers. Mathematics studies TRUTH in general. However, it is different from science and philosophy in that it uses an exact formal language. There is a fundamental language of math, which uses a few symbols (the equivalent of our alphabet) that can be combined in only a few precise ways (the equivalent of our grammar). From these symbols and combination rules, you get “mathematical sentences”.
Almost all the math that most people study all stems from a branch of mathematics called Set Theory. There are other distinct branches of math, too, such as Geometry. What makes Set Theory different from Geometry is that it has different AXIOMS. An axiom is a mathematical sentence that is supposed to be true, without any argument for its truth being given. The way all math of any kind works is that you begin with your axioms - your mathematical assumptions - and then, using the rules of mathematical language, you PROVE that, if your axioms are true, that a certain new mathematical statement must be true.
This has always been the way of math, and it always will be. However, around the early 1900s and before, everyone just assumed that, if you can ask a question in math, that question can be answered. If I can say “1+1=2 - true or false?”, then eventually humans can find the answer, and prove that that answer is the correct one.
This was shattered by Godel’s First Incompleteness Theorem (usually just referred to as the Incompleteness Theorem). This theorem proved that in Set Theory (and thus, in most math), there are questions that DO have answers, but that those answers are unprovable. Since humans do math exclusively by proof, that suggests (although does not demand) that we will never be able to find those answers.
As Ed has mentioned, there are some systems that are not incomplete - systems where every question has an answer that can be proven. Euclidian Geometry is one of these systems. So is the philosophical study of Propositional Logic. But there are also other axiomatic systems besides Set Theory that are INcomplete. Peano Arithmetic is one - First-Order Logic is another. These systems all contain questions whose answer cannot be proven.
One of the most interesting things about these “questions whose answers cannot be proven” is that, most of the time (although not all of the time), the answers are malleable in some sense. Here’s what I mean. Suppose you’re working with the mathematical system of standard arithmetic. You know that 1+1=2. You then decide, on a whim, to add an extra axiom to that system. You decide to assume, without any basis, that 1+1=3. All of a sudden, you have a self-contradictory system. You can prove (using the old rules) that 1+1=2 – but you can also prove (using your new axiom) that 1+1=3. Contradiction! Your system is now mathematically worthless.
Well, when you take an incomplete sentence, it doesn’t necessarily work that way. Let’s say that X is a sentence that is true, but cannot be proven to be true. It is entirely possible (and indeed common among incomplete sentences) for the following to work. You decide to add an extra axiom to your system. This new axiom reads “X is true”. Well, since X was true before, all this new axiom lets you do is PROVE that X is true. Before you couldn’t do it, but now you have this new axiom… and even though you’re just saying “my proof that X is true is that my axiom SAYS X is true,” in a mathematical sense, that’s perfectly acceptable. So you have this new axiomatic system where X is still true, but can now be proven.
What if you instead added the axiom “X is false”? You might think you’d get a contradiction, since beforehand, X was true. But NO - you now have a system with NO contradictions, in which X is false and can be proven to be false.
That is some weird stuff, buddy.
Lastly - here’s a more practical example of an “incomplete conjecture” than Bill gave. In fact, historically, this is really the first such example, besides the example Godel used in his proof.
In the late 1800s, a mathematician named Gregor Cantor proved that different sets can have different sizes of infinity. He proved that the set of all integers has the smallest size of infinity, and that the set of real numbers literally has MORE members - a bigger size of infinity - than the integers did.
People then naturally asked, “is there any set that has an infinite size right between the two?” Well, we don’t know what the answer is, but we know for a fact (it’s been proven, ironically) that the answer is unprovable.
It’s called the “Continuum Hypothesis”, and it’s the most easily understandable and generally best example of incompleteness out there.
Lovely discussion. I would only remark that I was only trying to give our querant a more useful place to start than referring him to a dense treatise that might or might not be helpful.
Interestingly, your statement that mathematics is concerned with truth is a pre-Goedel notion; one of the secondary consequences of the Goedel theorems is that notion being discarded (a process which was already under way, since Russell and Whitehead were having difficulty with their sums…). Mathematics studies the interrelations of symbols, nothing more – and in fact, to the best of my knowledge, no one has ever come up with a colorable reason for believing that the structure of the symbols has any necessary correspondence with the, for want of a better term, “structure of reality.” It just does, in some cases – and particularly, as is the case of physics, where we choose the symbols we want to work with because they seem homologous with the reality we want to work with. But as all design engineers know, just because the math works out that way doesn’t mean the machinery will behave according to plan. Reality is always bigger than the equations – and it seems more usefully described by the mathematics of the dynamics of complexly interactive systems, which can be just as weird as anything anywhere.
Again, though, very nice discussion.
Weeeelll, that’s not quite true. Actually, I’m interested to know if your background on this material is mathematical or philosophical. Have you ever actually worked with incompleteness proofs and model theory? Not to imply that what you believe is invalid if you haven’t, but rather that if you have more of a philosophical background than a mathematical one, that might explain the difference in our views.
You’re right when you say that mathematics is the manipulation of symbols - however, in a precise sense, it’s of course a bit more than that. You manipulate a countable (usually finite) set of symbols in accordance with a specific set of rules. You also have, very pointedly and necessarily, a notion of truth. In fact, you have two notions of truth - syntactic and semantic. Completeness is technically the assertion that the set of symantic truthes is equal to the set of syntactic truthes. It’s important to know that “truth” is not only a characteristic of mathematical systems, but an absolutely essential one. Godel’s First Theorem itself rests upon the fact that any mathematical conjecture is either True or False (given the axioms).
Certainly many will agree that the axioms of set theory, or other systems, are not inherent truthes in our universe. But math is not the assumption that the axioms are capital-T-true - they are the derivations, “IF the assumptions are true, these theorems follow” - and many mathematicians strongly believe that in this respect, the conclusions of math are capital-T-true in our universe.
The fact that we can observe that it seems to work, that our usage of the math is clearly productive and useful, is an argument for continuing to use the math and believe that it can give useful results. In general, you can provide a partial justification for this stance simply because Set Theory is so powerful and yet so fundamental that it can encode literally any axiomatic system that we know of within it. Presumably this would encode the axiomatic system of our universe.
Of course, neither of those arguments are by any means a proof. In general, it seems to me that the most reasonable stance is to believe that math can perfectly encode reality, but since it’s very difficult for us to be certain about small details in our reality, we may never know which math DOES encode the reality. It may well be true that ever-closer approximations are the best we’ll ever get.
Well, that’s not really a solid point. In engineering, and indeed in any physical science, there is a great deal of complicated stuff, and in order to make it manageable by our limited brains and techniques, they throw out a lot of details that are more or less irrelevant. They also use approximate physics (e.g. Newtonian mechanics) instead of the more complicated quantum mechanics. What you usually get is a mathematical answer that corresponds well, but imperfectly, to reality. Sometimes you get an answer that is significantly wrong. But none of this at all suggests that math fundamentally cannot model our reality perfectly. In fact, in a mathematical sense, we have every reason to believe it can, and that we’ve merely been using incorrect models.
I like this subject also…
I might have no clue what it is really about, but to me it’s something like…
you can never be certain that the system you use for something is ‘true’ ‘‘outside of itself’’… sort of…
if this is a way too simple explanation or just plain wrong, please tell me. 
Twiffy:
You raise some excellent points, but you seem to be working with a highly restricted definition of “truth,” and it appears to me that you have not really examined what the correspondence of mathematics to what we laughingly call “reality” might mean.
The logical-mathematical definition of truth (one of two mutually exclusive values that can be predicated to a proposition – i.e., either “true” or “false”) doesn’t really match up very well to the realities we deal with. Careful mathematical logicans might add the qualifying clause: “for certain values of x”, while classical logicians would say something more like “a thing is either true or not true for a given aspect at the same time.” Propositions always and necessarily deal with limited aspects of the nature or behavior of an entity; and the mathematical description of the particular aspect of nature or behavior of an entity at a given time and under a given set of circumstances might be more or less different under other circumstances and at different times. Blanket statements about the nature of “truth” are necessarily suspect.
Parenthetically, it’s hard to separate out the mathematical versus the philosopical orientation these days.
The fact is, we choose our symbols and rules for manipulating them according to what we find useful for a given purpose. Statistical mechanics produces some particular types of useful results, while classical mechanics produces some other particular types of useful results. Neither is inherently “better” for overall descriptive purposes. The kind of tool you choose determines the kind of result you can most easily get – and then generates its own metaphors. As Emerson said, first we build our house and then we are imprisoned by it. Wave mechanics was the dominant metaphor of 19th century science, and it produced a lot of interesting science. Statistical mechanics generated the dominant metaphors of 20th century science, but we’re poised on the brink of something else now, and it will have its own unique donees. I’m looking forward to it.
That belief is somewhat naive. The axioms of any system are capital-T true for the propositions within the system, because they determine the structure of the model and therefore what truths can be seen in the framework. I like your formulation “IF the assumptions are true, these theorems follow.”
I’m afraid I don’t see this gets you any for’arder. (Incidentally, Isaac Newton’s original insight was exactly the reverse – not that mathematics encodes reality, but that reality encodes mathematics, which has more possibilities to work with.)
I see two big problems with this formulation; first, it assumes “mathematics” is univocal, whereas there are a potentially infinite number of different mathematics, all of them designed to homologize certain aspects of physical reality or to explore logical consequences of propositions placed in conjunction with operational rules.
The second main problem is that a mathematical equation is always and necessarily an abstraction from the reality, and thus “closer and closer approximations” can necessarily never come anywhere near the actuality of the thing; the term “closer and closer” is itself an idiosyncratic notion (no matter how large the “idio” of the group), depending on what particular aspects you are interested in looking at. In some respects, the term “closer and closer” means “ignoring more and more important aspects of the thing,” the way, for example, “building a dam” also and necessarily and simultaneously means “making a desert.”
Linguistics in this case – or literary theory at any rate – gives us a better model for thinking about what goes on this way: we are “foregrounding” certain aspects and “backgrounding” others. The others don’t go away; they’re just less relvant to the aspect we want to look at when we place it in foreground.
I think you’re right. I’ve read the book a number of times, and after reading the other posts, I think I have something to add:
I’m going to try to do this using symbols.
Let say we have a mathematical system called S. And inside the system we have some axioms A1, A2, and A3 and from these axioms we can attain proofs P1, P2, and P3.
Godel’s theorem shows that by assigning another layer of symbols over these symbols you can come up with a proof that is true but unprovable within system S. Let’s call this proof GP (Godel Proof).
I think other folks have explained this much already, but here is an additional interesting fact:
What happens when you add GP as an axiom? Lets call this system S2.
So now you have a new system (S2) with axioms A1, A2, A3, and GP. Well, it doesn’t matter! You can just again layer the symbols over the new system and come up with another proof, GP2, that is true but unprovable within the system.
It’s the beauty of the theorem: every time you add the unprovable proof as an axiom to create a new system (Sx+1), you can generate a different, new unprovable proof (GPx+1+1)! Neat, huh.
Membrain,
Nice name, by the way. Is that from Zim, or something else?
Now be careful! This is a very interesting segment of the Incompleteness Theorem, but the truth of the matter is somewhat different. It isn’t that adding GP generates a new unprovable proof; it’s that, no matter how many axioms you add, the new system will still contain an incomplete sentence. Now, this either means that new incomplete sentences are generated, like you claimed, OR it means that there are fundamentally incomplete sentences, that cannot be added as axioms to the system in a consistent manner.
Thoughts about which it is?
Hi, sorry to barge in but I’m curently going through the misfortune of writing my masters dissertation.
Is anyone here familiar with Penrose’s hypothesis?
By the way I love Godel, Escher and Bach but it does lack philosophical weight.