re to Think About
IV. The Law of Excluded Middle
One logical law that is easy to accept is the law of non-contradiction. This law can be expressed by the propositional formula ¬(p^¬p). Breaking the sentence down a little makes it easier to understand. p^¬p means that p is both true and false, which is a contradiction. So, negating this statement means that there can be no contradictions (hence, the name of the law). In other words, the law of non-contradiction tells us that a statement cannot be both true and false at the same time. This law is relatively uncontroversial, though there have been those who believe that it may fail in certain special cases. However, it does lead us to a logical principle that has historically been more controversial: the law of excluded middle.
The law of excluded middle can be expressed by the propositional formula p_¬p. It means that a statement is either true or false. Think of it as claiming that there is no middle ground between being true and being false. Every statement has to be one or the other. That’s why it’s called the law of excluded middle, because it excludes a middle ground between truth and falsity. So while the law of non-contradiction tells us that no statement can be both true and false, the law of excluded middle tells us that they must all be one or the other. Now, we can get to this law by considering what it means for the law of non-contradiction to be true. For the law of noncontradiction to be true, ¬(p^¬p) must be true. This means p^¬p must be false. Now, we must refer back the truth table definition for a conjunction. What does it take for p ^ ¬p to be false? It means that at least one of the conjuncts must be false. So, either p is false, or ¬p is false. Well, if p is false, then ¬p must be true. And if ¬p is false, then p must be true. So we are left with the disjunction p _ ¬p, which is exactly the formulation I gave of the law of excluded middle. So we have just derived the law of excluded middle from the law of non-contradiction.
What we just did was convert the negation of a conjunction into a disjunction,
by considering what it means for the conjunction to fail. The rule that lets us do this is known as De Morgan’s rule, after Augustus De Morgan. Formally speaking, it tells us that statements of the following two forms are equivalent: ¬(p^q) and ¬p_¬q. If you substitute ¬p for q in the first formula, you will have the law of non-contradiction. So you might want to try doing the derivation yourself. You will, however, need the rule that tells us that p is equivalent to ¬¬p. The point of this exercise, however, was to show that it is possible to derive the law of excluded middle from the law of non-contradiction. However, it is also possible to convince yourself of the truth of the law of excluded middle without the law of non-contradiction.
We can show using the method of truth tables that the disjunctive statement
p _ ¬p is always true. As a point of terminology, a statement that is always true, irrespective of the truth values of its components, is called a tautology. p _ ¬p is a tautology, since no matter what the truth value of p is, p_¬p is always true. We can see this illustrated in the truth table belowp ¬p p _ ¬p
T F T
F T T
You can try constructing a similar truth table to show that the law of non-contradiction is also a tautology. Its truth table is a bit more complicated, though. However, since the law of excluded middle is a tautology, it should hold no matter what the truth value of p is. In fact, it should be true no matter what statement we decide p should represent. So the law of excluded middle tells us that every statement whatsoever must be either true or false. At first, this might not seem like a very problematic claim. But before getting too comfortable with this idea, we might want to consider Bertrand Russell’s famous example: “The present King of France is bald.” Since the law of excluded middle tells us that every statement is either true or false, the sentence “The present King of France is bald” must be either true or false. Which is it?
Since there is no present King of France, it would seem quite unusual to claim that this sentence is true. But if we accept the law of excluded middle, this leaves us only one option - namely, to claim that it is false. Now, at this point, we might choose to reject the law of excluded middle altogether, or contend that it simply does not hold in some cases. This is an interesting option toconsider, but then we might need to consider why the method of constructing truth tables tells us that the law of excluded middle holds, if it actually doesn’t. We would also have to consider why it is derivable from the principle of non-contradiction. After all, this sentence doesn’t pose a problem for the law of non-contradiction, since it’s not both true and false. So we’ll ignore this option for now.
Returning to the problem at hand, we must now consider the question of what it means for the sentence “The present King of France is bald” to be false. Perhaps it means “The present King of France is not bald.” But that would imply that there is a present King of France, and he is not bald. This is not a conclusion we want to reach. Russell, in his 1905 paper “On Denoting” presented his own solution to this problem, which comes in the form of a theory of definite descriptions. Under this theory, we can think of there being a hidden conjunctive structure in the sentence “The present King of France is bald.” What the sentence really says is that there is a present King of France, and he is bald. So the fact that there is no present King of France implies that this sentence is false, and we have the solution we need.
Russell’s solution clearly suggests that we can’t just extract the logical structure of a sentence from its grammatical structure. We have to take other things into account. If you’re interested in issues about the relationship between logic and language, you might want to take a class in philosophy of language. The other essay in this section, entitled “Logic and Natural Language”, covers some other issues in this area.
One method of proof that comes naturally from the law of excluded middle is a proof by contradiction, or reductio ad absurdum. In a proof by contradiction, we assume the negation of a statement and proceed to prove that the assumption leads us to a contradiction. A reductio ad absurdum sometimes shows that the assumption leads to an absurd conclusion which is not necessarily a contradiction. In both cases, the unsatisfactory result of negating our statement leads us to conclude that our statement is, in fact, true. How does this follow from the law of excluded middle? The law of excluded middle tells us that there are only two possibilities with respect to a statement p. Either p is true, or ¬p is true. In showing that the assumption of ¬p leads us to a contradictory conclusion, we eliminate the possibility that ¬p is true. So we are then forced to conclude that p is true, since the law of excluded middle is supposed to hold for any statement whatsoever.
Now, I’ve been a bit flippant in talking about statements. Statements can be about a lot of different things. The above discussion illustrated a problem with statements about things that don’t actually exist. I’m sure most people would agree that the designation “the present King of France” refers to something that doesn’t exist. But what about situations where it’s not so certain? One of the main metaphysical questions in the philosophy of mathematics is the question of whether or not mathematical objects actually exist. Think about the question of whether numbers exist. If they do exist, then what are they? After all, they’re not concrete things that we can reach out and touch. But if they don’t exist, then what’s going on in math?
Metaphysical worries have motivated certain people to argue that proofs by contradiction are not legitimate proofs in mathematics. Proponents of intuitionism and constructivism in mathematics place a significant emphasis on the construction of mathematical objects. One way to characterize this position is that in order to show that a mathematical object exists, it is necessary to construct it, or at the very least, provide a method for its construction. This is their answer to the metaphysical question. Suppose we had a mathematical proof in which we assumed an object did not exist, and proved that our assumption lead us to a contradiction. For an intuitionist or a constructivist, this proof would not be a sufficient demonstration that the object does exist. A sufficient demonstration would have to involve the construction of the object.
Even if questions about existence get too complicated, we can still ask the question “What mathematical objects can we legitimately talk about?” The intuitionist answer is that we can talk about those mathematical objects which we know can be constructed.
Simply speaking, intuitionistic logic is logic without the law of excluded middle. I have outlined some small part of the motivation behind developing such a system, but more details can be found in the work of L.E.J. Brouwer and Arend Heyting.