15

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?

Pedro
  • 1,422
  • 8
  • 14
Juan Tolosa
  • 167
  • 1
  • 4

6 Answers6

32

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.

Tanner Swett
  • 631
  • 4
  • 7
  • 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?) – justhalf Oct 09 '21 at 11:13
  • 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. – user2357112 Oct 09 '21 at 12:43
  • @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? – justhalf Oct 09 '21 at 14:22
  • 1
    @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. – user2357112 Oct 09 '21 at 14:36
  • 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! – justhalf Oct 10 '21 at 07:41
10

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

Chris Cunningham
  • 21,474
  • 6
  • 63
  • 148
  • 3
    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. – KCd Oct 09 '21 at 20:11
  • 3
    @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. – Chris Cunningham Oct 09 '21 at 21:55
  • what about square root of 2 is irrational? – BCLC Oct 09 '21 at 23:18
  • @BCLC Are you asking whether it is possible to prove the implication ($x$ is rational) implies ($x^2 \neq 2$)? – Chris Cunningham Oct 09 '21 at 23:39
9

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

user52817
  • 10,688
  • 17
  • 46
  • 6
    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. – Juan Tolosa Oct 09 '21 at 20:36
  • what about square root of 2 is irrational? – BCLC Oct 09 '21 at 23:17
  • @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 – user52817 Oct 10 '21 at 01:19
  • 1
    @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! – user52817 Oct 10 '21 at 05:14
  • 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) ? – BCLC Oct 10 '21 at 18:19
2

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

Mark Saving
  • 121
  • 2
  • 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. – eugenhu Oct 12 '21 at 04:09
  • 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$. – eugenhu Oct 12 '21 at 04:26
  • @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. – Mark Saving Oct 12 '21 at 04:45
  • 1
    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. – eugenhu Oct 12 '21 at 04:55
  • (We proved the contrapositive/formally-equivalent-to-contradiction and somewhere in the proof something leads to $\bot$/loosely-hey-that's-a-contradiction.) – eugenhu Oct 12 '21 at 05:02
  • @eugenhu It’s not a “hack” to distinguish between proof of negation and proof by contradiction. It’s a fundamental part of understanding constructive logic. As far as your examples with proving a number not even/not rational go, the trick is that we must first prove the theorem $\forall n (isOdd(n) \to \neg isEven(n))$ before we can use the fact that odd numbers aren’t even. In this prequel proof, we will invariably need to use proof of negation. So we actually do the proof of negation in a previous step which is then taken for granted as common knowledge in our later proof. – Mark Saving Oct 12 '21 at 05:16
  • I'm probably not being very clear. I understand the difference between proof of negation/by contradiction, and I think it is a useful distinction and this is not a hack. The "hack" I am referring to is that it seems very difficult (I have checked many places) to give a "real" proof by contradiction. All I mean to point out is that many people have said proof-by-contradiction is logically equivalent to proofs of the contrapositive statement, but the flipside which I'm commenting is that some proofs of the contrapositive laypeople would consider proofs by contradiction. – eugenhu Oct 12 '21 at 05:23
  • 1
    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. – eugenhu Oct 12 '21 at 05:26
  • Anyway, I didn't mean to ramble on, but part of the difficulty in finding a simple "true" proof by contradiction as OP puts it, is I think many proofs in highschool are e.g. show this is even, or show this is larger. Where to prove the negation you can equivalently (based on known results: odd implies not even) show it's odd, or show it's smaller, so you can avoid a $\bot$ appearing in the proof (sweep it under the carpet). So all of these proofs the OP would discard as "fake" proofs by contradiction. – eugenhu Oct 12 '21 at 05:36
  • @eugenhu See my edited answer for some more insight. I think I may have figured out what's going on here. – Mark Saving Oct 12 '21 at 20:37
  • Yeah the way I see it is a proof of $Q\to P$ by contradiction is: prove $\lnot(Q\to P)\to\bot=\lnot P\land Q\to\bot$. And proof by contrapositive is: prove $\lnot P \to \lnot Q$; i.e. assume $\lnot P$ and show $\lnot Q$ (which you may do by explicitly showing $Q\to\bot$); i.e. show $\lnot P\land Q\to\bot$; i.e. proving the contrapositive statement by assuming $\lnot P$ then proving the negative $\lnot Q$ via $Q\to\bot$, is the same as proof by contradiction. Which I think is what you are saying here that proof by contrapositive and proof by contradiction are only superficially different. – eugenhu Oct 13 '21 at 03:20
  • I guess a "real" proof by contradiction is one that spends a lot of time proving something $\to \bot$ (à la $\lnot P\land Q\to R_1\to R_2\to\cdots\to\bot$), inelegant since intermediate results equivalent to $\bot\to R_i$. Whereas maybe a proof by contrapositive is only proving $Q\to\bot$ out of necessity ($\lnot P\to R_1\to\cdots\to R_n$, then $R_n\land Q\to\bot$). – eugenhu Oct 13 '21 at 03:34
2

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.

eugenhu
  • 121
  • 5
0

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

Pedro
  • 1,422
  • 8
  • 14