Gödel’s Theorems and Truth
| Author: Dan Graves Subject: Mathematics & Probability Date: 1/17/98 |
Summary
Famed mathematician Kurt Gödel proved two extraordinary theorems. Accepted by all mathematicians, they have revolutionized mathematics, showing that mathematical truth is more than logic and computation. Does Gödel’s work imply that someone or something transcends the universe?
Truth and Provability
Kurt Gödel has been called the most important logician since Aristotle.(1) Such praise is evidence of how seriously Gödel’s ideas are taken by mathematicians. His two famous theorems changed mathematics, logic, and even the way we look at our universe. This article explains what Gödel proved and why it matters to Christians. But first we must set the stage.
There are many systems of math and logic. One kind is called a formal system. In a formal system there are only a few carefully defined symbols and rules. Examples of commonly used symbols are a, +, x, y, <, and so forth. Following strict rules, symbols are combined into new patterns (proofs). The symbols are actually little more than place-holders. Some represent operations such as addition. Others represent slots that can be filled with numbers or sentences. The reason that empty symbols are used is so that we can be sure that proofs are created without the mistakes that human emotion and misinterpreted words can cause. After a proof is made in a formal system, statements or numbers can be substituted for the symbols, and we then know that the results on the last line of the proof are one hundred percent logical. Serious math often uses formal systems.
A very simple formal system cannot support number theory but such a system is easily proven to be self-consistent. All we have to do is to show that it can’t make a silly proof such as A=Non-A, which would be like saying 2=17. To handle number theory a complex formal system is needed. But as systems get more complex, they are harder to prove consistent. One result is that we don’t know if our number theories are sound or if there are contradictions hidden in them. Gödel worked with such problems.
He especially studied undecidable statements. An undecidable statement is one which can neither be proven true nor false in a formal system. Gödel proved that any formal system deep enough to support number theory has at least one undecidable statement.(2) Even if we know that the statement is true, the system cannot prove it. This means the system is incomplete. For this reason, Gödel’s first proof is called “the incompleteness theorem”.
Gödel’s second theorem is closely related to the first. It says no one can prove, from inside any complex formal system, that it is self-consistent.(3) Hofstadter says, “Gödel showed that provability is a weaker notion than truth, no matter what axiomatic system in involved.”(4) In other words, we simply cannot prove some things in mathematics (from a given set of premises) which we nonetheless know are true.
Shaking up geometry
Gödel’s work really goes all the way back to Greek geometry. Euclid showed that in geometry a few statements, called axioms, could be made at the start and a vast system of sophisticated proofs derived from them. Axioms are ideas which are too obvious to be proven. They just seem as if they must be true. An example is the idea that you can add one to any number and get a bigger number. When a system needs as many axioms as number theory does, doubts begin to arise. How do we know that the axioms aren’t contradictory?
Until the 19th century no one was too worried about this. Geometry seemed rock solid. It had stood as conceived by Euclid for 2,100 years. If Euclid’s work had a weak point, it was his fifth axiom, the axiom about parallel lines. Euclid said that if you were given a straight line, you could draw only one other straight line parallel to it through a set point somewhere outside it.
first line
second line
Around the mid-1800s a number of mathematicians began to experiment with different definitions for parallel line. Lobachevsky, Bolyai, Riemann and others created new geometries by saying that there could be two parallel lines through the outside point or no parallel lines. These geometries weren’t mere games. In fact, it turns out that Riemann’s geometry is better at describing the curvature of space than Euclid’s. Consequently Einstein incorporated Riemann’s ideas into relativity theory.
These new geometries became known as non-Euclidean. They worried mathematicians. Euclid had been like Gibralter. Now one of his axioms had been changed. Since arithmetic is more complex than geometry, how could they be sure its axioms were trustworthy? In a bit of brilliant work, a masterful German mathematician, David Hilbert, converted geometry to algebra, showing that if algebra was consistent, so was geometry. This served as a useful cross check but wasn’t proof positive of either system. The reason is that modern theories are forced to assume that the number line is infinite. Since no one understands infinity, we are naturally uncertain about the systems based on it. Hilbert was confident he had found a way to overcome this difficulty. He laid out a program to do just that.
Paradox in set theory
Uneasy mathematicians hoped that Hilbert’s plan would fulfil its promise because axioms and definitions are based on common sense intuition but intuition was proving to be an unreliable guide. Not only had Riemann created a system of geometry which stood common sense notions on its head, but the philosopher-mathematician Bertrand Russell had bumped into a serious paradox for set theory.
A set is one of the easiest ideas to understand in mathematics and logic. It is any collection of items chosen for some characteristic which is alike for all its elements. For instance, there is the set of all numbers {1,2,3,4,5…..} or the set of planets which circle our sun {Mercury, Venus, Earth, Mars…}. Handling sets seemed fairly simple.
Russell’s paradox was this: Let there be two kinds of sets, he said–normal sets, which do not contain themselves, and non-normal sets, which are sets that do contain themselves. The set of all apples is not an apple. Therefore it is a normal set. The set of all thinkable things is itself thinkable, so it is a non-normal set.
Let ‘N’ stand for the set of all normal sets. Is N a normal set? If it is a normal set, then by the definition of a normal set it cannot a member of itself. That means that N is a non-normal set, one of those few sets which actually are members of themselves. But hold on! N is the set of all normal sets; if we describe it as a non-normal set, it cannot be a member of itself, because its members are, by definition, normal, not non-normal.
Russell did not feel that this paradox was insurmountable. By redefining the meaning of ‘set’ to exclude awkward sets, such as “the set of all normal sets,” he felt that he could create a single self-consistent, self-contained mathematical system. Using improved symbolic logic, he and Alfred North Whitehead set out to do just that. The result was their masterful three volume Principia Mathematica. However, even before it was complete, Russell’s expectations were dashed.
Enter Gödel
The man who showed once and for all that Russell’s aim was impossible was, of course, Kurt Gödel. His revolutionary paper was titled “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” In it he showed that a statement in a system could be made to refer to itself in such a way that it said about itself that it was unproveable. His proof was very complicated involving the mapping of prime numbers onto statements. For example, Gödelese for (x)(x=x) is the unique prime number code 28 X 311 X 58 X 78 X 1111 X 135 X 1711 X 199.
A Gödelian proof
Here is a simpler proof that no number system can generate all the statements which might be true within it. This proof is based on the writings of A. W. Moore and Roger Penrose.
#1. POINT TO PROVE: IT IS IMPOSSIBLE TO DERIVE ALL MATHEMATICAL TRUTH FROM ANY SET OF SELF-EVIDENT AXIOMS.
#2. IF ALL MATHEMATICAL TRUTHS CAN BE DERIVED FROM A CHOSEN SET OF AXIOMS, THEN, IN PRINCIPLE, AN ALGORITHM “A” CAN BE CREATED TO TEST WHETHER OR NOT ANY GIVEN THEOREM DERIVES FROM THE CHOSEN AXIOMSÑI.E.:WHETHER OR NOT IT IS TRUE OR FALSE.
#3. AT PRESENT WE DO NOT HAVE SUCH AN ALGORITHM. IF A CAN BE SHOWN TO BE IMPOSSIBLE, THEN #1 IS ESTABLISHED.
#4. LIST THE FACTUAL STATEMENTS WHICH CAN BE MADE ABOUT NUMBERS. EXAMPLES OF SUCH STATEMENTS ARE “X IS EVEN,” “X IS ODD,” “X IS PRIME”,”X IS LESS THAN 100,” ETC.
#5. CREATE A TABLE OF SUCH STATEMENTS, BEGINNING WITH THE SIMPLEST AND MOVING TO THE MORE COMPLEX. WE WILL CALL OUR STATEMENTS 1, 2, 3, 4… NOW WE NOTE THAT OUR TABLE CAN REFER TO ITS OWN STATEMENTS. SUPPOSE STATEMENT 0 MEANS: “X IS EVEN”, STATEMENT 1 “X IS ODD” ETC… WE LET THE VERTICAL AXIS REPRESENTS THE STATEMENT NUMBER. THE HORIZONTAL AXIS REPRESENTS ALL NUMBERS FROM 0 TO INFINITY. WE THEN ASK OURSELVES FOR EACH NUMBER IN THE HORIZONTAL AXIS, “IS THE VERTICAL STATEMENT TRUE OF THIS NUMBER?” WE WRITE Y BELOW IT IF IT IS TRUE, AND N IF IT ISN’T:
0 1 2 3 ….
0 (EVEN) N N Y N…
1 (ODD) N N Y Y
2 (PRIME) N N Y Y…
3 (x<100 ) Y Y Y Y….
… ………………
#6. FOR ANY NATURAL NUMBER (HORIZONTAL LINE) WE NOW HAVE A METHOD OF DECIDING IF THE VERTICAL STATEMENT IS TRUE. SINCE EVERY POSSIBLE STATEMENT OF THE SYSTEM CAN APPARENTLY BE LISTED AND SINCE EVERY NATURAL NUMBER CAN ALSO BE LISTED, IT APPEARS WE HAVE A COMPLETE SYSTEM OF NATURAL NUMBERS AND AXIOMS. NOTICE THAT EACH STATEMENT ON THE VERTICAL AXIS PRODUCES ITS OWN UNIQUE HORIZONTAL LINE OF Ys AND Ns.
#7. CREATE A NEW WELL-DEFINED SEQUENCE OF Ys AND Ns BY FOLLOWING A DIAGONAL ON THE CHART WE HAVE JUST CREATED. DO THIS BY TURNING EACH DIAGONAL ELEMENT INTO ITS OPPOSITE. THE N AT 0/0 ON THE TABLE BECOMES A Y. THE Y AT 1/1 BECOMES AN N. THE Y AT 2/2 BECOMES AN N. THE Y AT 3/3 BECOMES AN N AND SO FORTH. WE GET YNNN… DOES ANY STATEMENT WHICH HAS ALREADY BEEN GIVEN PRODUCE THIS NEW SEQUENCE?
#8. STATEMENT 0 DOESN’T BECAUSE IT HAS AN N WHERE THE NEW STATEMENT HAS Y. 1, 2, AND 3 DON’T BECAUSE THEY HAVE Ys WHERE THE NEW STATEMENT HAS Ns. THIS WOULD HOLD TRUE TO INFINITY IF WE COULD MAKE OUR TABLE THAT LONG,
#9. WE KNOW WE LEGITIMATELY CREATED THIS NEW Y & N PATTERN, IE: IT IS TRUE. YET NONE OF THE EXISTING AXIOM STATEMENTS PRODUCE THIS DIAGONAL STATEMENT. A NEW AXIOM IS NEEDED TO EXPRESS THE DIAGONAL.
- IF WE WRITE A NEW STATEMENT (CALL IT R) THAT INCLUDES A PROCEDURE FOR MAKING THIS DIAGONAL , AT SPACE R/R A NEW DIAGONAL LETTER WILL APPEAR AND WE WILL HAVE TO ADD STATEMENT S TO REPRESENT THIS NEW SEQUENCE. BUT AT S/S A NEW DIAGONAL NUMBER WILL APPEAR, REQUIRING A STATEMENT T AND SO ON, INFINITELY.
- THEREFORE ALGORITHM A IS IMPOSSIBLE, WHICH IS THE PROOF REQUIRED BY #2. IT IS IMPOSSIBLE TO AUTOMATICALLY DERIVE ALL POSSIBLE MATHEMATICAL TRUTH.
Immediate Implications
What do Gödel’s theorems mean for those who believe there is a God? First, Gödel shattered naive expectations that human thinking could be reduced to algorithms. An algorithm is a step by step mathematical procedure for solving a problem. Usually it is repetitive. Computers use algorithms. What it means is that our thought cannot be a strictly mechanical process. Roger Penrose makes much of this, arguing in Shadows of the Mind that computers will never be able to emulate the full depth of human thought. But whereas Penrose seeks solutions in quantum theory, Christians see man as a spiritual being with understanding that springs not just from the physical organ of the mind but also from soul and spirit.
Second, had Gödel been able to affirm that a complex system is able to prove itself self-consistent, then we could argue that the universe is self-sufficient. His proof points us toward a different understanding, one in which we must either declare the universe to be infinite–as some do(5)–or else look for infinity outside the universe as theists do.
The first possibility, that the universe is infinite, is most unlikely. Everything that we have learned about the universe tells us that it is finite. Astronomers have found details which set absolute limits to its age and dimensions. Physicists have estimated the number of protons in all of creation. And even if there were an infinite amount of natural matter, each particle would still suffer the limitations of matter, for no particle is infinite in itself. The Christian therefore is reasonable when he points to a spiritual creator outside the physical universe as an explanation for what goes on within it. Gödel recognized these implications and struggled to produce an ontological proof for the existence of God (a proof based on the definition of “God”). Gödel was wasting his time in trying to establish this proof. His own theorems strongly suggest that while the finite can infer something bigger than itself, it cannot prove the infinite. As in this article, reason can only show that it is reasonable to believe in a spiritual God who transcends the limits of the universe.
Gödel’s theorem means that the universe cannot be a vast self-contained computer. One modern scientist, Fredekin, suggests that it is.(6) The fundamental particles of nature (in his view) are information bits in that huge machine. Were he right that the universe is effectively a computer, then Gödel’s theorems would require that nature as a whole be understood only outside nature because no finite system is sufficient for itself. This conclusion flows by analogy from what Gödel proved. “…if arithmetic is consistent, its consistency cannot be established by any meta-mathematical reasoning that can be represented within the formalism of arithmetic.”(7)
As a third implication of Gödel’s theorem , faith is shown to be (ultimately) the only possible response to reality. Michael Guillen has spelled out this implication: “the only possible way of avowing an unprovable truth, mathematical or otherwise, is to accept it as an article of faith.”(8) In other words, scientists are as subject to belief as non-scientists. And scientific faith can let a man down as hard as any other. Guillen writes: “In 1959 a disillusioned Russell lamented: ÔI wanted certainty in the kind of way in which people want religious faith. I thought that certainty is more likely to be found in mathematics than anywhere…But after some twenty years of arduous toil, I came to the conclusion that there was nothing more that I could do in the way of making mathematical knowledge indubitable.'”(9)
A or Non-A?
Gödel showed that “it is impossible to establish the internal logical consistency of a very large class of deductive systems–elementary arithmetic, for example–unless one adopts principles of reasoning so complex that their internal consistency is as open to doubt as that of the sytemsthemselves.”(10) In short, we can have no certitude that our most cherished systems of math are free from internal contradiction.
Take note! He did not prove a contradictory statement, that A = non-A, (the kind of thinking that occurs in many Eastern religions). Instead, he showed that no system can decide between a certain A and non-A, even where A is known to be true. Any finite system with sufficient power to support a full number theory cannot be self-contained.
Judeo-Christianity has long held that truth is above mere reason. Spiritual truth, we are taught, can be apprehended only by the spirit. This, too, is as it should be. The Gödelian picture fits what Christians believe about the universe. Had he been able to show that self-proof was possible, we would be in deep trouble. As noted above, the universe could then be self-explanatory.
As it stands, the very real infinities and paradoxes of nature demand something higher, different in kind, more powerful, to explain them just as every logic set needs a higher logic set to prove and explain elements within it.
This lesson from Gödel’s proof is one reason I believe that no finitistic system, even one as vast as the universe, can ultimately satisfy the questions it raises.
References
(1)Moore, Gregory H., “Kurt Friedrich Gödel,” in Dictionary of Scientific Biography. New York: Scribner’s Sons, 1973.
(2)Edward, Paul. Encyclopedia of Philosophy. Macmillan and Free Press, 1967.
(3)Ibid.
(4)Hofstadter, Douglas R., Gödel, Escher, Bach; an Eternal Golden Braid. New York: Vintage, 1979, p.19.
(5)Zebrowski, George. “Life in Gödel’s Universe: Maps all the Way.” Omni. April 1992, p. 53.
(6)Wright, Robert, Three Scientists and Their Gods. New York: Times Books, 1988, pp. 4, 5-80.
(7)Nagel, Ernest and John Newman, Gödel’s Proof. New York: New York University Press, 1958, p. 96.
(8)Guillen, Michael, Bridges to Infinity. Los Angeles: Tarcher, 1983, pp. 117,18.
(9)Ibid, pp. 20,21.
(10)Nagel, p. 6.
See also:
Blanch, Robert, “Axiomatization,” in Dictionary of the History of Ideas Volume I (New York: Scribner’s Sons, 1973) p.170.
Moore, A. W. The Infinite. London and New York: Routledge, 1990.
Newman, James R. The World of Mathematics. New York: Simon and Schuster, 1956. Paulos, John Allen, Beyond Numeracy; Ruminations of a Numbers Man (New York: Knopf, 1991) p. 97.
Penrose, Roger. Shadows of the Mind. 1993.
XXXXXXXXXXXXXXXXXXXXXXXXX
CHRIST SUFFERED AS TRUTH
“Now if we are children [of God], then we are heirsÑheirs of God and co-heirs with Christ, if indeed we share in his sufferings in order that we may also share in his glory.” Rom. 8:17.
In answer to a question put by Pilate, Jesus said, “You are right in saying I am a king. In fact, for this reason I was born, and for this I came into the world, to testify to the truth. Everyone on the side of truth listens to me.”
“What is truth?” Pilate retorted. With this he went out again to the Jews and said, “I find no basis for a charge against him…” Then Pilate took Jesus and had him flogged…
The world met truth with force, but truth won.
Gödel’s proof implies that we must seek final truth outside our finite world. Jesus uttered one of the most ultimate claims ever made by a sane man. “I am the way, the truth, and the life,” he told his disciples just hours before he stood before Pilate.
Will we find truth in a transfinite Christ or will we prefer partial truth from within a system that cannot validate itself?
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
MATHEMATICIANS OF THE INFINITE
The mathematics of the infinite cannot be understood apart from Judeo-Christianity. Although infinitity theory intrigued all civilizations, especially the Greeks, nowhere has it been so important as in Christendom, where all theology hinged on its implications. Augustine in various writings and Boethius, in The Consolation of Philosophy, wrestled with the idea especially in relation to time and God’s eternal exitence. Of Learned Ignorance, by Bishop Nicholas Cusa, argued that at infinity all things become one, just as the arc of an infinitely large circle will flatten into a straight line.
Not surprisingly, the world’s first systematic treatment of infinity was produced by a theologian. The Czech, Bernard Balzano, pioneered the theory of real numbers, established some properties of infinite sets, and became a precurser of modern logic. Like most pioneers he made serious errors. His theology verged on heresy.
The great Cantor, a Protestant Jew with a Catholic mother, was spurred by religious impulses to create transfinite theory. His profoundly original work was spurned by most contemporaries and he was relegated to minor teaching posts. One of Cantor’s greatest contributions was the technique of diagonalization (which we employ in our page seven proof of Gödel). Kronecker savaged Cantor in print and in the classroom. Lacking self-confidence, Cantor came to doubt the worth of his own work. Although the Jesuits seized upon his proofs as validation for certain theological tenets, Cantor’s uncertainty eventually led him into madness.
Gödel, with a Lutheran background, took religious questions seriously and declared himself a theist. Profoundly influenced by his Lutheran predecessor, Leibnitz, he espoused an ontological proof for the existence of God based on his mathematics. This was not successful.
These instances show the power of Christianity to drive first-rate scientific work. No other religion in history has impelled men and women to do such science. The claims of Christianity are so ultimate that at every turn they must either be accepted and substantiated, or denied and challenged. Again and again friend and foe impress new insight upon old theology.
References:
Bell, E. T. Men of Mathematics.
Gillispie, Charles Coulston. Dictionary of Scientific Biography.
Guillen, Michael. Bridges to Infinity.
QUESTIONS FOR ATHEISTS AND AGNOSTICS
If we dwell in a finite world created by an infinite God, is not a Gödelian theorem exactly what we should expect to find?
Why was it that Christian theology and Christian thinkers impelled the major modern developments in infinity theory?
Since mathematical theory ultimately rests on faith, why do you denounce Christianity for resting on faith?
The history of science shows that strictly mechanistic views of the world have consistently failed to hold up. Why not acknowledge that the world is not strictly mechanistic as materialistic explanations must suppose?
In light of Gödel’s proofs and Christ’s transfinite claims, won’t you yield yourself to God?