GODEL'S THEOREMS AND TRUTH

By Daniel Graves,  MSL

Summary

Famed mathematician Kurt Godel proved two extraordinary theorems. Accepted by  all mathematicians, they have revolutionized mathematics, showing that mathematical truth is more than logic and computation. Does Godel's work imply that someone or something transcends the universe?

Truth and  Provability

Kurt Godel has been called the most important logician since Aristotle.(1) Such praise is evidence of how seriously Godel'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 Godel 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. Godel 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. Godel 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, Godel's first proof is called "the incompleteness theorem".

Godel'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, "Godel 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

Godel'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 Gibraltar. 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 crosscheck 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 fulfill its promise  because axioms and definitions are based on commonsense intuition but intuition was proving to be an unreliable guide. Not only had Riemann created a system of  geometry which stood commonsense 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 that 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  Godel

The man who showed once and for all that Russell's aim was impossible was, of  course, Kurt Godel. 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, Godelese  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 Godelian 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.

10. 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.

11. 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 Godel's theorems mean for those who believe there is a God? First, Godel 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 Godel 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 that 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. Godel recognized these implications and struggled to produce an ontological  proof for the existence of God (a proof based on the definition of "God"). Godel  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.

Godel'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 Godel'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 Godel 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 Godel'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?

Godel 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 sytems themselves."(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 Godelian 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 Godel's proof is one reason I believe that no finite system,  even one as vast as the universe, can ultimately satisfy the questions it  raises.

References

(1)Moore, Gregory H., "Kurt Friedrich Godel," 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., Godel, Escher, Bach; an Eternal Golden Braid. New York: Vintage, 1979, p.19.

(5)Zebrowski, George. "Life in Godel'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, Godel'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.

Godel'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 infinitely 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 existence. 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 precursor 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 Godel). 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.

Godel, 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.

[Home] [Syllabus] [Sessions] [Writing Code] [Help] [Setup] [Instructor]