More proofs

Chapter 5 More proofs

Now that we’ve done a little more logic we should get back to proving things. Consider the following examples which (superficially) look quite similar to those we did back in Chapter 3:

🔗

Example 5.0.1.

Let \(n\) be an integer. If \(3n+7\) is even then \(n\) is odd.

🔗

Scratchwork.

As always — assume the hypothesis is true.
\begin{align*} 3n+7 &= 2k \end{align*}

🔗
Then we try to use this to say something about the conclusion.
\begin{align*} n &= \frac{2k-7}{3} \end{align*}

🔗
And now we are stuck, because it isn’t clear that \(n\) is an integer and we need to show that
\begin{align*} \frac{2k-7}{3} &= 2\ell +1 \end{align*}
for some integer \(\ell\text{.}\) This doesn’t look so obvious. Though it is surprising how many students will try to claim that one can deduce the parity from here.

🔗

Urgh.

🔗

Example 5.0.2.

If \(n \in \mathbb{Z}\) then \(n^2+5n-7\) is odd.

🔗

Scratchwork.

Again, we start as we did previously; assume the hypothesis is true and work towards the conclusion.

Assume the hypothesis is true — so \(n\) is an integer.

🔗
Then \(n^2+5n-7 = 2\ell+1\) means that we need
\begin{align*} n^2+5n-6 &= 2\ell & \text{and so}\\ n^2+5n &= 2(\ell+3) \end{align*}

🔗
So…? Help — I’m stuck.

🔗

This would be a lot easier if we knew more about the parity of \(n\text{.}\)

🔗

In both cases we can make our lives much easier by manipulating the original statement into another form by use of logical equivalences. More precisely

\begin{align*} (P \implies Q) & \equiv (\neg Q \implies \neg P)\\ (P \lor R) \implies Q &\equiv (P \implies Q) \land (R \implies Q) \end{align*}

In both cases, proving the statement on the left-hand side of the equivalence is completely logically equivalent to proving the statement on the right-hand side of the equivalence. So if the statement on the right-hand-side is easier, then we should just do that instead. Lets apply these equivalences to the above examples:

🔗

Example 5.0.1 starts with the statement

🔗

Let \(n\) be an integer. If \(3n+7\) is even then \(n\) is odd.
🔗

🔗

The contrapositive of this is then

🔗

Let \(n\) be an integer. If \(n\) is not odd then \(3n+7\) is not even.
🔗

🔗

However since we know that \(n\) is an integer, we can clean this up still more

🔗

Let \(n\) be an integer. If \(n\) is even then \(3n+7\) is odd.
🔗

🔗

And now we are at a statement that looks exactly like results we proved in Chapter 3. This process of proving the contrapositive of the original statement is called contrapositive proof (not such an inventive term, but quite descriptive).

🔗

Manipulating Example 5.0.2 requires a little more thought. One of the impediments that we had was that we didn’t know about the parity of \(n\text{.}\) However since \(n\) is an integer, we know it must be even or odd. Indeed,

🔗

(\(n\) is an integer) \(\equiv\) ( (\(n\) is even) or (\(n\) is odd))
🔗

🔗

Hence we can rewrite Example 5.0.2 as

🔗

If \(n\) is even or \(n\) is odd, then \(n^2+3n-9\) is odd.
🔗

🔗

We can then use the one of the above logical equivalences to rewrite this as

🔗

(If \(n\) is even then \(n^2+3n-9\) is odd) and (If \(n\) is odd then \(n^2+3n-9\) is odd)
🔗

🔗

Again, we have arrived at statements that look just like those we proved in Chapter 3. This is an example of a proof by cases.

🔗

Prev Top Next