$4\mathrm{.}7$ Indirect Argument: Contradiction and Contraposition

Definition $1.$ The indirect method called proof by contraposition or contrapositive proof of $PQ$ makes use of the tautology $PQQP.$ We give a direct proof of $QP$ and conclude by replacement that $PQ.$

PROOF OF $PQ$ BY CONTRAPOSITION

Proof. State hypotheses if there is any. $($Let xinD.$)$

Assume $Q.$

:

Therefore, $P.$

Thus, $QP.$

Therefore, $PQ.$

Note: This method can work well when the connection between denials of $P$ and $Q$ are easier to understand than the connection between $P$ and $Q$ themselves, or when the statement of either $P$ and $Q$ is itself a negation.

Definition $2.$ An indirect method of a statement $R$ by the method of contradiction uses the logic that if $R$ can't be false, then $R$ must be true, that is using the tautology $Rc-=R,$ where $c$ means a contradiction.

PROOF OF $R$ BY CONTRADICTION

Proof.

Assume $R.$

:

Therefore, $S.$

:

Therefore, $S.$

Hence, $S^{{?}^{?}}S$ a contradiction.

Thus, $R.$

Note $1$: This method of proof can be applied to any proposition $R,$ whereas direct proofs and proofs by contraposition can be used only for conditional sentences.

Note $2$: The strategy of proving $R$ by proving $R(S^{{?}^{?}}S)$ has the disadvantage that when we set out to prove $R,$ we may have no idea that what proposition to use as $S.$ This means a proof by contradiction may require a spark of insight to determine a useful $S.$ The advantage of this method is that there may be many propositions $S$ such that $R$ implies both $S$ and $S,$ and any such proposition may be used to construct the proof.

$4\mathrm{.}8$ Indirect Argument: Two Classical Theorems

Euclid's Lemma. Let $a,b,$ and $p$ be integers. If $p$ is a prime and $p$ divides $ab,$ then $p$ divides $a$ or $p$ divides $b.$

HW for $4\mathrm{.}7$ :

Carefully formulate the negation of the following statement. Then prove the statement by contradiction:

There is no greatest negative real number.

Prove that for all integers $a,b$ and $c,$ if $a|b|$ and $ac$ then $a(b+c).$

Prove each of the statements in two ways: $($a$)$ by contraposition and $($b$)$ by contradiction.

$3.$ For every integer $n,$ if $n^2$ is odd then $n$ is odd.

$4.$ For all integers $a,b$ and $c,$ if $a,bc$ then $ab.$

HW for $4\mathrm{.}8$ :

Determine which statements are true and which are false. Prove those that are true and disprove those that are false.

$8-5\sqrt[\phantom{2}]{2}$ is irrational.

The difference of any two irrational numbers is irrational.

If $r$ is any rational number and $s$ is any irrational number, then $\frac{r}{s}$ is irrational.