Modus ponens, modus tollens, and proof by contradiction

In a recent post, I gave a (non-rigorous, sketchy) argument that shows there can’t be a one-to-one correspondence between the natural numbers and the real numbers. There’s a cliché that one “can’t prove a negative,” or, more specifically, that it’s not possible to prove that something doesn’t exist. But it is. We do it by assuming that what we want to prove is false — assume the positive to prove the negative — and showing that the assumption results in a contradiction.

Let’s look at how a conditional statement works, logically. Suppose I tell you that the following statement is true:

If it’s raining, then I’m at home.

If you live a few blocks away, when tomorrow comes you can look outside and see whether it’s raining. If it is, then you can conclude that I’ll be at home. But what if it’s clear and sunny? Does that mean I’ll be out?

It does not. My statement said nothing about what happens when it doesn’t rain. In plain English, of course, there’s other context, and semantic expectations about what we say. But considering it as a purely logical construct, you know nothing about my whereabouts if it’s sunny.

Now, what if you live across the country? You can’t look outside, but you can phone me — let’s assume that I’ll always answer the phone if I’m home. If you call and I’m not there, what can you conclude? And what if you call and I am there?

Well, there are four possibilities:

1. I’m home, and it’s sunny.
2. I’m home, and it’s raining.
3. I’m out, and it’s sunny.
4. I’m out, and it’s raining.

It should be clear that the only one that contradicts my statement is 4. As I said earlier, I’ve said nothing at all about what happens when it’s sunny, so 1 and 3 are consistent. And 2 is exactly what I described in my statement.

So, if you wanted to “prove” that it’s not raining where I live, you could see if I’m at home, or out. If I’m out, you have your proof that it’s not raining, since possibility 4 has been eliminated as being inconsistent with what we know to be true.

To put this into symbolic logic, let’s call P the statement that “it’s raining”, and let Q be the statement “I’m at home.”

If P then Q.

...or, in symbolic logic notation:

P → Q

Looking at the examples above, including the cross-country example, we can see these logical equivalencies:

P → Q

~Q → ~P   (the contrapositive)

~P ∨ Q

All three statements have the same truth values, and are logically equivalent. And to add a bit of cool terminology to this, we have two methods of proof to name, which take advantage of the above equivalences:

• Modus Ponens:

  given P → Q
  given P
  therefore Q

• Modus Tollens:

  given P → Q
  given ~Q
  therefore ~P

Proof by contradiction is, then, an application of modus tollens: if we show that some proposition P implies an impossible conclusion Q, then because we know ~Q, modus tollens tells us that ~P must be true (that is, our assumption was wrong, and P must be false).

These types of proofs are widely used in mathematics, and I’ll give a nice example here,[1] of a proof that there is no largest prime number.[2]

Definition: A prime number is a natural number p such that the only factors of p are 1 and p.

Proposition: There exists a “largest” prime number. Formally, there exists a prime number pmax, such that for all prime numbers pi, pi ≤ pmax.

If such a number exists, then, of course, the set of prime numbers, P is finite. We can therefore compute the number np, which is the product of all prime numbers.

np  :=

∏ p∈P

p

Consider np+1. Clearly, np+1 > pmax. Also, when we divide np+1 by any prime number other than 1, we get a remainder of 1, meaning that np+1 has no prime factors. Since we can reduce any factor down to prime factors, this means that np+1 has no factors other than 1 and np+1, and it is, therefore, prime. So:

np+1 is a prime number and np+1 > pmax.

This contradicts our proposition, proving that our proposition was false. Therefore:

There does not exist a “largest” prime number. Formally, there does not exist a prime number pmax, such that for all prime numbers pi, pi ≤ pmax.

 

---

[1] The example assumes, as usual, the axiom of choice. Quite a critical bit, that. We’re safe, there, because the customary set theory these days is Zermelo-Fraenkel with the axiom of choice.

[2] Note that, while no largest prime number exists, there is a largest number that we know to be prime. In fact, since I first wrote this up, a new largest known prime has been discovered: 243,112,609-1, a phenomenally large number with around 13 million digits. Large though that be, there are nevertheless many more that are larger still — a countably infinite number of them, in fact.

There’s a small error, by the way, in the last paragraph of the Science News article (at least at the time of this writing); did you catch it?:

Current cryptographic systems rely on the challenge of factoring large primes. This task is distinct from verifying primeness, but the root difficulty is the same: limited computing power. Through this prize, “we maintain a pulse on what people might be able to do in breaking cryptosystems,” Noll says.

Factoring prime numbers is, of course, trivial, by definition. What they mean to say is that cryptographic systems rely on the challenge of factoring products of large primes. If p and q are large prime numbers, it’s very difficult to factor (p * q) into p and q.