What is "Godel's Incompleteness Theorem"?
- Thread starter Yahweh
- Start date
-
- Tags
- godel's theorem
Kopji
Philosopher
- Joined
- Apr 21, 2003
- Messages
- 8,004
It's a math thing, but Gödel wrote his own version of Anselm's Ontological Argument using its premises. This makes it fair game in the philosophy realm as far as I'm concerned.
There's some controversy about Gödel. He's sometimes portrayed as a mystic woo, but his work actually shows the modal logic behind a popular 'proof' of God.
This would make the idea of God to be purely a mathematical construct, removing the 'mystery'. If there is no mystery to God, where is the place for belief to live?
Gödel was a smart guy, he MUST have known this was sort of like disproving God. Yet, the controversy continues. He died thinking everyone was trying to poison him...
Anyway the IT Has to do with the liar's paradox. Gödel proved, using modal logic, that any system sufficiently complex contains statements that are true but cannot be proved true within the system.
There is a story somewhere about Bertrand Russell moving to philosophy from mathematics because of Gödel, not sure if its true.
Someone in the UK had been asked to create a book that cataloged all books in the US. When completed, the publisher mentioned the list would not really be complete without mentioning the UK catalog book itself. (sorry, much paraphrased).
There's some controversy about Gödel. He's sometimes portrayed as a mystic woo, but his work actually shows the modal logic behind a popular 'proof' of God.
This would make the idea of God to be purely a mathematical construct, removing the 'mystery'. If there is no mystery to God, where is the place for belief to live?
Gödel was a smart guy, he MUST have known this was sort of like disproving God. Yet, the controversy continues. He died thinking everyone was trying to poison him...
Anyway the IT Has to do with the liar's paradox. Gödel proved, using modal logic, that any system sufficiently complex contains statements that are true but cannot be proved true within the system.
There is a story somewhere about Bertrand Russell moving to philosophy from mathematics because of Gödel, not sure if its true.
Someone in the UK had been asked to create a book that cataloged all books in the US. When completed, the publisher mentioned the list would not really be complete without mentioning the UK catalog book itself. (sorry, much paraphrased).
Kopji
Philosopher
- Joined
- Apr 21, 2003
- Messages
- 8,004
I've seen atheists sort of 'poo poo' using Gödel as a proof against God. However, most of them did not grow up in a religion that claimed at some point to know the Truth. I disagree and feel that what Gödel has to say is a powerful argument against not all, but much religious thinking.
The logic and reason behind much of Catholicism and Protestantism derives from Thomas Aquinas.
Gödel shreds the foundation set down by Aquinas, without it, the rest is just a house of cards.
To me, understanding what Gödel was saying was something of a watershed moment. God is a mystery because well, there is always a mystery.
The logic and reason behind much of Catholicism and Protestantism derives from Thomas Aquinas.
Gödel shreds the foundation set down by Aquinas, without it, the rest is just a house of cards.
To me, understanding what Gödel was saying was something of a watershed moment. God is a mystery because well, there is always a mystery.
arthwollipot
Limerick Purist
In 1920, the mathematician David Hilbert proposed to a symposium of mathematics the challenge to formally prove that Principia Mathematica (the Opus of formal mathematics at the time) was both consistent and complete.
Kurt Godel proved him wrong with the Incompleteness Theorem. The details are quite complex and in fact unneccesary. In effect, Godel invented a method of encoding in the symbols of mathematics the statements of mathematics themselves.
By doing this, he could make a mathematical statement refer to a mathematical statement. Specifically, he could make a mathematical statement refer to itself.
He then imported the Epimenides Paradox ("this sentence is false") into formal mathematics, producing a statement ("this theorem cannot be proven in formal mathematics") that was true, but could not be proven in formal mathematics. This showed that formal mathematics was fundamentally incomplete, since there was at least one true result which could not be proven.
The woo misuses this result in the same way that the woo misuses Heisenberg's Uncertainty Principle, which it resembles. They overgeneralise it to apply to systems it was not designed to refer to.
("But evolution can't possibly be correct - Godel's Incompleteness Theorem shows that science can't have all the answers!")
Kurt Godel proved him wrong with the Incompleteness Theorem. The details are quite complex and in fact unneccesary. In effect, Godel invented a method of encoding in the symbols of mathematics the statements of mathematics themselves.
By doing this, he could make a mathematical statement refer to a mathematical statement. Specifically, he could make a mathematical statement refer to itself.
He then imported the Epimenides Paradox ("this sentence is false") into formal mathematics, producing a statement ("this theorem cannot be proven in formal mathematics") that was true, but could not be proven in formal mathematics. This showed that formal mathematics was fundamentally incomplete, since there was at least one true result which could not be proven.
The woo misuses this result in the same way that the woo misuses Heisenberg's Uncertainty Principle, which it resembles. They overgeneralise it to apply to systems it was not designed to refer to.
("But evolution can't possibly be correct - Godel's Incompleteness Theorem shows that science can't have all the answers!")
arthwollipot
Limerick Purist
BTW, the best book on the subject (in my opinion of course) is Godel Escher Bach: An Eternal Golden Braid by Douglas R. Hofstadter, which explains the Incompleteness Theorem step-by-step (starting from an assumption of complete ignorance about formal mathematics) and relates it to other fields of study such as genetics, consciousness, and computer science (although having been written in 1979 it is a bit dated now).
The book has been described as "an excursion for anyone who is interested in the same things the author is", but it is essential reading if you really want to understand the Incompleteness Theorem. In fact, read it anyway.
The book has been described as "an excursion for anyone who is interested in the same things the author is", but it is essential reading if you really want to understand the Incompleteness Theorem. In fact, read it anyway.
TragicMonkey
Poisoned Waffles
Kopji said:
Aquinas, in turn, was trying to combine Christian theology with Greek philosophy, specifically Aristotle. It was a pretty good effort. Personally, I doubt Christianity would have lasted past the Dark Ages without Aquinas. He managed to transform Christianity from an oriental mystical religion which had risen to prominence thanks to the favor of a line of Roman emperors and stayed there thanks to an efficient bureaucracy, and turn it into a religion that actual intellectuals could accept.
Of course, it looks like it's made full circle back to mysticism, with people like Jack Chick running around. Would the man recognize a logical proof if it bit his kneecaps off?
FireGarden
Philosopher
- Joined
- Aug 13, 2002
- Messages
- 5,047
I've never understood the theorem all that well. Those with a better understanding can make corrections.
Eculid's geometry has five axioms. The fifth, regarding parallel lines, was not always regarded as entirely self evident, and attempts were made to prove it using the first four. These attempts failed, and were bound to fail. Because it turns out that, given the first four axioms, you can have a variety of equally consistent geometries each with its own statement about parallel lines.
So the four axiom system is incomplete, because a statement about parallel lines (such as "there can be no such things") cannot be proven or disproven regardless of its "real world" status of true/false (whatever that means).
But problem solved! (it seemed)
Because Gauss had an algebraic geometry where the number of parallel lines and all other goemetic theorems could be proved as a consequence of a "metric" (which is basically just a description of the distance between two points. If you assume the metric given by Pythagorus' theorem, you end up with all of Euclidean geometry. Different metrics, all of which are considered "equal" by Gauss' system, would give you different geometries.) So you had a consistent and complete geometry by inbedding it within arithmatic.
Except that the work of Godel shows that arithmatic (and any other axiomatic system) will itself be incomplete. Given an undecidable theorem, we can have a "larger" mathematics, in which the theorem is no longer undecidable. But that system will itself be incomplete.
Eculid's geometry has five axioms. The fifth, regarding parallel lines, was not always regarded as entirely self evident, and attempts were made to prove it using the first four. These attempts failed, and were bound to fail. Because it turns out that, given the first four axioms, you can have a variety of equally consistent geometries each with its own statement about parallel lines.
So the four axiom system is incomplete, because a statement about parallel lines (such as "there can be no such things") cannot be proven or disproven regardless of its "real world" status of true/false (whatever that means).
But problem solved! (it seemed)
Because Gauss had an algebraic geometry where the number of parallel lines and all other goemetic theorems could be proved as a consequence of a "metric" (which is basically just a description of the distance between two points. If you assume the metric given by Pythagorus' theorem, you end up with all of Euclidean geometry. Different metrics, all of which are considered "equal" by Gauss' system, would give you different geometries.) So you had a consistent and complete geometry by inbedding it within arithmatic.
Except that the work of Godel shows that arithmatic (and any other axiomatic system) will itself be incomplete. Given an undecidable theorem, we can have a "larger" mathematics, in which the theorem is no longer undecidable. But that system will itself be incomplete.
Dr Adequate
Banned
- Joined
- Aug 31, 2004
- Messages
- 17,766
Goedel was interested in number theory --- the theory of the arithmetic of the natural numbers. The natural numbers are 0, 1, 2, 3 ...
(Note: in some maths modules the natural numbers don't include 0. It's a flexible term in that respect.)
In particular, Goedel was interested in what could be said about them in first order logic.
First order logic allows you to make sentences using phrases such as "there exists an number x", or "for any number x", but not "there exists a set of numbers (of unspecified and possibly infinite size)" or "for all sets of numbers (of unspecified and possibly infinite size)".
This is not a severe restriction on the sorts of properties we can express. For example, suppose I want to state the "twin primes conjecture", which states that there's an infinite number of primes a distance of 2 apart, e.g. 13 & 17, or 21 & 23. Then I can say:
"For any number x, there is a number p such that p > x, and such that there is no number d such that there is a number n such that (d + 1) * (n + 1) = p and such that there is no number c such that there is a number m such that (c + 1) * (m +1) = p + 2."
You don't have to follow that (and I just edited it 'cos I got it wrong the first time) but I just want to make the point that we can say all sorts of things in this apparently restricted language.
When we use it to talk about natural numbers like this, we shall call these statements in first order arithmetic.
Now, what we would like to do is axiomatize first order arithmetic. That is, we would like a set of statements about the natural numbers which are true, and from which we can deduce all the true statements in first-order arithmetic. (This would also allow us to deduce that any such false statement was false).
Such an axiomatization can be done for, e.g., Euclidian geometry, so the idea of such an axiomatization isn't just crazy talk.
For example, you might want to start off like this: "For any number x, there is a number y such that y = x + 1. For any number x, if there exists a number y such that y + 1 = x + 1, then x = y. There does not exist a number such that x + 1 = 0..."
(You may think the last one rather odd, but we're trying to axiomatize the natural numbers 0, 1, 2, 3 ...)
And so on. This helps pin down what you mean by "number" just as Euclid pinned down what he meant by "line" by saying, amongst other things, that a line could be drawn between any two points.
So you might be hopeful of axiomatizing first-order arithmetic.
However, suppose you place various restrictions on the axioms and the methods of reasoning. For example, you would wish the list of axioms to be finite; you might wish them to be first-order themselves, rather than allowing in any second-order axioms; you might require that induction should not be transfinite (I'm not even going to talk about that, relax).
Then Goedel shows that there is no such axiomatization. For any particular set of axioms fulfilling the criteria , there will be some statements in first-order arithmetic (not the same for each set of axioms) such that you can't deduce from that set of axioms whether those statements are true or false. The system of axioms will be incomplete.
The proof itself is cute but hard for a tyro to follow. The underlying reason is rather simpler. No such set of axioms (fulfilling the technical criteria) can exactly pin down the first-order arithmetic of the natural numbers: they will also describe a more exotic system of numbers (indeed, infinitely many other exotic systems of numbers) in which the answers to various first-order questions are different.
Given the restrictions, such a set of axioms simply can't distinguish between the natural numbers you want them to describe and the exotic number systems which you don't.
I hope this helps, but I'm open to questions. There's an old joke about an incompetent maths professor trying to explain the factorial function to a timid undergraduate. In the end, he bursts out: "Oh for heaven's sake, it's only the gamma function restricted to the integers!"
(Note: terms underlined at place of first use.)
(Note: in some maths modules the natural numbers don't include 0. It's a flexible term in that respect.)
In particular, Goedel was interested in what could be said about them in first order logic.
First order logic allows you to make sentences using phrases such as "there exists an number x", or "for any number x", but not "there exists a set of numbers (of unspecified and possibly infinite size)" or "for all sets of numbers (of unspecified and possibly infinite size)".
This is not a severe restriction on the sorts of properties we can express. For example, suppose I want to state the "twin primes conjecture", which states that there's an infinite number of primes a distance of 2 apart, e.g. 13 & 17, or 21 & 23. Then I can say:
"For any number x, there is a number p such that p > x, and such that there is no number d such that there is a number n such that (d + 1) * (n + 1) = p and such that there is no number c such that there is a number m such that (c + 1) * (m +1) = p + 2."
You don't have to follow that (and I just edited it 'cos I got it wrong the first time) but I just want to make the point that we can say all sorts of things in this apparently restricted language.
When we use it to talk about natural numbers like this, we shall call these statements in first order arithmetic.
Now, what we would like to do is axiomatize first order arithmetic. That is, we would like a set of statements about the natural numbers which are true, and from which we can deduce all the true statements in first-order arithmetic. (This would also allow us to deduce that any such false statement was false).
Such an axiomatization can be done for, e.g., Euclidian geometry, so the idea of such an axiomatization isn't just crazy talk.
For example, you might want to start off like this: "For any number x, there is a number y such that y = x + 1. For any number x, if there exists a number y such that y + 1 = x + 1, then x = y. There does not exist a number such that x + 1 = 0..."
(You may think the last one rather odd, but we're trying to axiomatize the natural numbers 0, 1, 2, 3 ...)
And so on. This helps pin down what you mean by "number" just as Euclid pinned down what he meant by "line" by saying, amongst other things, that a line could be drawn between any two points.
So you might be hopeful of axiomatizing first-order arithmetic.
However, suppose you place various restrictions on the axioms and the methods of reasoning. For example, you would wish the list of axioms to be finite; you might wish them to be first-order themselves, rather than allowing in any second-order axioms; you might require that induction should not be transfinite (I'm not even going to talk about that, relax).
Then Goedel shows that there is no such axiomatization. For any particular set of axioms fulfilling the criteria , there will be some statements in first-order arithmetic (not the same for each set of axioms) such that you can't deduce from that set of axioms whether those statements are true or false. The system of axioms will be incomplete.
The proof itself is cute but hard for a tyro to follow. The underlying reason is rather simpler. No such set of axioms (fulfilling the technical criteria) can exactly pin down the first-order arithmetic of the natural numbers: they will also describe a more exotic system of numbers (indeed, infinitely many other exotic systems of numbers) in which the answers to various first-order questions are different.
Given the restrictions, such a set of axioms simply can't distinguish between the natural numbers you want them to describe and the exotic number systems which you don't.
I hope this helps, but I'm open to questions. There's an old joke about an incompetent maths professor trying to explain the factorial function to a timid undergraduate. In the end, he bursts out: "Oh for heaven's sake, it's only the gamma function restricted to the integers!"
(Note: terms underlined at place of first use.)
Dr Adequate
Banned
- Joined
- Aug 31, 2004
- Messages
- 17,766
No, not really. We want to talk about something very precise. We either have to introduce a new term and define it precisely, or substitute the precise definition every time we want to use the term.Yahweh said:
Yes. I did a compilation a while ago on GS&TP. I'll repeat it.
Before I begin, could I point out that no matter how the science-haters blather, there is not one scientific result which rests on a proposition in first order arithmetic which has not been proven.
Here we go.
Aren’t rhetorical questions so much easier than research? : Penrose points out that Godel's and Tuning's theorems about the incompleteness of axiomatic systems depends on the reader's perception that there is a true statement that is not provable. If its not provable, how is it that we 'know' that its true?
The "in other words" gambit : In the field of higher mathematics we find Godel's theorem. In very simple terms, it states that it is not possible to know everything about a particular situation from within that situation… In a similar way to the principles of Godel's theorem, the ancient mystics gained access by deep meditation to a perspective beyond the physical, in order to attain a more complete picture of the physical realm.
You what? : As a third implication of Godel's theorem , faith is shown to be (ultimately) the only possible response to reality… If we dwell in a finite world created by an infinite God, is not a Godelian theorem exactly what we should expect to find? … Godel's proof implies that we must seek final truth outside our finite world…. In light of Godel's proofs and Christ's transfinite claims, won't you yield yourself to God?
The Gnomes Of Uncertainty : Like the great collections of Gnomae of the past this book makes no pretense at convincing hostile minds. It is devoid of argument, persuasion or verbose explanations. In addition, the reader is expected to be familiar with Bell's Theorem, the anthropic principle, Godel's Theorem and the like… Homo sapiens sapiens rarely pays much attention to its thinkers. The human race has driven out Lao Tzu, crucified Jesus, excommunicated Galileo, executed Valentinus and Simon Magus, lynched Hypatia, drowned Hippasus, ignored Heraclitus, ostracized Anaxagoras, murdered Archimedes, drove Frege to despair and Cantor to insanity, starved Mozart, urinated on van Gogh, assassinated Gandhi and King, burned books, destroyed libraries and obliterated entire cultures. So much for sapiens.
That ol’ "In effect" again : Godel's theorem distinguishes in effect between self-conscious beings and inanimate objects.
Goedel proves science is bunk : As I deliberated over the meaning and the implication of Goedel's great work, it became more and more clear that at any stage of its development in future, Science will always remain a mathematical system to which Goedel's theorem will be applicable. All the so-called scientific laws that will be discovered are really the newly added axioms mentioned above. Thus, I concluded that the scientific approach is not sufficient to fathom the depths of Reality.
The General Theory Of Religion… is this taking syncretism too far? : The linkage between mystical union and diverse fields of knowledge comes about because the experience of mystical union brings the mystic into contact with Being which is classically considered to be the root of knowledge. The fields of knowledge linked to mystical union are: metaphysics, ontology, epistemology, philosophy of the mind, cognitive science, neuroscience, parapsychology, psychiatry, psychology, anthropology of consciousness, evolutionary psychology, comparative religion, history of science, sociology, theoretical biology, artificial life, irreversible thermodynamics, theoretical physics, non-linear control theory, Godel's Theorem, and the mathematics of non-linear differential equations associated with any system dynamics model. Phenomena such as entrainment, jump phenomena, shift in loop dominance, bifurcation, and chaos arise out of such equations.
Comparing yourself to someone who's proved what he's said is very nearly as good as proving what you've said : According to intelligent design, Darwin's theory fails for essentially the same reason that Hilbert's program failed. Hilbert's program for mechanizing mathematics failed because Gödel was able to demonstrate that logical rules of inference could not connect all mathematical truths back to a reasonable set of starting points (that is, a recursive set of axioms). Likewise Darwin's program for mechanizing biological evolution fails because it can be demonstrated that the Darwinian mechanism lacks the capacity to connect biological organisms exhibiting certain types of complex biological structures (for example, irreducibly complex or complex specified structures) to evolutionary precursors lacking those structures.
Blow your mind with pure mathematics… and lots and lots of acid, it seems : The need for sweeping revision of the paradigms that organize our approach to the clinical investigation of psychedelic drugs as significant elements in a complex process of human healing and transformation can be clarified by turning to mathematics. KURT GODEL brought a famous paradox from philosophy into mathematics and it seems to have relevance for research with psychedelics as well. GODEL'S theorem holds that the logical consistency and completeness of a system may not be assessed from within that system, in fact in order to assess such properties one must build another system from which to observe and assess the first. With this situation we may then make an assessment of the logical consistency and completeness of the first system but may not be sure of the consistency or completeness of the system that we are observing from. If one applies this to psychedelic research it becomes apparent that when researchers sought to apply previously existing conceptual frameworks to the startling new phenomenon of psychedelic drugs they influenced the results through mechanisms outside of their awareness at the time.
Dr Adequate said:
But transfinites are so nice. I once spent 40 minutes staring at an example solution that I had inherited from the previous TA, trying to figure out what was it about before going to present it to undergraduates. And it took me four years before I found the error in the solution.
As you may have guessed by now, it was about transfinite stuff. (Namely, an example where finding the fixed point of an operator took a transfinite number of steps).
There are many variations on Godel's (1st) incompleteness depending on what you assume about the theory.
In the simplest version you assume that every statement provable is true, in Godel's original proof he only assumed omega-completeness (That the statement "There exists an x such that F(x)" implies one of F(0),F(1),F(2)...F(N)... is true).
Rosser proved that it also holds if the system is simply-consistant (if a statement S is provable then the negation of this statement ~S is not provable).
The importance of this results is that they allow us to check if we can apply Godel's (1st) incompleteness theorem in an entirely technical manner, checking for consistancy without having to bother ourselves with deep philosophical questions such as "What is truth?".
The generalisation of Godel's 2nd incompleteness theorem states that a diagonalisable (technical but simple criterea) simply consistant theory can not assert its own constancy.
It is worth noting that you can create complete consistant theories if you allow proofs of infinite length.
In the simplest version you assume that every statement provable is true, in Godel's original proof he only assumed omega-completeness (That the statement "There exists an x such that F(x)" implies one of F(0),F(1),F(2)...F(N)... is true).
Rosser proved that it also holds if the system is simply-consistant (if a statement S is provable then the negation of this statement ~S is not provable).
The importance of this results is that they allow us to check if we can apply Godel's (1st) incompleteness theorem in an entirely technical manner, checking for consistancy without having to bother ourselves with deep philosophical questions such as "What is truth?".
The generalisation of Godel's 2nd incompleteness theorem states that a diagonalisable (technical but simple criterea) simply consistant theory can not assert its own constancy.
It is worth noting that you can create complete consistant theories if you allow proofs of infinite length.
FireGarden
Philosopher
- Joined
- Aug 13, 2002
- Messages
- 5,047
A rose by any other name....LW said: