Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Section 3.2 Direct proofs

A lot of the examples we will see shortly will involve even and odd numbers. Let us define these formally so we have a clear and solid base for our proofs.

Definition 3.2.1.

An integer \(n\) is even if \(n=2k\) for some \(k \in \mathbb{Z}\text{.}\)
So since \(14=2\times 7\) and \(7 \in \mathbb{Z}\text{,}\) we know that \(14\) is even. Similarly \(-22 = 2 \times (-11)\) and \((-11) \in \mathbb{Z}\text{,}\) so \(-22\) is even.
When we first encounter “even” we learn that a number that is not even is “odd”. At that time we have not yet encountered fractions or reals, so implicitly we thought all numbers were integers. But we know about rationals and reals (and maybe even complex numbers), so we should define odd numbers a little more carefully.

Definition 3.2.2.

An integer \(n\) is odd if \(n=2\ell+1\) for some \(\ell \in \mathbb{Z}\text{.}\)
Since \(13=2\times6+1\) and \(6\in\mathbb{Z}\) we know that 13 is odd. Similarly, \(-21\) is odd because \(-21 = 2\times(-11)+1\) and \(-11 \in \mathbb{Z}\text{.}\)
We should make a few observations about definitions before we move on to prove something.
The word “If”
Notice that in both definitions we use the word “if” when we really mean “if and only if”. If a number \(n\) is even then it can be written as \(n=2k\) for some integer \(k\text{.}\) AND if we can write \(n=2\ell\) for some integer \(\ell\text{,}\) then we say that \(n\) is even. This becomes quite cumbersome, so it is convention that we write “if” in this context in definitions instead of writing “if and only if”. We can safely assume that our reader knows this convention.
Find it easily
Also we should make sure our definition is clear on the page. We declare it with “Definition:”! It is poor writing to hide important definitions inside the middle of an otherwise undistinguished paragraph (though this does happen from time to time). Some writers will put the key word being defined in inverted commas, or italics, or bold or underline, to further highlight it. If the definition is of an important object or property, then the reader should be able to find it and read it very easily.
Number it
We have numbered 34  the definition so that we can refer to it easily (if necessary).
“For some” is coming
We have also used the phrase “for some” in both definitions. We haven’t yet covered quantifiers in any sort of detail, but we will do so in Chapter 6 after a little more logic and some more proofs.

Definition 3.2.3.

We say that two integers have the same parity if they are both even or they are both odd. Otherwise we say that the numbers have opposite parities.
For a little more practice with definitions, lets extend the idea of “evenness” (being divisible by two):

Definition 3.2.4.

Let \(n\) and \(k\) be integers. We say that \(k\) divides \(n\) if we can find an integer \(\ell\) so that \(n=\ell k\text{.}\) In this case we write \(k \mid n\) and say that \(k\) is a divisor of \(n\) and that \(n\) is a multiple of \(k\text{.}\)
There is nothing in this definition that you haven’t seen before (we hope), but it is worth looking at its structure since it is very typical.
  • We start by defining the objects and symbols in our definition (this will necessarily build on previous definitions).
  • We then define our main property divides.
  • We follow up with some additional properties related to the main one.
  • We have also used “if” in the definition in the way that we highlighted previously — we really mean “if and only if”.
Finally, lets do one more definition related to divisibility — primes.

Definition 3.2.5.

Let \(n\) be a natural number strictly greater than one. We say that \(n\) is prime if it cannot be written as the product of two smaller natural numbers. Equivalently \(n\) is prime when the only natural numbers that divide it are are 1 and itself.
If a natural number strictly greater than 1 is not prime then we say that it is composite. Finally, the number 1 is neither prime nor composite.

Remark 3.2.6. The importance of being strict or equal.

Notice in the above definition the emphasis we have placed on strictly greater than one. We really want the reader to realise that we mean “\(\gt\)” and not “\(\geq\)”. In general, when writing inequalities in words (rather than symbols) it is a good idea to be very explicit so as to avoid possible confusion:
  • \(a\lt b\text{:}\) “\(a\) strictly less than \(b\)”
  • \(a\leq b\text{:}\) “\(a\) less than or equal to \(b\)”
If we were to write “\(a\) less than \(b\)” we may leave the reader confused as to whether or not \(a\) is allowed to be equal to \(b\text{.}\)
Let us go back to one of our first examples, and now that we have the right definitions and have done the required logic, we can prove it.
Lets think through our truth table again:
  • If the hypothesis is false, the implication is true — no work required.
  • If the hypothesis is true, then the implication will be true or false depending on the truth value of the conclusion — work required!
Just as we will many many times in the future, we start by assuming the hypothesis is true.
Assume \(n\) is an even number.
What are we trying to get to?
\(n^2\) is an even number.
At this point we know where we will start and where we need to end up, so a good next step is to flesh out what both the hypothesis and conclusion mean.
  • If \(n\) is an even number then we can write it as \(n=2k\text{,}\) where \(k\) is an integer.
  • If \(n^2\) is an even number then we can write it as \(n^2=2\ell\text{,}\) where \(\ell\) is an integer.

Remark 3.2.8. Not all even numbers are equal.

Notice here that our result involves two even numbers, \(n\) and \(n^2\text{.}\) When I have invoked the definition of even, I have been careful to write \(n=2k\) and \(n^2=2\ell\) using different symbols. This is important because it helps us to avoid making any additional assumptions about those numbers. Maybe we’ll end up showing they are the same, and maybe we won’t.
If we were to accidentally use the same symbols (and the authors know you won’t do this after this warning), then we would have
  • \(n\) is even, so \(n=2k\)
  • \(n^2\) is even, so \(n^2=2k\)
  • But then \(n^2=n\) which means \(n^2-n = 0\)
  • Factoring this gives \(n(n-1)=0\) and so \(n=0,1\)
So by reusing the symbol “\(k\)”, we have inadvertently assumed that \(n=0,1\text{,}\) which is definitely not the result as stated.
Now since we know that \(n=2k\text{,}\) we also know that \(n^2=(2k)(2k)=4k^2\text{.}\) From this we know \(n^2=4k^2 = 2(2k^2)\text{.}\) Since \(k\) is an integer, \(k^2\) is an integer and \(2k^2\) is an intger. So we’ve shown that \(n^2\) can be written as twice and integer. In other words, we shown that it is even — exactly what we needed to do.
But we’re not done. We have (in our work above) worked out how to prove our result, but we still need to write it up nicely. In this way proving a result really breaks into two parts
Scratch work
Scratch work or proof-strategy or exploration or … — this is typically the difficult part, trying to work out what is going on, what does the hypothesis mean, what does the conclusion mean, how do we get from one to the other. What is the idea or path of the proof.
Write-up
Once we have all the ideas and parts we still need to write things up nicely. This is typically easier than the scratch work, but it is non-trivial. We’ll still need to work to make sure our presentation is clear, precise and easy to follow.
Let’s write more nicely (and quite explicitly) with dot-points.
  • Assume \(n\) is even.
  • So we can write \(n=2k\text{,}\) where \(k \in \mathbb{Z}\text{.}\)
  • But now, \(n^2 = 4k^2\text{.}\)
  • This in turn implies that \(n^2=2(2k^2)\text{.}\)
  • Since \(2k^2\) is an integer, it follows that \(n^2\) is even.
Notice that we don’t prove that \(2k^2 \in \mathbb{Z}\text{,}\) nor do we have to explain basic facts about multiplication (as stated in Axiom 3.0.1); it is sufficiently obvious 36  that we can assume the reader will follow. Recall that back at the start of this chapter we warned you that we would make such assumptions about our (hypothetical) reader when writing our proofs.
Also notice the structure of the proof.
  • \(P\) is true — where \(P\) is “\(n\) is even”.
  • \(P \implies P_1\) is true — where \(P_1\) is “\(n=2k\) for some \(k\in\mathbb{Z}\)”.
    This follows from the definition of even.
  • \(P_1 \implies P_2\) is true — where \(P_2\) is “\(n^2=4k^2\)”.
    This is a basic fact about multiplication. To be more specific, “if \(a=b\) then \(ac=bc\)”.
  • \(P_2 \implies P_3\) is true — where \(P_3\) is “\(n^2\) is twice an integer”.
    We are really using the fact that \(4=2\times2\) and that multiplication is associative; we can expect the reader to understand this 37 .
  • \(P_3 \implies Q\) is true.
    This is just the definition of even again.
