Direct Proof, Proof by Contrapositive

Section 5.2 Direct Proof, Proof by Contrapositive

Subsection 5.2.1 Direct Proof

Definition 5.2.1.

A direct proof is a proof technique that involves using the assumptions of the statement, axioms, established facts and theorems, and combining them to logically deduce the desired conclusion.

Typically, direct proof is used for conditional statements $A \implies B\text{.}$ We assume $A\text{,}$ and make a sequence of conclusions from that, until we logically conclude $B\text{.}$ Often, using direct proof involves playing around with definitions and previous theorems, in an attempt to combine them in some way.

Subsection 5.2.2 Ending a Proof (Q.E.D)

Often, proofs are ended by the symbol $\square$ in the bottom right corner, like

Proof.

Alternatively, proofs can be ended with the acronym “Q.E.D” which stands for the latin phrase “quod erat demonstrandum” which means “that which was to be demonstrated”, which basically means “we have proved what we said we would prove”.

Subsection 5.2.3 Average of Two Numbers is Between Them

Fact 5.2.2.

Let $a, b \in \mathbb{R}, a \lt b\text{.}$ Then,

\begin{equation*} a \lt \frac{a + b}{2} \lt b \end{equation*}

In other words, the average of two numbers $a$ and $b$ is greater than the smaller number and less than the larger number.

Proof.

First,

\begin{align*} a + b \amp \lt b + b \amp\amp \text{as $a \lt b$}\\ a + b \amp \lt 2b\\ \frac{a + b}{2} \amp \lt b \amp\amp \text{dividing both sides by 2} \end{align*}

Similarly,

\begin{align*} a + b \amp > a + a \amp\amp \text{as }\\ a + b \amp > 2a\\ \frac{a + b}{2} \amp > a \end{align*}

as desired.

Alternate proof.

Alternatively, start with $a \lt b$ and add $a$ to both sides,

\begin{align*} a \amp \lt b\\ 2a \amp \lt a + b \end{align*}

and divide by 2. Similarly, adding $b$ to both sides,

\begin{align*} a \amp \lt b\\ a + b \amp \lt 2b \end{align*}

and dividing by 2 again.

Subsection 5.2.4 Sum of Rational Numbers is Rational

Fact 5.2.3.

If $x, y$ are rational numbers, then their sum $x + y$ is a rational number.

Proof.

Let $x, y$ be rational, so $x = \frac{a}{b}, y = \frac{c}{d}$ for some $a, b, c, d \in \mathbb{Z}, b, d \neq 0\text{.}$ Then,

\begin{equation*} x + y = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd} \end{equation*}

Then, $ad + bc, bd \in \mathbb{Z}\text{,}$ and $bd \neq 0$ (because $b, d \neq 0$). Thus, $x + y$ is rational.

Note that the previous two results imply that for any two rational numbers, there exists a rational number between them.

Subsection 5.2.5 Square of a Rational Number is Rational

Fact 5.2.4.

If $x$ is a rational number, then $x^2$ is rational.

Proof.

Let $x$ be rational, so $x = \frac{a}{b}$ for some $a, b \in \mathbb{Z}, b \neq 0\text{.}$ Then,

\begin{equation*} x^2 = \brac{\frac{a}{b}}^2 = \frac{a^2}{b^2} \end{equation*}

Then, since $a^2, b^2 \in \mathbb{Z}$ (because the squares of integers are integers) and $b^2 \neq 0$ (since $b \neq 0$), this implies that $x^2$ is rational.

Corollary 5.2.5.

If $x^2$ is irrational, then $x$ is irrational.

Proof.

This is the contrapositive of the previous statement.

Subsection 5.2.6 Product of Rational Numbers is Rational

Fact 5.2.6.

If $x, y$ are rational numbers, then their product $xy$ is rational.

This is only a slight generalization from the fact that the square of a rational number is rational. Here, we consider two different numbers, but the structure of the proof is similar.

Proof.

Let $x, y$ be rational, so $x = \frac{a}{b}, y = \frac{c}{d}$ for some $a, b, c, d \in \mathbb{Z}, b, d \neq 0\text{.}$ Then,

\begin{equation*} xy = \frac{a}{b} \cdot \frac{c}{d} = \frac{ac}{bd} \end{equation*}

Then, $ac, bd \in \mathbb{Z}\text{,}$ and $bd \neq 0$ (since $b, d \neq 0$). Thus, $xy$ is rational.

Subsection 5.2.7 Absolute Value of Product is Product of Absolute Values

Fact 5.2.7.

For all $x, y \in \mathbb{R}\text{,}$

\begin{equation*} \abs{xy} = \abs{x} \cdot \abs{y} \end{equation*}

Proof.

Exercise.

Subsection 5.2.8 More Examples

Fact 5.2.8.

If $a \lt b\text{,}$ then $4ab \lt (a + b)^2\text{.}$

First, expanding the right-hand side,

\begin{align*} 4ab \amp \lt a^2 + 2ab + b^2\\ 0 \amp \lt a^2 - 2ab + b^2\\ 0 \amp \lt (a - b)^2 \end{align*}

Then, since this is a true statement (since $a \neq b$), we can reverse the steps to form a proof.

Proof.

If $a \lt b\text{,}$ then $a - b \neq 0\text{,}$ and so $(a - b)^2 > 0\text{.}$ Then,

