14
$\begingroup$

When teaching proofs by contradiction of an implication P => Q, one starts by assuming both P and (not Q), and then reaches a contradiction. The problem is, most elementary proofs of this type are "fake," in the sense that the assumption "P" is never used. A typical example is proving the proposition if n^2 is even then n is even by contradiction. One assumes both "n^2 is even" and "n is odd" Then one shows that if n is odd then n^2 is also odd, reaching a contradiction with the assumption "n^2 is even." In reality, however, this assumption was never used in the argument, so this is what I call a "fake" proof by contradiction, since one can rephrase it into a contrapositive proof.

My question, then, is, can anyone provide a relatively simple (for educational purposes) "true" proof by contradiction of a proposition "P => Q" in which one would really need BOTH the assumption (not Q) and the assumption (P) to actually reach some kind of contradiction?

$\endgroup$
11
32
$\begingroup$

As you've noticed, there are (at least) three potential ways of proving an implication $p \Rightarrow q$:

  1. Assume $p$, and conclude $q$.
  2. Assume $\neg q$, and conclude $\neg p$.
  3. Assume both $p$ and $\neg q$, and derive a contradiction.

If I understand you right, you're asking for a proof which is of the third kind. Moreover, you're asking for a proof which is essentially of the third kind, rather than being a proof which is essentially a proof of the first or second kind, but which has been dressed up as a proof of the third kind.

In other words, you're asking for a proof which takes $p$ and $\neg q$ and "meets in the middle," rather than starting with one premise and reasoning all the way to the negation of the other premise.

My suggestion is below.


Theorem. If a number $x$ is odd, then $x$ is not even. (A number is defined as even if it is of the form $2n$ for integer $n$, and odd if it is of the form $2n + 1$ for integer $n$.)

Proof. We will prove this by contradiction. Suppose that $x$ is odd and even. Then, for some integer $n$ and some integer $p$,

$$x = 2 n$$

and

$$x = 2 p + 1.$$

This means that

$$\begin{align*} 2 n &= 2 p + 1\\ 2 n - 2 p &= 1\\ n - p &= \tfrac12. \end{align*}$$

However, since $n$ and $p$ are integers, $n - p$ is an integer, whereas $\frac12$ is not an integer. This is a contradiction, and so our proof is complete.

$\endgroup$
5
  • $\begingroup$ Nice example, upvoted. It seems that this case boils down to whether we can prove that n is not an integer from the premises [p is an integer and n-p=0.5], without using contradiction. (in your proof you assume that if n is an integer, n-p cannot be 0.5, contradiction. But is there a "direct" way to go from n-p=0.5 to n is not an integer?) $\endgroup$
    – justhalf
    Oct 9 at 11:13
  • $\begingroup$ Trying to work from "n-p=0.5" is starting at the wrong level. A direct proof by contrapositive would start from "x is even" and prove "x is not odd", or more explicitly, start from "there exists an integer $n$ such that $x=2n$" and prove "there does not exist an integer $p$ such that $x=2p+1$". It's quite doable, but more awkward than the proof by contradiction. $\endgroup$ Oct 9 at 12:43
  • $\begingroup$ @user2357112supportsMonica I was in the process of trying to prove exactly the last formulation you mentioned when I ended up there. So x=2n, for all p such that x=2p+1, I want to prove that p is not an integer. Maybe I am indeed attacking it from a wrong angle. How would you do it? $\endgroup$
    – justhalf
    Oct 9 at 14:22
  • 1
    $\begingroup$ @justhalf: Assume $x=2n$ for some integer $n$. $1$ is not divisible by $2$, so for any integer $p$, we have $2(n-p) \ne 1$. Rearranged, this becomes $2n \ne 2p+1$, so $x \ne 2p+1$, so for any integer $p$, we have $x \ne 2p+1$. By De Morgan, there does not exist an integer $p$ such that $x=2p+1$, which means that $x$ is not odd. $\endgroup$ Oct 9 at 14:36
  • $\begingroup$ So we do start from n-p=0.5, but the part I missed was using divisibility to show 2(n-p)!=1. Nice. Thanks! $\endgroup$
    – justhalf
    Oct 10 at 7:41
9
$\begingroup$

I think you are overlooking the fact that proof by contradiction must invoke the tautology $(P\ \hbox{or}\ \neg P)$, called the law of excluded middle.

To prove $P\Rightarrow Q$ by contradiction, we show that $(\neg Q\Rightarrow\neg P)$. The next step, which is where we deduce the conclusion $Q$, is where we must invoke the assumption that $P$ is "true."

So in proof by contradiction, we do not actively use $P$. Instead, we passively use the assumption $P$ in the last step of the proof when we invoke the law of excluded middle. In effect, proof by contradiction swaps the active use of $P$ that we would use in a direct proof with active use of $\neg Q$.