So we have really shown
\begin{gather*} (P \implies P_1) \land (P_1 \implies P_2) \land (P_2 \implies P_3) \land (P_3 \implies Q) \end{gather*}
And since we assume \(P\) is true, \(P_1\) is true (modus ponens is our friend). Since \(P_1\) is true, \(P_2\) is true. And so forth until we conclude that \(Q\) is true. Hence we have shown that when \(P\) is true, we must have that \(Q\) is true.
This sort of proof in which we start by assuming the hypothesis is true and then work towards the conclusion is called a direct proof.
Now of course, when we actually prove something we don’t go into this level of lurid detail. But for a first proof its not a bad idea to really see what is going. Let’s write the proof more compactly, and a little more naturally:
Assume \(n\) is even. Hence we can write \(n=2k\) where \(k \in \mathbb{Z}\text{.}\) Then \(n^2=4k^2=2(2k^2)\text{.}\) Since \(2k^2 \in \mathbb{Z}\) it follows that \(n^2\) is even.
You can see there are some standard phrases that get used again and again
  • Hence…
  • It follows that…
  • So…
  • This implies that…
  • We can now write…
These serve to make the proof more legible and flow a little more naturally.
We don’t leap into the proof; we start with scratch work.
  • Assume the hypothesis is true (if it is false, there is nothing to be done).
  • The hypothesis means that \(n=2k+1\) for some integer \(k\text{.}\)
  • The conclusion means that \(2n+7 = 2\ell+1\) for some \(\ell \in \mathbb{Z}\text{.}\)
  • But if \(n=2k+1\text{,}\) then \(2n+7 = 2(2k+1)+7 = 4k+9 = 2(2k+4)+1\text{.}\)
  • Since \(2k+4 \in \mathbb{Z}\text{,}\) \(2n+7\) is odd.
So we’ve got the idea, lets write it up.
Assume that \(n\) is an odd integer and so \(n=2k+1\) for some \(k \in \mathbb{Z}\text{.}\) So
\begin{align*} 2n + 7 &= 2(2k+1)+7 = 4k+9 = 2(2k+4)+1. \end{align*}
Since \(k\) is an integer, \(2k+4\) is also an integer and so \(2n+7\) is odd.
Another one — this one for you
Do your scratch work before you write up the proof — even if you see the way to prove it. Writing the scratch work really helps to formulate your ideas and makes writing out the proof much easier.
Assume that \(n\) is an odd integer and so \(n=2k+1\) for some \(k \in \mathbb{Z}\text{.}\) So
\begin{gather*} n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1 \end{gather*}
Since \(k\) is an integer, \(2k^2+2k\) is also an integer and so \(n^2\) is odd.
Assigning numbers to results, lemmas, theorems and so on is standard practice in mathematical writing. Unfortunately the topic of numbering equations is much less settled. This author has gotten into some strongly worded “discussions” with their coauthors on exactly this topic. Some authors like to number all equations, some like to only number the equations that get referenced inside the same document, and some like to number only the important equations. See these papers for an good discussion of numbering, Samaritans, Fisher, Occam and Fisher-Occam. It is also a good illustration of how mathematicians like a good argument over tiny details.
cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html
Well known to those that know it well, as this author’s PhD supervisor says.
Or they can quickly recall (or search-engine towards recalling) that the associativity of multiplication is just the fact that \(a \times (b \times c) = (a\times b)\times c\text{.}\)
<Prev^TopNext>