Proving Unprovability
by Keith Devlin @profkeithdevlin
Euclid’s Elements (ca.350BCE) presented geometry and number theory based on axioms, using proofs to establish truth based on those axioms
Proof is the gold standard for determining truth in mathematics. While it is possible to determine that some statements are true by everyday practical rational activities, these are generally the most basic statements, such as 2 + 3 = 5 (with the usual interpretation of this equation). You can prove that by counting.
And you can extend that further to cover examples such as 2,000,000,000 + 3,000,000,000 = 5,000,000,000, which cannot be verified by counting, by giving a simple analogy argument – something along the lines of, “If you had enough time to do all the counting, that is what you would get.” [Anything beyond that involves mathematical reasoning, albeit very simple mathematical reasoning will suffice.]
But for most mathematical statements, you have to rely on proof.
I should note that I’m not using the word “proof” in the formal logic sense here; rather with its everyday meaning among professional mathematicians of a sound, rational argument that convinces other professional mathematicians. (This would include my above example about the sum of two integers in the billions range, which lies on the fuzzy threshold between everyday activities and theoretical arguments.)
The point is, just as mathematics extends our everyday reality by postulating the existence of various abstract entities, it also extends our everyday rational reasoning to include the construction of abstract arguments. And despite the common practice of justifying such arguments by claiming they could be fleshed out to be entirely formal, with no steps left out, such claims remain counterfactual, and in practical terms the validity of a proof comes down to the agreement of its soundness by the mathematical community, usually by way of publication in a respected, peer-reviewed journal.
With proofs at our disposal, we can determine (to the general acceptance by the mathematical community) the truth of a wide range of mathematical statements, many being of high degrees of abstraction, of what is true or what can be performed.
For an example of a mathematical truth established by a proof, take Fermat’s Last Theorem, proved by Andrew Wiles in 1995, a simple and readily understood statement about integer arithmetic (for which the proof can be fully understood by only a handful of professional mathematicians with specialist knowledge). For an example of a simple statement about a mathematical act to be performed, take the Fundamental Theorem of Algebra, that every polynomial can be solved in the system of complex numbers, first conjectured in the early Seventeenth Century and finally proved by Argand in 1806 (with the proof requiring much more than a basic understanding of the complex numbers). [The distinction I am making between statements and procedures is somewhat artificial, but will I think be helpful in the context of this essay.]
It is also the case that we can use the method of proof to establish that statements initially assumed or thought to be true are in fact false or that certain acts that mathematicians had tried to perform cannot in fact be performed.
A classical assumption that was eventually proved to be false is that the rational numbers are sufficient to measure the length of any line, which was famously proved to be false by the Pythagoreans, who showed that the hypotenuse of a right-angled triangle with adjacent sides of length 1 cannot be so measured. An example of a procedure that was proved to be false is the famous Squaring of the Circle problem of Euclidean geometry, to construct, using ruler and compass, a square having the same area as a given circle, which was finally proved to be impossible by Lindemann in 1882 using advanced mathematical techniques the ancient Greeks could not even have dreamed of.
A wonderful article about impossibility proofs was published in the mathematics magazine Quanta recently by David Richeson, a professor of mathematics at Dickinson College in Pennsylvania, titled When Math Gets Impossibly Hard.
Many of the examples Prof Richeson cites are familiar to tertiary-level mathematics instructors, but there is a less hackneyed, topical example right at the end you will likely find interesting.
What all those examples have in common, however, is that they are about impossibility within everyday mathematics, with the impossibility being established by regular mathematical arguments. At no point do you have to raise questions about the axioms for mathematics – a state of affairs that characterizes the approach to mathematics taken by the vast majority of mathematicians.
Of course, all proofs rest ultimately on axioms, even if they are neither mentioned nor considered. The axiomatic approach to mathematics and proof was first established by the Ancient Greeks, and codified in Euclid’s Elements. Euclid developed plane geometry from a set of five axioms.
And it is with Euclid’s axioms that there arises an impossibility proof that differs from the ones in Richeson’s article in that it is about the axiomatization.
For many years, mathematicians attempted to deduce Euclid’s rather complicated-looking Fifth Axiom (a.k.a. the Parallels Postulate) from the other four, far more simple and elegant axioms. In the early to mid-1800s, mathematicians finally resolved the issue by proving that it is impossible to make such a deduction.
They did this by constructing, within Euclidean Geometry, mathematical models that satisfied the first four of Euclid’s axioms but did not satisfy the Parallels Postulate. In one set of models, there were no parallel lines; any pair of lines meet. In the other set of models, through any point not on a line there are infinitely many lines that are parallel to (i.e., never meet) the given line. The existence of any one of these models implies that it cannot be possible to deduce the Fifth Axiom from the first four. (If it were possible to deduce it, it would have to be true in any model of the first four.)
This is all very accessible and fairly widely known, and is frequently taught at high school or college level.
Less well known, and far less accessible, is that you can do something similar with set theory. The significance of this is that, whereas plane geometry is just one branch of mathematics, set theory is a fundamental grounding framework for the whole of mathematics. Anything you can prove about set theory can potentially have ramifications throughout mathematics.
When restricted to finite sets, set theory is at heart a discipline grounded in kindergarten-level activities, but when infinite sets are allowed, the subject rapidly becomes highly technical.
Ernst Zermelo (1831–1953) and Abraham Frankel (1891–1965) formulated an axiom system for Set Theory that is widely accepted today as the basis for the discipline.
To get (Infinitary) Set Theory off the ground, it was imperative to base it on a set of axioms. Several axiom systems have been produced, some of them mutually contradictory, but the one that garnered by far the greatest adoption is a collection of nine statements called the Zermelo-Fraenkel Axioms (ZFC for short, with the “C” indicating that the axioms include the Axiom of Choice – see momentarily), developed in the early Twentieth Century.
The ZFC axioms are self-evident for finite sets, and postulating that they also apply to infinite sets initially seems totally reasonable, but one of them, the Axiom of Choice, then leads to some consequences that are decidedly counter-intuitive. (Google “Banach-Tarski Paradox”.)
The success of ZFC was in large part because it provides a foundation on which to develop the entire edifice of mathematics, that most mathematicians find reasonable.
Although the axioms are sufficient to answer almost all the mathematical questions about sets that have arisen over the years, there were some that eluded solution. One such is Suslin’s Problem, which asks if a certain set of conditions on a linearly-ordered sets guarantees that the set is isomorphic to the real line.
Paul Cohen (1934–2007)
In 1963, Stanford mathematician Paul Cohen invented a new technique whereby one could take a model of ZFC and extend it to a second model in such a way that a given mathematical statement S of interest was forced to be true in the extension. (Cohen’s technique involves some ingenuity to create the extended model so as to ensure that S is indeed true in the resulting model.)
If, for a given statement S, it were possible to create such an extension model in which S were forced to be true, it would follow that it would not be possible to ever prove S to be false. If it were also possible to construct an extension model in which ~S (the negation of S) were forced to be true, it would also follow that it would not be possible to ever prove S were true. Taken together, those two results would show that S was totally undecidable in the ZFC axiom system.
By the time I entered graduate school in 1968, Cohen’s method of forcing had been significantly strengthened and extended (by Robert Solovay, Dana Scott, and others) into a powerful set of tools to prove independence results. Mastering that toolkit provided a fast track for young mathematics graduate students to make a name for themselves: Scour the literature for some mathematical statement that has resisted attempts to prove it over the years, and try to show it was in fact impossible to prove it (from the ZFC axioms).
I certainly could not resist it, and that’s what I set out to do for my Ph.D. research. As it happens, I was eventually seduced to spend more time on a particular axiom for set theory (the Axiom of Constructibility) that could also be used to establish non-provability results, but the method of forcing was one I continued to use frequently in my early research.
Those were heady days, as a whole series of unanswered mathematical questions were, one after another, shown to be absolutely unanswerable (in the ZFC system).
Infinity can be, it seems, not only difficult to pin down, sometimes it is impossible to do so – and mathematicians can prove it!