The Limits of Mathematics

At the beginning of the 20th century, the great German mathematician David Hilbert (1862-1943) advocated an ambitious program to formulate a system of axioms and rules of inference that would encompass all mathematics, from basic arithmetic to advanced calculus. His dream was to codify the methods of mathematical reasoning and put them within a single framework.

Hilbert insisted that such a formal system of axioms and rules should be consistent, meaning that one can't prove an assertion and its opposite at the same time. He also wanted a scheme that is complete, meaning that one can always prove a given assertion either true or false. He argued that there had to be a clear-cut mechanical procedure for deciding whether a certain proposition follows from a given set of axioms.

Hence, given a well-defined system of axioms and appropriate rules of inference, it would be possible, though not actually practical, to run through all possible propositions, starting with the shortest sequences of symbols, and to check which ones are valid. In principle, such a decision procedure would automatically generate all possible theorems in mathematics.

What Hilbert was saying is that "we can solve a problem if we are clever enough and work at it long enough," mathematician Gregory J. Chaitin of the IBM Thomas J. Watson Research Center writes in The Limits of Mathematics. "He didn't believe that in principle there was any limit to what mathematics could achieve."

In the 1930s, Kurt Godel (1906-1978), followed by Alan Turing (1912-1954) and others, proved that no such decision procedure is possible for any system of logic made up of axioms and propositions sufficiently sophisticated to encompass the kinds of problems that mathematicians work on every day.

"What Godel showed was that if you assume that [the system is] consistent, then you can show it's incomplete," Chaitin says.

In Godel's realm, no matter what the system of axioms or rules is, there will always be some assertion that can be neither proved nor invalidated within the system. Indeed, mathematics is full of conjectures assertions awaiting proof with no assurance that definitive answers even exist.

Turing's argument involved mathematical entities known as real numbers. Suppose you happen upon the number 1.6180339887. It looks vaguely familiar, but you can't quite place it. You would like to find out whether this particular sequence of digits is special in some way, perhaps as the output of a specific formula or the value of a familiar mathematical constant.

It turns out that the given number is the value, rounded off, of the so-called golden ratio, which can also be written as (1 + SQRT5)/2, an example of a real number. Given that expression, which represents an infinite number of decimal digits, you can compute its value to any number of decimal places. Going in the opposite direction from the given rounded-off number to the expression, however, is much more difficult and problematic.

For example, it's possible that if the mystery number were available to an extra decimal place, the final digit would no longer match the decimal digits of the golden ratio. You would have to conclude that the given number is not the golden ratio. Indeed, the extended strings of digits could represent the output of a completely different expression or formula or even part of a random sequence. It's impossible to tell. There isn't enough information available.

To sort through the relationship between random sequences and the types of numbers that mathematicians and scientists use in their work, Chaitin has defined the "complexity" of a number as the length of the shortest computer program (or set of instructions) that would spew out the number.

Suppose the given number consists of 100 1s. The instruction to the computer would simply be to "print 1, 100 times." Because the program is substantially shorter than the sequence of 100 1s that it generates, the sequence is not considered random. Instructions for printing out a sequence of alternating 1s and 0s lengthens the program only slightly, so that sequence doesn't count as random. If the sequence is disorderly enough that any program for printing it out cannot be much shorter than the sequence itself, the sequence counts as random. Hence, a random sequence is one for which there is no compact description.

Chaitin proved that no program can generate a number more complex than itself. In other words, "a 1-pound theory can no more produce a 10-pound theorem than a 100-pound pregnant woman can birth a 200-pound child," he likes to say.

Conversely, Chaitin also showed that it is impossible for a program to prove that a number more complex than the program is random. Hence, to the extent that the human mind is a kind of computer, there may be a type of complexity so deep and subtle that our intellect could never grasp it. Whatever order may lie in the depths would be inaccessible, and it would always appear to us as randomness.

At the same time, proving that a sequence is random also presents insurmountable difficulties. There's no way to be sure that we haven't overlooked a hint of order that would allow even a small compression in the computer program that produces the sequence.

From a mathematical point of view, Chaitin's result suggests that we are far more likely to find randomness than order within certain domains of mathematics. Indeed, his complexity version of Godel's theorem states: Although almost all numbers are random, there is no formal axiomatic system that will allow us to prove this fact.

Chaitin's work suggests that there is an infinite number of mathematical statements that one can make about, say, arithmetic that can't be reduced to the axioms of arithmetic, so there's no way to prove whether the statements are true or false by using arithmetic. In Chaitin's view, that's practically the same as saying that the structure of arithmetic is random.

"What I've constructed and exhibited are mathematical facts that are true . . . by accident," he says. "They're mathematical facts which are analogous to the outcome of a coin toss. . . . You can never actually prove logically whether they're true."

That doesn't mean that anarchy reigns in mathematics, only that mathematical laws of a different kind might apply in certain situations. In such cases, statistical laws hold sway and probabilities describe the answers that come out of equations. Such problem arise when one asks whether an equation involving only whole numbers has an infinite number of whole-number solutions, a finite number, or none at all.

"In the same way that it is impossible to predict the exact moment at which an individual atom undergoes radioactive decay, mathematics is powerless to answer particular questions," Chaitin states. "Nevertheless, physicists can still make reliable predictions about averages over large ensembles of atoms. Mathematicians may in some cases be limited to a similar approach."

That makes mathematics much more of an experimental science than many mathematicians would be willing to admit.

References:

Chaitin, Gregory J. 1998. The Limits of Mathematics: A Course on Information Theory and the Limits of Formal Reasoning. Singapore: Springer-Verlag.

Johnson, George. 1998. Useful invention or absolute truth: What is math? New York Times (Feb. 10).

Kleiner, Israel, and Nitsa Movshovitz-Hadar. 1997. Proof: A many-splendored thing. Mathematical Intelligencer 19(No. 3):16-26.

Peterson, Ivars. 1998. The Jungles of Randomness: A Mathematical Safari. New York: Wiley.

______. 1990. Islands of Truth: A Mathematical Mystery Cruise. New York: W.H. Freeman.

Tymoczko, Thomas, ed. 1998. New Directions in the Philosophy of Mathematics: An Anthology (Revised and Expanded Edition). Princeton, N.J.: Princeton University Press.

Vellemman, Daniel J. 1997. Fermat's last theorem and Hilbert's program. Mathematical Intelligencer 19(No. 1):64-67.

Additional information about Gregory Chaitin and his writings is available at http://www.cs.auckland.ac.nz/CDMTCS/chaitin.

Comments are welcome. Please send messages to Ivars Peterson at ip@sciserv.org.

Ivars Peterson is the mathematics and physics writer and online editor at ScienceNews (http://www.sciencenews.org/). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, FatalDefect, and *The Jungles of Randomness: A Mathematical Safari. His current works in progress are an updated, 10th anniversary edition of The Mathematical Tourist (to be published in 1998 by W.H. Freeman) and Fragments of Infinity: A Kaleidoscope of Mathematics and Art (to be published in 1999 by Wiley).

NOW AVAILABLE The Jungles of Randomness: A Mathematical Safari by Ivars Peterson. New York: Wiley, 1997. ISBN 0-471-16449-6. $24.95 US.