July 13, 2011
The logic of science-4: Truth and proof in mathematics
(For previous posts in this series, see here.)
Within mathematics, Euclidean geometry is the prototypical system that demonstrates the power of proof and serves as a model for all axiomatic systems of logic. In such systems, we start with a set of axioms (i.e., basic assumptions) and a set of logical rules, both of which seem to be self-evidently true. By applying the rules of logic to the axioms, we arrive at certain conclusions. i.e., we prove what are called theorems. Using those theorems we can prove yet more theorems, creating a hierarchy of theorems, all ultimately resting on the underlying axioms and the rules of logic. Do these theorems correspond to true statements? Yes, but only if the axioms with which we started out are true and the rules of logic that we used are valid. Those two necessary conditions have to be established independently.
So how does one do that? While we may all be able to agree on the validity of the rules of logic if they are transparent, simple, and straightforward (though there are subtle pitfalls even there) establishing the truth of the axioms is not always easy because things that seem to be obviously true may turn out to be not so.
Furthermore, even assuming for the moment that one knows that the axioms are true and the rules of logic are valid, there are still problems. For example, how can we know that all the theorems that we can prove correspond exactly to all the true statements that exist? Is it possible that there could be true statements that can never be reached however much we may grow the tree of theorems? This is known as the problem of completeness.
There is also another problem known as the problem of consistency. Since the process of proving theorems is open-ended in that there is no limit to how many we can potentially prove, how can we be sure that if keep going and prove more and more theorems we won't eventually prove a new theorem that directly contradicts one that we proved earlier, thus resulting in the absurdity that a statement and its negation have both been proven?
To address this, we rely upon a fundamental principle of logic that 'truth cannot contradict truth', and thus we believe that it can never happen that two true statements contradict each other. Thus establishing the truth of the axioms and using valid rules of logic guarantees that the system is consistent, since any theorem that is based on them must be true and thus no two theorems can contradict each other. Conversely, if we ever find that we can prove as theorems both a statement and its negation, then the entire system is inconsistent and this implies that at least one of the axioms must be false or a rule of logic is invalid.
There is usually little doubt about the validity of the rules of logic that are applicable in a mathematical system (if they are simple and transparent enough) and thus a true set of axioms implies a consistent system of theorems and vice versa. Hence we can at least solve the problem of consistency if we can establish the truth of the axioms, though the completeness problem remains open.
(Those who are familiar with these issues will recognize that we are approaching the terrain known as Godel's theorem. While I will discuss its main results, for those seeking to understand it in more depth I can strongly recommend an excellent little monograph Godel's Proof by Ernest Nagel and James R. Newman, and the clever and entertaining (but much longer) Godel, Escher, Bach: An Eternal Golden Braid by Douglas R. Hofstadter.)
So how do we establish the truth of the axioms? If the system we are dealing with consists of a finite number of objects, we may be able to prove the axioms to be true by seeing if every one of the objects in the system satisfy the axioms by exhaustively applying all the axioms to all the objects and seeing if they hold true in every case. Even if the axioms do not relate to a set of objects, we may be able to construct a model system of objects in which the elements of the model correspond to the elements in the axioms and thus repeat the above process. So, for example, we can take the axioms involving points and lines and so forth in Euclidean geometry (which are abstractions that have purely mathematical relationships with each other) and build a model system of real objects (such as points and lines in space that can be drawn on paper) and see if the axioms apply to the properties of such real objects in real space. Similarly, we can see if the abstract rules for adding numbers correspond to what we get if we add up real objects together.
The catch is that for most systems of interest (such as points and lines in geometry and the integers in number theory), the number of elements in the system is infinite and it is not possible to exhaustively check if (for example) every point and every line that can be drawn in space satisfy the axioms. So then how can we know if the axioms are true? It is not enough that the axioms may look so simple and intuitive that they can be declared to be 'obviously' true. It has been shown that even the most seemingly simple and straightforward mathematical concept, such as that of a 'set', can produce contradictions that destroy the idea that a system is consistent, so we have to be wary of using simplicity and transparency as our sole guide in determining the truth of axioms.
One might wonder why we are so dependent on such a pedestrian method as applying each axiom to every element of the system to establish the truth of axioms and the consistency of systems. Surely we can apply more powerful methods of reasoning to show whether a set of axioms is true even if they involve an infinite number of elements? One would think so except that Godel proved that this could not be done except for very simple systems that do not cover the areas of most interest to mathematicians. Godel "proved that it is impossible to establish the internal logical consistency of a very large class of deductive systems - number theory, for example - unless one adopts principles of reasoning so complex that their internal consistency is as open to doubt as that of the systems themselves." (Nagel and Newman, p. 5, my italics.)
In other words, the price we pay for using more powerful reasoning methods to prove the consistency of some axiomatic system is that we lose transparency and simplicity in the rules of logic used in constructing those very methods and now they cannot be assumed or shown to be valid. As the old saying goes, what we gain on the swings, we lose on the roundabouts. As a result, we arrive at Godel's melancholy conclusion that Nagel and Newman state as "no absolutely impeccable guarantee can be given that many significant branches of mathematical thought are entirely free of internal contradiction." In other words, Godel proved that the goal of proving consistency cannot be achieved even in principle.
This is quite a blow to the idea of determining absolute truth because if we cannot show that a system is consistent, how can we depend upon its results?
Next in the series: The problem of incompleteness