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?
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.
I did find a number of descriptions of the proof. The clearest one is at http://www.miskatonic.org/godel.html . Even that one only gives an outline of a simplified version of the theorem.
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.
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.
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.
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.
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).
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.
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.
Correction:
It was not Godel. it was Ludwig Wittgenstein.
Attempted to reduce all mathematics to logic.
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.
Er, isn’t the “Parallel Postulate” in fact an AXIOM of Euclidean geometry?
Er . . . Yeah . . .The “Parallel Postulate” is in fact an axiom.
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.
All of the postulates are axioms.
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.
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.
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.
I think ye’d best start a new thread, E.S.; this one’s hopelessly polluted.