$\endgroup$
5
  • 4
    $\begingroup$ You are confusing "proof by contradiction" with "proof by contrapositive." If you do not "actively use P" this is in fact a proof by contrapositive (not Q implies not P), not by contradiction. A "true" proof by contradiction will need to "actively" use P. $\endgroup$ Oct 9 at 20:36
  • $\begingroup$ what about square root of 2 is irrational? $\endgroup$
    – BCLC
    Oct 9 at 23:17
  • $\begingroup$ @BCLC the proof you are thinking of is a direct proof of the statement that $\sqrt{2}$ is irrational, at least in classical logic where $\neg\neg S$ is equivalent to $S$. The proof is "proof of negation," which is not the same as proof by contradiction. Here is a good reference Bauer $\endgroup$
    – user52817
    Oct 10 at 1:19
  • 1
    $\begingroup$ @Juan Tolosa Using $P\wedge\neg Q$ and reaching a contradiction is called "proof of negation" because you actively use the negation of $P\rightarrow Q$, namely $P$ and $\neg Q$. So you reach a contradiction to the negation of the implication. But proof by contradiction uses the logically equivalent contrapositive of $P\rightarrow Q$, which is $\neg Q\rightarrow\neg P$. I guess we just have different vocabularies here! $\endgroup$
    – user52817
    Oct 10 at 5:14
  • $\begingroup$ user52817 i was taught in classes that such proof is proof by contradiction. so it's in a different sense of the term proof by contradiction in the sense that OP is talking about (and not necessarily in the sense that you're talking about) ? $\endgroup$
    – BCLC
    Oct 10 at 18:19
8
$\begingroup$

No, I suspect this situation never occurs. Here is why:

If $P$ really implies $Q$, then we know logically that $\neg Q$ implies $\neg P$.

Thus if you assume $\neg Q$, you will be able to deduce $\neg P$.

In this way, you never "need" the assumption $P$.

$\endgroup$
4
  • 3
    $\begingroup$ But it might be much easier to prove $P$ implies $Q$ by showing $P$ and not $Q$ leads to a contradiction than by showing not $Q$ implies not $P$ directly. The point is that your "will be able" step might require a longer argument. $\endgroup$
    – KCd
    Oct 9 at 20:11
  • 2
    $\begingroup$ @KCd The question explicitly states "in which one would really need BOTH the assumption (not Q) and the assumption (P) to actually reach some kind of contradiction?" If the question was instead "in which one would prefer..." or "in which it would be easier..." then I would agree. $\endgroup$
    – Chris Cunningham
    Oct 9 at 21:55
  • $\begingroup$ what about square root of 2 is irrational? $\endgroup$
    – BCLC
    Oct 9 at 23:18
  • $\begingroup$ @BCLC Are you asking whether it is possible to prove the implication ($x$ is rational) implies ($x^2 \neq 2$)? $\endgroup$
    – Chris Cunningham
    Oct 9 at 23:39
2
$\begingroup$

Claim: Compact ($P$) metric space implies sequentially compact ($Q$).

Proof. Assume $P\land \lnot Q$. We use $\lnot Q$ to construct an infinite sequence with no limit points. Because there are no limit points, each point in our space has an open neighbourhood containing only finitely many points of the sequence. These neighbourhoods form a cover and we use $P$ to pick out a finite subcover. But a finite subcover cannot contain the infinite sequence. □

This was the simplest example I could find. You can also consider proofs using strategy stealing arguments, which can be simpler to explain informally.


As to how this relates to other answers saying proof by contradiction is logically equivalent to proof by contrapositive. You can view this as a proof of $\lnot Q \Rightarrow \lnot P$. The contradiction arises because it is the easiest way to prove $\lnot P \Leftrightarrow P\to\bot$, which some like to call a proof of negation. A contradiction is in some sense unavoidable when proving a negative, e.g. prove $\sqrt2$ is not rational.

$\endgroup$
2
$\begingroup$

I think you may be looking at this the wrong way.

There are three distinct logical rules which are all equivalent. Each rule holds for all propositions $P$ and $Q$.

Rule 1: $\neg \neg P \implies P$

This is the classic "proof by contradiction" rule.

Rule 2: $(\neg P \implies \neg Q) \implies (Q \implies P)$

This is "proof by contrapositive".

Rule 3: $P \lor \neg P$

This is the so-called "law of excluded middle" (a name which I don't like, but that's another story).

Each of these logical rules can be proved using the others (and the other rules of constructive logic, also known as intuitionist logic).

(2) $\to$ (1): Take $Q$ to be true. Then $\neg P \implies \neg Q$ is the statement that $\neg P$ implies false, which is the same as saying $\neg \neg P$. Conversely, saying $Q \implies P$ is the same as saying that true implies $P$, which is equivalent to $P$. So $(\neg P \implies \neg Q) \implies (Q \implies P)$ is equivalent to $\neg \neg P \implies P$.

(3) $\to$ (2): Suppose $\neg P \implies \neg Q$. Suppose $Q$. Now we have $P \lor \neg P$. In the case that $P$ is true, we have $P$. And in the case that $\neg P$ holds, we have $\neg Q$, which contradicts $Q$. This proves that $(\neg P \implies \neg Q) \implies (Q \implies P)$.

