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.
QUESTIONS FOR ATHEISTS AND AGNOSTICS
If we dwell in a finite world created by an infinite God, is not a Godelian
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 Godel's proofs and Christ's transfinite claims, won't you yield yourself to God?