Monday, November 23, 2015
Thoughts On Proofs by Contradiction
by Carl Pierer
Among the many tools available to mathematicians attempting to prove a statement is something called "proof by contradiction" or reduction ad absurdum. The general method of the proof is a very smug one: Let the statement to be proved be Φ. The strategy, then, is to suppose that Φ is false and to consequently derive a contradiction. Now there are quite a few, infinitely many one might say, ways of going about this. This shan't be our concern. What is of interest here is the question as to what kind of contradiction forms the end of such a proof. Let us distinguish 2 cases:
- Internal contradiction. The proof takes the form of:
Suppose ¬Φ. Then γ.
Contradiction! ∴ Φ.
Here, we deduce an immediate consequence (γ) from the assumption that ¬Φ and then proceed by a sequence of logical steps (Δ) to show that this leads to ¬γ – a blatant contradiction. For example, let us say our statement to prove is:
Φ: is not a rational number
Then, ¬Φ is " is a rational number" and an immediate consequence of this would be:
γ: Then we can write √2 = m/n , where m,n are natural numbers, such that m,n are coprime. That is, m/n is an irreducible fraction.
One standard proof then goes as follows:
1. Then, 2 = m2/n2
2. So, 2n2 = m2
3. This means, m is even.
4. So m can be written as m = 2k for some natural number k.
5. Thus: 2n2 = (2k)2
6. Ergo, 2n2 = 4k2
7. And hence: n2 = 2k2
8. So n is even.
9. Then 2 divides both n and m.
10. Therefore, ¬γ.
Now, we have the desired contradiction, and therefore we conclude Φ.
- External contradiction. Here, the proofs take the following form:
Suppose ¬Φ. Then:
But ¬μ! Contradiction. Therefore, Φ.
Here, ¬μ is some generally accepted mathematical truth, such as 1 ≠ 2. In contrast to the internal contradiction, it need not be a statement that is a consequence of ¬Φ. ¬μ is some statement in the general corpus of mathematical truths (i.e. proven statements) and is not necessarily linked in its content to Φ.
Now, the astute reader might question the meaningfulness of the distinction between internal and external contradiction. In particular, since μ appeared in the proof of Φ, there must be a sequence of logical derivations that relate the two. So, one might ask, how much sense does it make to distinguish between a "direct" consequence of ¬Φ and one that is related by a longer sequence of logical steps? Certainly, formally speaking, such an objection is valid. But there seems to be an intuitive sense in which some consequences are more immediate than others, and this is all that is needed at this stage.
In 1914, the French physicist Pierre Duhem (1861-1916) published his "La Théorie Physique: Son Objet, Sa Structure". This work about the nature and method of physics as a science contains his most celebrated and influential contribution to the philosophy of science. Duhem strongly criticised the notion of a "crucial experiment", that is some single experiment that could establish the truth of two competing scientific theories. Joined in this task by W.V.O. Quine (1908-2000) about 40 years later, who made the idea more precise and powerful, this became known as the Duhem-Quine Thesis.
According to them, our beliefs form an inter-connected whole. A single hypothesis by itself does enable us to make any testable predictions at all. It is only in light of a broader theory and in conjunction with a bunch of background assumptions that a hypothesis has empirical consequences. In other words, a hypothesis acquires its meaning only because a host of other assumptions underlie it. Take for example, an experiment, where theory A predicts that substance β is observable under a microscope. A multitude of theoretical assumptions about the correct workings of the microscope, a sophisticated optical theory, the influence and disturbances caused by the environment, etc., have to be in place for this hypothesis to require significance. In particular, if substance β is not observable – what has failed us? Is it the beliefs we hold about optics? The belief that the setup of the experiment was correct? Or the tested hypothesis?
Quine and Duhem suggest that this is the reason there can be no such thing as a "crucial" experiment that serves to refute a particular theory. Quine goes on to suggest that by making suitable modifications in our web of beliefs, we can accommodate any outcome of the experiment.
Looking back at the proof by external contradiction, the method is that we suppose the sentence to be proved is false and show that this leads to a contradiction with another, established sentence. But then, aren't we in precisely the same situation as Duhem's scientist facing the outcome of her experiment? Couldn't we go equally well down either road, that is: accept ¬Φ and μ and reject ¬μ? To be quite clear, opting for the latter would have tremendous repercussions. If μ is something as pervasive as 2≠1, then much of what we have established in mathematics at the moment will be incompatible. Yet, in and of itself, this cannot be reason enough to abandon the approach – precisely, because at each instance where we face a contradiction, we can repeat opting for the "other" choice.
Perhaps we can make this idea a little bit more precise. The methods of logic, in general are devised so as to allow us to discover valid patterns of reasoning. This is often phrased as: a logically valid argument is one where if the premises are true, the conclusion has to be true as well. Now, the logical system works from certain axioms, that is, sentences that are taken to be true. If we believe that the rules of inference that are accepted in the logical system are incapable of producing a contradiction (that is, one valid deduction from the axioms arrives at ρ while a different but also valid deduction arrives at ¬ρ), then changing the axioms should not make the system inconsistent. So, say we think about the logical system as codifying all valid inferences. Then, if the inputs (i.e. axioms) are true, so are the outputs.
Now, axioms in established branches of mathematics are likely to be of the sort 2≠1. But what if one of our deductions leads to the conclusion that ¬(2≠1)? The above argument, if correct, seems to suggest that we could develop an equally consistent, albeit completely different corpus of mathematical statements. And isn't this precisely what – on a more limited scale – happened in the development of non-euclidean geometry?
Looking back at the proofs by internal contradiction, there is a different way to take upon encountering a contradiction. Instead of changing a belief very central to mathematics, we can change some of the logic axioms underlying the reasoning, rather than mathematical statements.
One of the most notable features of Intuitionism in mathematics is the rejection of the law of bivalence, or tertium non datur, which states that any proposition is either true or false – there is no third option. There are several ways to cache this out philosophically. For example, one might say that mathematical statements are only true or false if proven to be so. So, taking for instance the Goldbach Conjecture, it is neither true nor false that every even integer greater than two can be expressed as the sum of two primes, because this statement is still an unsolved problem. The denial of tertium non datur has far reaching consequences. Indeed, it has been shown that intuitionist mathematics is not simply a restriction of classical mathematics, but that that the two are incompatible. In particular, the kind of reasoning employed in the proofs by contradiction as mentioned earlier, are invalid.
Consider the case of "internal contradiction". The argument can be rendered more formally as:
2. Therefore, γ
3. If γ then Δ
4. Δ implies ¬γ
5. Hence, ¬¬Φ
But now, the last step requires us to move from ¬¬Φ to Φ that is to delete the double negation. Yet, this step relies on the fact that tertium non datur. Because if there is a third way, then "It is not the case that not Φ" is not the same as "It is the case that Φ". In particular, a "proof by contradiction" can only prove negative statements.
This is only a tiny aspect of intuitionist mathematics, which has been developed to quite some detail over the last century. But it serves well to illustrate that (1) denying logical axioms such as tertium non datur can be meaningfully done, even in mathematics, and (2) what this means in context of proofs by contradiction.
This essay raised questions about the mathematical method of proof by contradiction or reductio ad absurdum. In combination with the Duhem-Quine Thesis about the underdetermination of scientific theory, this yielded that if there are fixed truths in the corpus of mathematical statements, these need to be true in virtue of something other than mere consistency. As applied to logical axioms, it was pointed out that this leads in the areas of constructive mathematics and intuitionism in particular.
There are many more questions to be asked about this. One might wonder what exactly this criteria of truth for mathematical statements could be – other than consistency? Perhaps there is no truth to the matter of mathematical questions? Other questions can be asked about what happens if we deny certain logical axioms, such as the law of bivalence or the law of non-contradiction? Would this upset our established set of mathematical truths or can most of them be recovered?
Posted by Carl Pierer at 12:35 AM | Permalink