2.5 Contradiction and the contrapositive
As mentioned earlier, negating statements are useful when trying to prove statements using different methods. First we look at proof by contradiction.
□
While we will use this method more extensively later, let us see an easy example.
Statement: Let \(x,y \in \mathbb{Q}\). If \(x<y\) then \(-x>-y\).
Proof: For the sake of a contradiction let us assume that \(x<y\) and \(-x\leq-y\). (Recall the negation of \(P \implies Q\) is \(P \vee \neg Q\).) Since \(x<y\) we have \(x-x<y-x\) [by (O3)], i.e. \(0<y-x\). Since \(-x\leq -y\) then \(-x+y\leq -y+y\), i.e. \(y-x\leq 0\). So \(0<y-x\) and \(y-x\leq 0\), i.e. [by (O1)] \(0<0\), which is a contradiction. Hence \(x<y\) and \(-x\leq-y\) is false, so If \(x<y\) then \(-x>-y\). \(\square\)Another technique is a proof by contrapositive.
The contrapositive of (A1), “for all \(x,y\), if \(x,y \in \mathbb{Z}\) then \(x+y \in \mathbb{Z}\)” is “for all \(x,y\), if \(x+y \notin \mathbb{Z}\) then \(x\notin\mathbb{Z}\) or \(y\notin\mathbb{Z}\).”
The contrapositive of (O3), “for all \(x,y,z \in \mathbb{Q}\), if \(x<y\) then \(x+z<y+z\)” is “$for all \(x,y,z\in\mathbb{Q}\) if \(x+z\geq y+z\) then \(x\geq y\)”.By Theorem 2.8, we know that \(P \implies Q\) is equivalent to its contrapositive. Sometimes, proving the contrapositive is easier than proving \(P \implies Q\) (we will see more examples of this later).
Statement: Let \(x,y \in \mathbb{Q}\). If \(x<y\) then \(-x>-y\).
Proof: We prove the contrapositive. The contrapositive is “if \(-x\leq -y\) then \(x\geq y\)”. Suppose \(-x\leq -y\) then \(-x+(x+y) \leq -y+(x+y)\) [since \(x+y \in \mathbb{Q}\) by (A1) and using (O3)*]. In other words \(y\leq x\), i.e. \(x\geq y\). \(\square\)Note that we have proven “\(x<y \implies -x>-y\)” by contradiction and by contrapositive. It is also worth noting that we could have proven it directly. This is meant to show that often there are numerous way to prove the same thing.
Note that the contrapositive doesn’t just change the implication symbol, but it also negates \(P\) and \(Q\). The contrapositive can often be confused with the converse:
Note that \(P \implies Q\) is not equivalent to its converse. Be careful when using a theorem/lemma/proposition that you are not using the converse by accident (which may not be true).
If the converse of \(P\implies Q\) is true, then we can deduce that \(P \iff Q\).
The converse of “If \(x<y\) then \(-x>-y\)” is “\(-x>-y\) then \(x<y\)”. We can show this is true, suppose \(-x>-y\) then \(-x+(x+y)>-y+(x+y)\), i.e. \(y>x\), i.e. \(x<y\).
Therefore we conclude, for all \(x,y \in \mathbb{Q}\), \(x<y\) if and only if \(-x>-y\).
Contradiction comes from the Latin contra which means “against” and dict which is a conjugation of the verb “to say, tell”. A contradiction is a statement that speaks against another statement.
Contrapositive also comes from the Latin contra and the Latin positus which is a conjugation of the verb “to put”. The contrapositive of a statement is a statement “put against” the original statement, we have negated both parts and reversed the order. Furthermore it is “positive” as it has the same truth value as the original statement.
On the other hand, while sounding similar, converse comes from the Latin con which means “together with” and vergere which means “to turn”. The converse turns the order of \(P\) and \(Q\).