4.6 Proving equivalences

We have already seen and proven some conditional statements, i.e. ones of the form $P\Rightarrow Q$ . Recall, from Section 3.2.5, that saying two statements $P$ and $Q$ are equivalent means that $P\Rightarrow Q$ and $Q\Rightarrow P$ . Hence proving $P\Leftrightarrow Q$ means proving $P\Rightarrow Q$ and $Q\Rightarrow P$ .

4.6.1 Proving $P\Leftrightarrow Q$ by proving $P\Rightarrow Q$ and $Q\Rightarrow P$ separately

As we saw with the proofs of the Pythagorean theorem and its converse (Section 4.2.1), it may be simplest to prove $P\Rightarrow Q$ and $Q\Rightarrow P$ separately and then conclude that $P\Leftrightarrow Q$ .

Example 4.26.

Suppose that $n=10a+b$ for positive integers $a$ and $b$ . We shall prove that $(a+b)$ is a multiple of $9$ if and only if $n$ is a multiple of $9$ .

[Take a few minutes to make sure you understand what this statement is claiming.]

Note that a positive integer being a multiple of $9$ means that it can be written in the form $9$ times an integer. So the above statement is claiming that

n=9k\quad\Leftrightarrow\quad(a+b)=9l

for some integers $l$ and $k$ .

First we will prove the statement $n=9k\Rightarrow(a+b)=9l$ . Suppose $n=9k$ . Then

	$\displaystyle n$	$\displaystyle=10a+b$	(definition of $n$ )
$\displaystyle\Leftrightarrow\quad$	$\displaystyle 9k$	$\displaystyle=10a+b$	(replacing $n$ )
$\displaystyle\Leftrightarrow\quad$	$\displaystyle 9k$	$\displaystyle=9a+(a+b)$	(rewriting the right-hand side)
$\displaystyle\Leftrightarrow\quad$	$\displaystyle a+b$	$\displaystyle=9k-9a$	(rearranging)
$\displaystyle\Leftrightarrow\quad$	$\displaystyle a+b$	$\displaystyle=9(k-a)$	(factorising).

Since $k-a$ is an integer, we can conclude that $a+b$ is a multiple of $9$ .

Now we prove that $(a+b)=9l\Rightarrow n=9k$ . Suppose $(a+b)=9l$ . Then

	$\displaystyle n$	$\displaystyle=10a+b$	(definition of $n$ )
$\displaystyle\Leftrightarrow\quad$	$\displaystyle n$	$\displaystyle=9a+(a+b)$	(rewriting the right-hand side)
$\displaystyle\Leftrightarrow\quad$	$\displaystyle n$	$\displaystyle=9a+9l$	(replacing $a+b$ )
$\displaystyle\Leftrightarrow\quad$	$\displaystyle n$	$\displaystyle=9(a+l)$	(factorising).

Since $a+l$ is an integer, we can conclude that $n$ is a multiple of 9.

We have proved $n=9k\Rightarrow(a+b)=9l$ and $(a+b)=9l\Rightarrow n=9k$ and so we have proved $n=9k\Leftrightarrow(a+b)=9l$ .

Exercise 4.27.

Prove that a positive integer $n$ is a multiple of $6$ if and only if $n$ is a multiple of $2$ and of $3$ .

Solution.First we will prove that if $n$ is a multiple of $6$ then $n$ is a multiple of $2$ and of $3$ .

Suppose $n$ is a multiple of $6$ , i.e. $n=6k$ for some integer $k$ . Then

		$\displaystyle n$	$\displaystyle=2\times(3k),$		hence $n$ is a multiple of 2,
	and	$\displaystyle n$	$\displaystyle=3\times(2k),$		hence $n$ is a multiple of 3.

Now we prove that if $n$ is a multiple of $2$ and of $3$ then $n$ is a multiple of $6$ . Suppose:

–

$n$ is a multiple of 2, i.e. let $n=2l$ for some integer $l$ , and
–

$n$ is a multiple of 3, i.e. let $n=3m$ for some integer $m$ .

Then

$\displaystyle n$	$\displaystyle=3n-2n$	(see the note below)
	$\displaystyle=3(2l)-2(3m)$	(replacing $n$ )
	$\displaystyle=6l-6m$	(simplifying)
	$\displaystyle=6(l-m)$	(factorising).

Because $l-m$ is an integer, it follows that $n$ is a multiple of 6. The proof is complete.

A key step in the solution presented above is realising that you can write $n$ as $3n-2n$ . The identity $n=3n-2n$ is obvious, but it is not obvious that this fact is going to be useful in a proof. Most mathematics students struggle with this phenomenon – you may read a proof, follow the logical argument, but be left feeling ‘I would not have thought of that’. The point you should take away from this exercise is that figuring out how to construct a proof (e.g. realising that writing $n=3n-2n$ might help) is part of what doing mathematics is all about. You will get better at finding arguments the more you practice and build your repertoire of ideas.

