I want a "true" proof by contradiction of an implication $P \Rightarrow Q$

Question

When teaching proofs by contradiction of an implication $P \Rightarrow 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 \Rightarrow Q"$ in which one would really need BOTH the assumption (not $Q$) and the assumption ($P$) to actually reach some kind of contradiction?

Answer 1

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.

Answer 2

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$.

Answer 3

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$.

Answer 4

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.

Answer 5

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).

Answer 6

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?

Theorem: If $x\in(0,\infty)$, then $x+\frac{4}{x}\geq 4$.

Proof by contradiction: Suppose that $x+\frac{4}{x}<4$. Since $x>0$ (by hypothesis), it follows that $(x+\frac{4}{x})\cdot x<4\cdot x$. This implies that $(x-2)^2<0$, which is a contradiction.

In this example:

• $P$ is the assertion $x\in(0,\infty)$, that is, $x>0$.
• $Q$ is the assertion $x+\frac{4}{x}\geq 4$.
• $\neg Q$ is the assertion $x+\frac{4}{x}< 4$.
• The contradiction is $(x-2)^2<0$.

Note that the assumptions $P$ and $\neg Q$ were used together in order to reach the contradiction. And the contradiction is different from the negation of $P$. Therefore, it is a "true" proof by contradiction.

However (and this is a fact that should be clear to the people you are educating), we use contradiction because, in general, it is easier (requires less knowledge) and simpler (requires less creativity) than the contrapositive and not, necessarily, because the use of the contrapositive is impossible. For example, the same theorem above can be proved by contrapositive. Write this proof. Possibly, we can argue that the proof by contrapositive is more elegant. But which one is more "naturtal" (especially for students)?