# Larger than proof

David Hilbert, the great German mathematician (he died in 1943), had a stupendous, dazzling vision. He hoped and believed that some day mathematicians would construct one vast formal deductive system with axioms so powerful that every possible theorem in all of mathematics could be proved true or false. Such a system would have to be both consistent and complete. Consistent means it is impossible to prove both a statement and its negation. Complete means that every statement in the system can be proved true or false.

In 1931, to the astonishment of mathematicians, a shy, reclusive Austrian, Kurt Gödel, aged twenty-five, shattered Hilbert’s magnificent dream. Gödel showed that any formal system rich enough to include arithmetic and elementary logic could not be both consistent and complete. If complete, it would contain an infinity of true statements that could not be proved by the system’s axioms. What is worse, even the consistency of such a system cannot be established by reasoning within the system. “God exists,” a mathematician remarked, “because mathematics is consistent, and the devil exists because we can never prove it.”

I recall a cartoon by Robert Monkoff which shows a man in a restaurant examining his bill. He is saying to the puzzled waiter: “The arithmetic seems correct, yet I find myself haunted by the idea that the basic axioms on which arithmetic is based might give rise to contradictions that would then invalidate these computations.”

Fortunately, arithmetic can be shown consistent, but only by going outside it to a larger system. Alas, the larger system can’t be proved consistent without going to a still larger system. Many formal systems less complex than arithmetic, such as simple logic and even arithmetic without multiplication and division, can be proved consistent and complete without going beyond the system. But on levels that include all of arithmetic, the need for meta-systems to prove completeness and consistency never ends. There is no final system, such as Hilbert longed for, that captures all of mathematics. “Truth,” as the authors of this new book encapsule it, “is larger than proof.”