4.6.2 Proving $P\Leftrightarrow Q$ directly

In some cases, it might be possible to prove a statement $P\Leftrightarrow Q$ directly, rather than proving $P\Rightarrow Q$ and $Q\Rightarrow P$ separately.

Example 4.28.

Suppose that $a$ and $b$ are real numbers. We shall prove that $a<b\Leftrightarrow\frac{a+b}{2}<b$ .

[As usual, take a few minutes to understand this claim.]

Here is a proof.

$\displaystyle a<b\quad$	$\displaystyle\Leftrightarrow\quad a+b<b+b$	(adding $b$ to both sides)
	$\displaystyle\Leftrightarrow\quad a+b<2b$
	$\displaystyle\Leftrightarrow\quad\frac{a+b}{2}<b$	(dividing both sides by $2$ ).

All statements made in this argument are equivalent; the proof is complete.

Note that we could have presented proofs of $a<b\Rightarrow\frac{a+b}{2}<b$ and $\frac{a+b}{2}<b\Rightarrow a<b$ separately (as we did in the previous section) but in this case it is possible and neater to do both at once.

4.6.3 Proving that more than two statements are equivalent

In Sections 4.6.1 and 4.6.2 we discussed how to prove statements of the form $P\Leftrightarrow Q$ . We now discuss what it means to prove that more than two statements are equivalent.

We do this by discussing an example and leave the details of the proof as an exercise.

Example 4.29.

Suppose that $n$ is an integer and consider the following statements.

$A$ :

$n$ is even.
$B$ :

$n/2$ is an integer.
$C$ :

$n+1$ is odd.
$D$ :

$n+2$ is even.

These statements are all equivalent; if one is true then the others are true, and if one is false then the others are false. Take a few minutes to convince yourself of this.

One way to prove that $A$ , $B$ , $C$ and $D$ are equivalent would be to do so pairwise, i.e. to prove $A\Leftrightarrow B$ , $A\Leftrightarrow C$ , $A\Leftrightarrow D$ , $B\Leftrightarrow C$ , $B\Leftrightarrow D$ , $C\Leftrightarrow D$ . But this is quite inefficient and is not necessary if we think things through logically.

Suppose instead we can prove $A\Rightarrow B$ , $B\Rightarrow C$ , $C\Rightarrow D$ and $D\Rightarrow A$ . We can then deduce that all four statements are equivalent. To see this, observe that we would have established this loop of implications.

Now, for example, we can deduce that $A\Leftrightarrow C$ : we know that $A\Rightarrow B$ and $B\Rightarrow C$ and so $A\Rightarrow C$ ; and we know that $C\Rightarrow D$ and $D\Rightarrow A$ and so $C\Rightarrow A$ .

Observe, too, that it is not necessary to take the statements in the order they are given above. For example, it might be easier to prove $B\Rightarrow A\Rightarrow C\Rightarrow D\Rightarrow B$ . As long as there is a loop of implications involving all statements, you can deduce that the statements are equivalent.

Exercise 4.30.

Let $n$ be an integer. Prove that the following are equivalent.

$A$ :

$n$ is even.
$B$ :

$n/2$ is an integer.
$C$ :

$n+1$ is odd.
$D$ :

$n+2$ is even.

Solution.As suggested above, we will prove $B\Rightarrow A\Rightarrow C\Rightarrow D\Rightarrow B$ .

$B\Rightarrow A$ : Assuming $n/2$ is an integer $k$ , then

$n/2=k\quad\Leftrightarrow\quad n=2k.$

This is the form of an even number so we can conclude $n$ is even.

$A\Rightarrow C$ : By Definition 2.6, if $n$ is even, we can write $n=2l$ for some integer $l$ . Then $n+1=2l+1$ is odd.

$C\Rightarrow D$ : If $n+1$ is odd, we can write $n+1=2p+1$ for some integer $p$ and

$\displaystyle n+2$ $\displaystyle=(n+1)+1$

$\displaystyle=(2p+1)+1$

$\displaystyle=2p+2$

$\displaystyle=2\times(p+1).$

This is the form of an even number so we conclude $n+2$ is even.

$D\Rightarrow B$ : Assuming $n+2$ is even, then there is an integer $q$ such that $n+2=2q$ . Rearranging, we have $n=2q-2=2\times(q-1)$ which shows $n$ is even as required.

	$\displaystyle n+2$	$\displaystyle=(n+1)+1$
		$\displaystyle=(2p+1)+1$
		$\displaystyle=2p+2$
		$\displaystyle=2\times(p+1).$