(1) $\to$ (3): We first prove the statement $\neg \neg (P \lor \neg P)$. Suppose that $\neg (P \lor \neg P)$. Now suppose $P$. Then $P \lor \neg P$. But this contradicts $\neg (P \lor \neg P)$. Therefore, $\neg P$. Then $P \lor \neg P$. But this contradicts $\neg (P \lor \neg P)$. Therefore, $\neg \neg (P \lor \neg P)$.

We now apply proof by contradiction to conclude that $\neg \neg (P \lor \neg P) \implies P \lor \neg P$, and we therefore conclude that $P \lor \neg P$.

So the moral of the story here is that any proof which is done using any one of these three rules can always be rephrased to use another of the 3 rules. In particular, any proof using rule 1 can always be rephrased to use only rule 2.

There is another way to look at this which illustrates why it almost always seems more natural to you to use proof by contrapositive as opposed to proof by contradiction.

Consider the fact that whenever we're proving just about any fact whatsoever, we're proving this fact in the context of some assumptions that we've made.

For example, suppose I know that $x$ is a positive real number, and I wish to prove $\exists y \in \mathbb{R} (y \cdot x = 1)$. Then one can also view this as proving the implication $(x > 0) \implies \exists y \in \mathbb{R} (y \cdot x = 1)$.

In particular, let's suppose we've made an assumption $Q$, and then we have proved $\neg \neg P$ on our way to proving $P$ by contradiction.

Then we can also view this proof as a proof of $Q \implies \neg \neg P$. This is equivalent to proving $\neg (Q \land \neg P)$, which is in turn equivalent to proving that $\neg P \implies \neg Q$.

So our proof, in the context of $Q$, that $\neg \neg P$ holds can also be viewed as a proof of $\neg P \implies \neg Q$.

From there, we wish to conclude, in the context of the assumption $Q$, that $P$ holds. That is, we wish to conclude $Q \implies P$.

So in fact, what we're "really doing" is proving $\neg P \implies \neg Q$ and then concluding from this fact that $Q \implies P$.

So in this sense, all proofs by contradiction with any assumptions whatsoever are actually proofs by contrapositive. We collect all the assumptions into a single proposition $Q$, prove $\neg P \implies \neg Q$, and then conclude that $Q \implies P$.

This illustrates the fact that proof by contradiction is really just proof by contrapositive where no assumptions are made. Of course, making no assumptions is equivalent to only assuming $\top$. Put another way, proof by contradiction is just proof by contrapositive in the case where $Q = \top$. And this is indeed exactly how we proof that proof by contradiction is a valid technique using proof by contrapositive (exactly (2) $\to$ (1) above).

$\endgroup$
12
  • $\begingroup$ A proof by contrapositive could still involve a contradiction though right? As in to prove $P\to Q$ via $\lnot Q \to \lnot P$, you would need to show given $\lnot Q$ that $\lnot P$. And the easiest (sometimes only?) way to prove $\lnot P$, is to show $P\to\bot$. I.e. given $\lnot Q$, we have $P\to\bot$ or equivalently $\lnot Q\land P\to\bot$. And this (without going into what we mean exactly) most people would consider a proof by contradiction. $\endgroup$
    – eugenhu
    Oct 12 at 4:09
  • $\begingroup$ To expand, if $\lnot P$ is show a number is not even, we can equivalently show that the number is odd so we don't actually show $P\to\bot$ in our proof. Or $\lnot P$ is show a number is not rational, and we prove a stronger statement that the number has a finite difference from every rational number. Or if $\lnot P$ is something else and we prove it by using some other theorem. But on the other hand, maybe the easiest way is to just show $P\to\bot$. $\endgroup$
    – eugenhu
    Oct 12 at 4:26
  • $\begingroup$ @eugenhu You’re definitely right that proving $\neg P$ and proving $P \to \bot$ are essentially the same. In fact, in constructive logic, $\neg P$ is often viewed as shorthand for $P \to \bot$. But you’re conflating two things. Proof of negation is proving $\neg P$ by proving that $P \to \bot$, which is constructively ok. Proof by contradiction is proving $P$ by proving that $\neg P \to \bot$, and this is not constructively valid. You’re also right to note that we often prove a weak statement like “$x$ is not rational” by proving a constructively stronger but classically equivalent statement. $\endgroup$ Oct 12 at 4:45
  • $\begingroup$ Yep, but I suppose the hack is, if we do not consider proofs of $\lnot P$ via $P\to\bot$ as proofs by contradiction, then although the proof of $\lnot Q \to \lnot P$ has a proof of negation, in the context of serving as a proof to the original $P \to Q$, I would think this counts by most peoples standards as a proof by contradiction. $\endgroup$
    – eugenhu
    Oct 12 at 4:55
  • 1
    $\begingroup$ They both have the same proving power, so mathematically proof-by-contradiction/proof-by-contrapositive may not be well defined as separate things. But informally they're not the same because I think people would be uncomfortable if we were teaching kids proof-by-contradiction and proof-by-contrapositive are the same things, so there must be a distinction somewhere. $\endgroup$
    – eugenhu
    Oct 12 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.