How to Understand proof by contradiction.

Question

What is the meaning of this following passage?

"An indirect proof always begins by negating what it is we would like to prove. The argument then proceeds until (hopefully) a logical contradiction with some other accepted fact is uncovered. Many times this accepted fact is part of the hypothesis of the theorem. When the contradiction is with the theorems hypothesis, we technically have what is called a contrapositive proof."

I know how to negate statements and have tried proof by contradiction. I'm not sure what the writer means by "uncovering some other fact" and "when the contradiction is with the theorems hypothesis, we have a contrapositive proof" can someone please make this clear for me.

I know that theorems are of the form A implies B, and contrapositive is of the form not(B) implies not(A).

Answer 1

Let's elucidate each of these confusing phrases with its own example.

First I'll discuss a proof by contradiction that $\sqrt{2}$ is irrational. The argument will uncover a contradiction with another accepted fact. If $\sqrt{2}=a/b$ with $a,\,b$ non-zero integers then $a^2=2b^2$ is even, so $a$ is even, say $a=2c$. Then $b^2=2c^2$ is also even, as is $b$. In particular, we can cancel a factor of $2$ from the numerator and denominator of any fraction equal to $\sqrt{2}$, so there's no lowest terms for such a fraction. This uncovers a contradiction with another accepted fact, namely that every fraction can be cancelled into lowest terms.

Next I'll discuss a proof by contradiction that if some finite number $n$ of people attend a party, some two shake hands with the same number of people. The number of people with whom a given attendee can shake hands ranges from $0$ to $n-1$ inclusive, which is only $n$ options. Since the number of options equals the number of people, we can restate our hypothesis as some number of handshakes from $0$ to $n-1$ inclusive isn't achieved. Well, let's get a contradiction from that. In this argument the contradiction is with the theorem's hypothesis. Suppose instead they all are. Since someone shakes hands with no-one ($0$ shakes), say Alice, no-one shakes hands with everyone, because Alice is always missed. But that means $n-1$ is unachieved, so we don't achieve all totals after all! Note here the potential truth of the claim we wished to refute has implied its own falsity; or equivalently, the hypothesis being false implied it is true.

Answer 2

A proof by contradiction of a statement $B$ is when we start with the assumption of $\lnot B,$ derive something false from that assumption, and then conclude that the assumption must have been wrong (i.e. $B$ is true).

But often times are theorems are if/then statements, in other words of the form $A\to B.$ A proof of $A\to B$ by contrapositive is a proof of $\lnot B\to \lnot A,$ which we typically prove by assuming $\lnot B$ and deriving $\lnot A.$ This is valid since the contrapositive $\lnot B\to \lnot A$ is logically equivalent to $A\to B.$

People often confuse these two and say a proof is 'by contradiction' even if it actually takes the second form. There is a good reason for this. When we're proving $A\to B,$ the way we generally think about it is that we assume $A$ and then prove $B$ under that assumption. One route we might take is to prove $B$ by contradiction by assuming $\lnot B$ and then proving $\lnot A,$ which is a false statement under our assumption of $A.$

Whereas in a proof by contradiction we derive any false statement whatsoever, in the pattern above, we derive a very specific statement $\lnot A$ which is only false under the assumption of $A$ that we made. This is what the author meant by "where the contradiction is with the theorem's hypothesis."

Notice the part where all the work was done was in assuming $\lnot B$ and then deriving $\lnot A,$ i.e. directly proving the contrapositive $\lnot B\to \lnot A$. However, we mentally framed it as a proof by contradiction of $B$, under the assumption $A$, which amounts to a proof of $A\to B$. Note this is not at all the same thing as a true proof by contradiction of the statement $A\to B,$ which would consist of assuming $\lnot(A\to B)$ and deriving a false statement.