\begin{align*} (a - b)^2 \amp > 0\\ a^2 - 2ab + b^2 \amp > 0 \amp\amp \text{expanding the left hand side}\\ a^2 + 2ab + b^2 \amp > 4ab \amp\amp \text{adding $4ab$ to both sides}\\ (a + b)^2 \amp > 4ab \amp\amp \text{factoring the left hand side} \end{align*}

Fact 5.2.9.

Let $x \in \mathbb{R}\text{.}$ If $x^3 - x > 0\text{,}$ then $x > -1\text{.}$

This fact is an implication, where the hypothesis $x^3 - x > 0$ is complicated, but the conclusion $x > -1$ is simpler. Then, a good idea is to try proving the contrapositive.

Proof.

We will prove the contrapositive, that if $x \leq -1\text{,}$ then $x^3 - x \leq 0\text{.}$ Let $x \leq -1\text{.}$ Then $x \leq -1 \lt 0\text{.}$ Also,

\begin{align*} x \amp \leq -1\\ x^2 \amp \geq 1 \amp\amp \text{squaring both sides, both $x$ and $-1$ are negative so flip inequality}\\ x^2 - 1 \amp \geq 0\\ x^3 - x \amp \leq 0 \amp\amp \text{multiplying by $x \lt 0$} \end{align*}

as desired.

Fact 5.2.10.

If $p$ is prime and $p \geq 5\text{,}$ then $p^2 - 1$ is divisible by 24.

Proof.

First, $p^2 - 1 = (p - 1)(p + 1)\text{.}$ Since $p \geq 5$ is prime, $p$ is odd, so $p-1$ and $p+1$ are both even. This implies that $4 \mid (p^2 - 1)\text{.}$ Also, $p-1$ and $p+1$ are two consecutive even integers, so exactly one of them is divisible by 4. Thus, $8 \mid (p^2 - 1)\text{.}$ Also, in general, exactly one of $p-1, p, p+1$ is divisible by 3. Since $p$ is prime, $3 \nmid p\text{.}$ Thus, either $p-1$ or $p+1$ is divisible by 3. Together, $24 \mid (p^2 - 1)\text{.}$

Subsection 5.2.9 Proving “Or” Statements

Consider an “or” statement, that $P \rightarrow (A \lor B)\text{,}$ i.e. that given the hypotheses $P\text{,}$ either one of $A$ or $B$ is true (or both).

To prove a statement of this form, we can split up the proof into two cases: (1) if $A$ is true, or (2) $A$ is false. These two cases cover all possible scenarios, so if the statement is true in both of these cases, it will be true in all cases.

In the first case, the proof is done, because $A$ being true implies that $A \lor B$ is true. Here, there is nothing to prove.
In the second case, the goal is to prove that because $A$ is false, this implies that $B$ will be true.

Of course, we could have instead considered (1) $B$ is true and (2) $B$ is false, because $A$ and $B$ are symmetric.

Here, the first case is trivially true, so the argument is phrased in a different but equivalent way. To prove $A \lor B$ we assume that $A$ is false, and prove that $B$ is true (or, assume $B$ is false, and prove $A$ is true). That is, we prove the statement $\not A \rightarrow B\text{.}$ So, in summary, $A \lor B$ is logically equivalent to $\neg A \rightarrow B\text{,}$ or,

\begin{equation*} \boxed{A \lor B \equiv \neg A \rightarrow B} \end{equation*}

Also, “or” statements can also be proven by contradiction, by assuming that $\neg A \land \neg B$ (because $\neg (A \lor B) = \neg A \land \neg B$ by DeMorgan's laws).

Subsection 5.2.10 Disproving a Statement

To disprove a statement is to prove its negation. To disprove $\forall x \in D\text{,}$ if $P(x)\text{,}$ then $Q(x)\text{,}$ we have to prove the negation, that is, there exists $x \in D$ such that $P(x)$ and $Q(x)\text{.}$

Subsection 5.2.11 Proof by Contrapositive

Proof by contrapositive involves proving a conditional $P \rightarrow Q$ by instead proving its contrapositive $\neg Q \rightarrow \neg P\text{.}$ This is valid because the contrapositive of a conditional is logically equivalent to the original conditional.

This is often helpful if the hypothesis $P$ is a more complicated statement than the conclusion $Q\text{.}$

Subsection 5.2.12 False Algebra Proof

Fact 5.2.11.

$2 = 1\text{.}$

Proof.

Let $x = y\text{.}$ Then, multiplying both sides by $y\text{,}$ $x^2 = xy\text{.}$ Then, subtracting $y^2$ from both sides, $x^2 - y^2 = xy - y^2\text{.}$ Then, factoring the left-hand side as a difference of squares, and factoring the common factor of $y$ from the right-hand side,

\begin{equation*} (x - y)(x + y) = y(x - y) \end{equation*}

Then, cancelling the common factor of $x - y$ on both sides, we get $x + y = y\text{.}$ Then, recall that $x = y\text{,}$ so this implies that $y + y = y\text{,}$ or $2y = y\text{.}$ Finally, cancelling $y$ from both sides, we get $2 = 1\text{.}$

The issue with this proof is that you can only cancel a factor on both sides (i.e. divide by that factor) if it is non-zero. For example, $2 \cdot 0 = 3 \cdot 0$ is true (both sides are 0), but it does not imply that $2 = 3$ (cancelling the factors of 0). Here, we cancelled $x - y$ on both sides. However, we assumed that $x = y\text{,}$ and so $x - y = 0\text{.}$