# Math + Logic = Godel? **URL:** \ **Category:** Factual Questions\ **Created:** [April 25, 2001, 4:42am UTC](https://boards.straightdope.com/t/math-logic-godel/63242 "2001-04-25T04:42:55Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [April 25, 2001, 4:42am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/1 "2001-04-25T04:42:55Z")
I came across an older TIME magazine, explaining how some expert in locic named Godel was one of the greatest minds of the 20th century, for his proof that Mathematics cannot be sucessfully united with logic. The proof is a little hard for me to understand. Can any of the teeming millions explain it to me as if I was ten years old? ---
**Author:** ![Synergist](https://avatars.discourse-cdn.com/v4/letter/s/ed8c4c/32.png) [@Synergist](https://boards.straightdope.com/u/Synergist)\ **Post date:** [April 25, 2001, 4:52am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/2 "2001-04-25T04:52:34Z")
If you are talking about Godel’s most famous work, the undecidibility theorem, I doubt there is anyone who can explain the proof to you as if you were ten years old. A ten year old couldn’t grasp it. IIRC George Hilbert refused to believe it at all. ---
**Author:** ![Synergist](https://avatars.discourse-cdn.com/v4/letter/s/ed8c4c/32.png) [@Synergist](https://boards.straightdope.com/u/Synergist)\ **Post date:** [April 25, 2001, 5:05am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/3 "2001-04-25T05:05:55Z")
I did find a number of descriptions of the proof. The clearest one is at [http://www.miskatonic.org/godel.html](http://www.miskatonic.org/godel.html) . Even that one only gives an outline of a simplified version of the theorem. ---
**Author:** ![panamajack](https://avatars.discourse-cdn.com/v4/letter/p/47e85d/32.png) [@panamajack](https://boards.straightdope.com/u/panamajack)\ **Post date:** [April 25, 2001, 5:44am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/4 "2001-04-25T05:44:32Z")
The absolute best explanation of Gödel’s theorem for non-mathematicians is the book \*Gödel, Escher, Bach : An Eternal Golden Braid \* by Douglas Hofstadter. Not just a good explanation, but a great book as well (according to the back of my copy of _The Mind’s I_, it won a Pulitzer). It is not anything very simple, but the theorem may be as difficult. The book covers a wide variety of topics, but is at its best with Gödel & math. It took me at least three attempts to finish the book when I was in high school. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [April 25, 2001, 6:20am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/5 "2001-04-25T06:20:10Z")
I’ll try to give you the two-cent description of it, just to give everyone else something to work from. Kurt Gödel’s insight was that in formal logic, the manipulation of symbols according to rules in order to logically prove or disprove a statement, the symbols meant nothing but what we made them mean. Therefore, he could convert the symbols to numbers and apply arithmetical rules that were the equvalents of the logical rules used on the symbols. He could also use the numbers that represented logical statements in logical statements. So, being a clever SOB, he made a statement that said “This number is not produceable by this logic system”. The number the statment referred to was the number that represented the statement itself. He then went on to prove that you could use the same logic system to **both prove and disprove his statement**. The logic system he used was the _Principa Mathematica_, the basic foundation for all of our mathematics. A lot of people never forgave him for finding a paradox in the most fundamental level of math. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [April 25, 2001, 7:23am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/6 "2001-04-25T07:23:27Z")
> [@](#): > > He then went on to prove that you could use the same logic system to both prove and disprove his statement. Actually, what he did was show that the statement was _neither_ provable nor disprovable within the system–the statement is “undecidable”. Not really paradoxical, but not really a happy day for mathematicians, either. For a while after that, it was widely thought that Godel’s Theorem would have no serious impact on mathematics–it was merely a curiosity, certainly such mathematical statements exist, but they would all simply be trivial ones (on the order of “This Theorem has no proof” curiosities), while all the important ones would still be decidable. In 1900, David Hilbert presented a list of what he considered to be the 23 most important unsolved mathematical problems for the 20th century. The very first one on the list was the “Continuum Hypothesis”–basically, does there exist an infinite cardinal strictly between that of the integers and that of the reals? In the early '60s, Paul Cohen showed that this statement is actually undecidable in the standard set theory axioms. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [April 25, 2001, 3:56pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/7 "2001-04-25T15:56:32Z")
There’s also a host of other propositions in mathematics which are believed to be undecideable. The Greater Goldbach Conjecture, for instance (which states that every even number greater than 2 can be expressed as the sum of two primes), has never been proven, despite many attempts by many great minds, but it’s been tested up to numbers in the billions and higher, and nobody really doubts its truth. This is a particularly bothersome one, because if it is, in fact, undecideable, we’ll never even be able to prove that it’s undecideable. I believe it’s even been proven that “most” mathematical statements are undecideable, in much the same way that “most” real numbers are irrational, but that’s not too much cause for worry, sinc most mathematical statements are rather boring even to a mathematician, and most _interesting_ statements seem to be decideable. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [April 25, 2001, 4:08pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/8 "2001-04-25T16:08:13Z")
> [@](#): > > I believe it’s even been proven that “most” mathematical statements are undecideable, in much the same way that “most” real numbers are irrational, but that’s not too much cause for worry, sinc most mathematical statements are rather boring even to a mathematician, and most interesting statements seem to be decideable. Yeah, that’s basically true. A very informal, “intuitive” idea of Goedel’s theorem could run as follows (intuitive if you’re comfortable with cardinality). There are uncountably many subsets of natural numbers, while our notation (any notation) can only describe countably many things–we can come nowhere near describing most subsets of natural numbers (or most real numbers). ---
**Author:** ![hawthorne](https://avatars.discourse-cdn.com/v4/letter/h/c89c15/32.png) [@hawthorne](https://boards.straightdope.com/u/hawthorne)\ **Post date:** [April 25, 2001, 4:23pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/9 "2001-04-25T16:23:36Z")
See if this helps: Epimenides, a bloke from Crete once said “All Cretans are liars.” This is a _self-referential_ statement. If the statement is true, then Epimenides himself must be a liar and the statement must be false (and so on). Over the centuries this turned out to be more than a silly puzzle, and seemed to threaten the ground of mathematics. Gödel showed that in a system at least as powerful as number theory\* that such problems touched maths. Specifically, by a system of coding, Gödel showed that statements _of_ number theory could at the same time be statements _about_ number theory. Provable statments were given a number. In particular the coding allowed a string of numbers and symbols to stand for the proposition “that this statement doesn’t have any proof”. This produces a _True_ statement _of_ number theory _inside_ number theory which is not provable within number theory. \*Consistent systems less powerful than number theory (stuff you can do with whole positive numbers) such as Euclidean geometry do not have undecidable propositions. ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [April 25, 2001, 11:10pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/10 "2001-04-25T23:10:30Z")
> [@](#): > > \*Originally posted by \*\*\*picmr \*\* > \*Consistent systems less powerful than number theory (stuff you can do with whole positive numbers) such as Euclidean geometry do not have undecidable propositions. Not so. The parallel postulate is not decidable from the other postulates of geometry. Gödel’s theorem says that any system that contains arithmetic must contain undecidable propositions. Containing arithmetic is a sufficient condition but not a necessary condition. There are systems that contain undecidable propositions; Euclidean geometry is just not one of them. The fundamental difference between Epimenides’ paradox and Gödel’s statement is the Epimedies’ paradox asserts something about the truth value of itself – that it is false. We can disallow statements that refer to truth values. Gödel’s statement asserts that it has no proof. Any system that allows arithmetic can produce Gödel’s statement. If a consistent system can produce a statement that asserts that it has no proof, then it _must_ be true. However, no proof can exist, for if a proof exists, then it would be false. Since you cannot prove or disprove it, it is undecidable. **panamajack** , I tried to read Gödel’s proof by Gödel in college. I just couldn’t get it. Then I read _Gödel, Escher, Bach : An Eternal Golden Braid_. I loved it! It’s a very entertaining book that deals with Gödel’s theorems and a whole lot more. It did win the 1980 Pulitzer prize for general non-fiction. ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [August 20, 2002, 3:07am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/11 "2002-08-20T03:07:06Z")
Correction: It was not Godel. it was Ludwig Wittgenstein. Attempted to reduce all mathematics to logic. ---
**Author:** ![Wendell\_Wagner](https://avatars.discourse-cdn.com/v4/letter/w/8491ac/32.png) [@Wendell\_Wagner](https://boards.straightdope.com/u/Wendell_Wagner)\ **Post date:** [August 20, 2002, 8:27am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/12 "2002-08-20T08:27:55Z")
_Godel’s Proof_ by Ernest Nagel and James Newman is a short book that’s as simplified an explanation of the theorem as is possible while still getting across the general idea. ---
**Author:** ![The\_Great\_Unwashed](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/the_great_unwashed/32/4791_2.png) [@The\_Great\_Unwashed](https://boards.straightdope.com/u/The_Great_Unwashed)\ **Post date:** [August 20, 2002, 10:17am UTC](https://boards.straightdope.com/t/math-logic-godel/63242/13 "2002-08-20T10:17:05Z")
> [@](#): > > \*Originally posted by DrMatrix \* > \*\*Not so. The parallel postulate is not decidable from the other postulates of geometry. \*\* Er, isn’t the “Parallel Postulate” in fact an AXIOM of Euclidean geometry? ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [August 20, 2002, 12:51pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/14 "2002-08-20T12:51:33Z")
Er . . . Yeah . . .The “Parallel Postulate” is in fact an axiom. ---
**Author:** ![muttrox](https://avatars.discourse-cdn.com/v4/letter/m/a8b319/32.png) [@muttrox](https://boards.straightdope.com/u/muttrox)\ **Post date:** [August 20, 2002, 12:53pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/15 "2002-08-20T12:53:20Z")
It’s an axiom because they couldn’t figure out a way to prove it. If they could have proved it, they wouldn’t have needed to make it an axiom. ---
**Author:** ![John\_Kentzel-Griffin](https://avatars.discourse-cdn.com/v4/letter/j/ccd318/32.png) [@John\_Kentzel-Griffin](https://boards.straightdope.com/u/John_Kentzel-Griffin)\ **Post date:** [August 20, 2002, 1:15pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/16 "2002-08-20T13:15:04Z")
All of the postulates are axioms. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 20, 2002, 2:50pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/17 "2002-08-20T14:50:41Z")
Note that there’s nothing logically wrong with having axioms that follow from other axioms. They’re just dependent, and you’ve written more than you need to. The theory is not invalidated in the least. For the curious, I explained G’s theorem in great detail in a recent GD thread. Search on “inconsistent incomplete” within the past three months. I’ll try to dig up a link, but the search engine’s being slow. Once I find the thread, the discussion is in the last few posts, on page 2. Note that it presupposes that you’re familiar with predicate logic–this may be a small barrier for some. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 20, 2002, 3:00pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/18 "2002-08-20T15:00:25Z")
Note that there’s nothing logically wrong with having axioms that follow from other axioms. They’re just dependent, and you’ve written more than you need to. The theory is not invalidated in the least. For the curious, I explained G’s theorem in great detail in a recent GD thread. Search on “inconsistent incomplete” within the past three months. I’ll try to dig up a link, but the search engine’s being slow. Once I find the thread, the discussion is in the last few posts, on page 2. Note that it presupposes that you’re familiar with predicate logic–this may be a small barrier for some. ---
**Author:** ![The\_Great\_Unwashed](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/the_great_unwashed/32/4791_2.png) [@The\_Great\_Unwashed](https://boards.straightdope.com/u/The_Great_Unwashed)\ **Post date:** [August 20, 2002, 3:04pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/19 "2002-08-20T15:04:20Z")
> [@](#): > > \*Originally posted by muttrox \* > \*\*It’s an axiom because they couldn’t figure out a way to prove it. If they could have proved it, they wouldn’t have needed to make it an axiom. \*\* Oh. When you say “they couldn’t figure out a way to prove it” you’re probably referring to Euclids own expectation that the parallel postulate (PP) could be derived from the others, which it can’t, no matter how much one figures. This does not make it an UNDECIDABLE THEOREM of geometry though – in fact, with only the core axioms (all except the PP) the PP is NOT a theorem. Euclid wasn’t such a raving egotist to name Geometry “Euclidean”, which is a much more modern term (IIRC it dates from the 19c). **Euclidean Geometry** by _definition_ includes the PP – the non-Euclidean flavours don’t. ---
**Author:** ![Nametag](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/nametag/32/406_2.png) [@Nametag](https://boards.straightdope.com/u/Nametag)\ **Post date:** [August 20, 2002, 3:23pm UTC](https://boards.straightdope.com/t/math-logic-godel/63242/20 "2002-08-20T15:23:12Z")
> [@](#): > > \*Originally posted by Enola Straight \* > \*\*Correction: > > It was not Godel. it was Ludwig Wittgenstein. > > Attempted to reduce all mathematics to logic. \*\* I think ye’d best start a new thread, E.S.; this one’s hopelessly polluted. [Next page](https://boards.straightdope.com/t/math-logic-godel/63242.md?page=2)