Proof Technique: Direct Proofs
At this point, we’ve talked a lot about mathematical logic, arguments, and some common terminology. In this section, we introduce a method for providing a proof for a proposition — the most straightforward technique we have at our disposal.
The Underlying Argument
Consider a statement such as $p \to q$ — but remember that a theorem is almost always implicitly universally quantified, so what we really want to show is $\forall x\ [p(x) \to q(x)]$ for every element $x$ within some universe $\mathcal{U}$. How would we show this is always true?
Recall the strategy behind the Rule of Universal Generalization: pick an arbitrary element $x_0 \in \mathcal{U}$, establish some property for that one element, then generalize the result to the entire universe. Suppose we assume $p(x_0)$ holds for our arbitrarily chosen $x_0$, and suppose we also have some already-established fact — a definition, a piece of algebra, or a previously proven theorem — telling us $p(x_0) \to q(x_0)$ is true for this particular $x_0$. The argument
\[ \begin{array}{l} p(x_0) \\ p(x_0) \to q(x_0) \\ \hline \therefore \forall x\ [p(x) \to q(x)] \end{array} \]is the basis for any direct proof. Is this argument valid?
\[ \begin{array}{lll} \textbf{Step} & \textbf{Proposition} & \textbf{Reason} \\ (1) & x_0 \in \mathcal{U} & \text{We can always pick an arbitrary element from a non-empty universe} \\ (2) & p(x_0) & \text{Assumed Premise} \\ (3) & p(x_0) \to q(x_0) & \text{Established Fact} \\ (4) & q(x_0) & \text{Modus Ponens on (2) and (3)} \\ (5) & \therefore \forall x\ [p(x) \to q(x)] & \text{Rule of Universal Generalization on (1), (2), and (4)} \end{array} \]Notice that step (3) is labeled an established fact rather than an assumed one — it can’t simply be handed to us as a premise, since that would already be the theorem we’re trying to prove. Instead, it has to come from somewhere else entirely: a definition, an algebraic identity, or an already-proven theorem that happens to connect $p(x_0)$ to $q(x_0)$ for this particular $x_0$. And step (5)’s conclusion isn’t generalizing the bare fact $q(x_0)$ from step (4) alone — it’s generalizing the implication $p(x_0) \to q(x_0)$, which is really what’s been established once we notice that $q(x_0)$ only followed because we assumed $p(x_0)$ in the first place. That’s why the citation for step (5) includes step (2) as well as step (4).
Since $x_0$ was an arbitrary element of $\mathcal{U}$ — not some specific one — the Rule of Universal Generalization lets us conclude the implication holds for every element of $\mathcal{U}$, not just the one we happened to pick.
This strategy is called a direct proof because we start by assuming the hypothesis $p(x_0)$, and derive the conclusion $q(x_0)$ from it directly, via a single use of Modus Ponens. In practice, establishing $p(x_0) \to q(x_0)$ itself might take several steps — appealing to definitions, algebra, or previously proven theorems along the way — but each of those steps is really just another instance of this same pattern: take a fact you already have, apply a known implication, get the next fact, and repeat until you reach the conclusion.
An In-Depth Example
Let’s break down a simple example of a proof for a mathematical proposition. Since we’re providing a proof, we can call the proposition a theorem.
Consider the statement “If $n$ is an even integer, then $n + 1$ is an odd integer.” Since the hypothesis and conclusion are both about integers, our universe of discourse is $\mathbb{Z}$. Let
\[ \begin{array}{rl} e(n)\text{: } &n \text{ is even.} \\ o(n)\text{: } &n \text{ is odd.} \end{array} \]Implicit as usual is the universal quantifier, so this rewrites as $\forall n\ [e(n) \to o(n + 1)]$ (we don’t write $\forall n \in \mathbb{Z}$ explicitly, since it’s clear from context that we’re only considering integers).
So, how do we show $e(n) \Longrightarrow o(n + 1)$? We can appeal to the definitions of even and odd. Since we’re asserting $n$ is even (if it weren’t, the implication would be trivially true), there’s some integer $k$ such that $n = 2k$. But if $n = 2k$, then $n + 1 = 2k + 1$ — always true, since we can substitute $2k$ for $n$ wherever it appears. Now, $2k + 1$ satisfies the definition of odd. Since $n + 1 = 2k + 1$, and $2k + 1$ is odd, $n + 1$ is odd. We don’t know exactly which integer $k$ or $n$ is, except that $n$ must be even — but everything we did applies to all even integers, meaning adding one to an even integer always gives an odd integer.
Written out formally, with $e(n)$ and $o(n)$ as before, along with
\[ \begin{array}{rl} p(n)\text{: } &\exists k\ [n = 2k] \\ q(n)\text{: } &\exists k\ [n = 2k + 1] \end{array} \]and picking a specific but arbitrary integer $n_0$ where $e(n_0)$ is assumed as a premise:
\[ \begin{array}{lll} \textbf{Step} & \textbf{Proposition} & \textbf{Reason} \\ (1) & \forall n\ [e(n) \leftrightarrow p(n)] & \text{Definition of Even Integer} \\ (2) & e(n_0) \leftrightarrow p(n_0) & \text{Universal Specification on (1)} \\ (3) & (e(n_0) \to p(n_0)) \land (p(n_0) \to e(n_0)) & \text{Law of Mutual Implication} \\ (4) & e(n_0) \to p(n_0) & \text{Conjunctive Simplification on (3)} \\ (5) & e(n_0) & \text{Assumed Premise} \\ (6) & p(n_0) & \text{Modus Ponens on (4) and (5)} \\ (7) & \forall n\ [p(n) \to q(n + 1)] & (n = 2k) \Longleftrightarrow (n + 1 = 2k + 1) \text{ for all integers } n \\ (8) & p(n_0) \to q(n_0 + 1) & \text{Universal Specification on (7)} \\ (9) & q(n_0 + 1) & \text{Modus Ponens on (6) and (8)} \\ (10) & \forall n\ [o(n) \leftrightarrow q(n)] & \text{Definition of Odd Integer} \\ (11) & o(n_0 + 1) \leftrightarrow q(n_0 + 1) & \text{Universal Specification on (10)} \\ (12) & (o(n_0 + 1) \to q(n_0 + 1)) \land (q(n_0 + 1) \to o(n_0 + 1)) & \text{Law of Mutual Implication} \\ (13) & q(n_0 + 1) \to o(n_0 + 1) & \text{Conjunctive Simplification on (12)} \\ (14) & o(n_0 + 1) & \text{Modus Ponens on (9) and (13)} \\ (15) & \therefore \forall n\ [e(n) \to o(n + 1)] & \text{Universal Generalization on (5) and (14)} \end{array} \]One last thing to note: the same placeholder $n_0$ is used throughout — in the Universal Specification steps and the assumed premise alike — because we want to show that when a particular integer is even, the integer one more than it is odd. All our manipulations have to happen on the exact same number, or we wouldn’t know the result holds.
And there we have it — a fully worked-out proof for a simple result. Most of the time, proof-writing uses a mixture of English, arithmetic, and algebraic manipulation written out in a paragraph format. We showed this one using formal logic to demonstrate that, if we’re ever unsure whether a proof is correct, we can fall back on the tools of mathematical logic. From here on, we’ll write proofs using this more conventional, paragraph-style approach instead.
A Conventionally Written Proof
Let’s rewrite the previous, very lengthy proof in a more conventional style.
If $n$ is even, then $n + 1$ is odd.
Proof 2.13.1
Because $n$ is even, there exists some integer, which we’ll call $k$, such that $n = 2k$. Adding $1$ to both sides yields $n + 1 = 2k + 1$. But $2k + 1$ is odd by definition, and since $n + 1 = 2k + 1$, we must have that $n + 1$ is odd, as desired.
This proof is much more compact, and much easier to follow. Again, if we’re ever unsure whether a proof is correct, we can write out the open statements, refer to the rules of inference, and lay out an argument in tabular form. Theorems and their proofs will be presented in specially marked magenta boxes going forward — if you’d like to try providing a proof before seeing one (always an excellent exercise), the proof stays collapsed until you’re ready to see it.
More Theorems and Proofs Regarding Even and Odd Numbers
Our next few theorems expand on the idea of even and odd numbers.
If $n$ is odd, then $n + 1$ is even.
Proof 2.13.2
Because $n$ is odd, there exists some integer $k$ such that $n = 2k + 1$. Adding $1$ to both sides yields $n + 1 = 2k + 1 + 1 = 2k + 2$. Notice that a factor of $2$ can be brought out on the right-hand side: $n + 1 = 2(k + 1)$. But $k + 1$ is an integer, which we can refer to as $\ell$. Thus, there exists some integer $\ell$ such that $n + 1 = 2\ell$, meaning $n + 1$ is even, as desired.
If $n$ is even, then $n + 2$ is even.
Proof 2.13.3
By the previous theorem, since $n$ is even, $n + 1$ is odd. Then by the theorem before that, $(n + 1) + 1$ must be even. Notice that $(n + 1) + 1 = n + 2$, meaning $n + 2$ is even, as desired.
If $n$ is odd, then $n + 2$ is odd.
Proof 2.13.4
This result is proved using nearly identical logic to the previous theorem.
Let’s quickly discuss the first two theorems above. They may seem obvious to anyone with a high-school education, but they give us a chance to practice writing proofs using easy results — meaning we can easily check the logic used is valid. The main tool in both proofs was the definitions of even and odd integer, with a little algebra to make sure the relevant equations stayed balanced after adding $1$ to $n$.
The third theorem had an interesting proof: we used two previous theorems, which is completely valid, since they’re already proven to be true. The fourth theorem’s proof is perhaps the simplest so far — we could have invoked the second theorem first on $n$, then the third on $n + 1$, but the similarity to the third theorem’s proof was close enough that we could almost copy it directly. Sometimes this is warranted; other times there’s enough of a difference to necessitate an original proof.
Let’s expand our understanding of even and odd numbers even further.
If $m$ and $n$ are both even, then $m + n$ is even.
Proof 2.13.5
Since $m$ is even, there exists some integer $a$ such that $m = 2a$. Likewise, there’s some integer $b$ such that $n = 2b$. Thus,
$$m + n = 2a + 2b = 2(a + b).$$Since $a$ and $b$ are integers, $a + b$ must be an integer too, which we’ll refer to as $c$. Hence $m + n = 2c$, which satisfies the definition of even. Thus, $m + n$ is even, as desired.
If $m$ is even, and $n$ is odd, then $m + n$ is odd.
Proof 2.13.6
Since $m$ is even and $n$ is odd, there exist integers $a$ and $b$ such that $m = 2a$ and $n = 2b + 1$. Adding $m$ and $n$ together:
$$m + n = 2a + 2b + 1 = 2(a + b) + 1.$$Since $a$ and $b$ are integers, $a + b$ is also an integer, which we’ll call $c$. Thus $m + n = 2c + 1$, satisfying the definition of odd. Hence $m + n$ is odd, as desired.
If $m$ and $n$ are both odd, then $m + n$ is even.
Proof 2.13.7
Since $m$ and $n$ are both odd, there exist integers $a$ and $b$ such that $m = 2a + 1$ and $n = 2b + 1$. Adding $m$ and $n$ together:
\[ \begin{array}{lll} \boldsymbol{m + n} & = & (2a + 1) + (2b + 1) \\ & = & 2a + 2b + 2 \\ & = & 2(a + b + 1) \end{array} \]where in the last step, we simply factored a $2$ out of all three terms. Since $a$, $b$, and $1$ are all integers, $a + b + 1$ is an integer too, which we’ll call $c$ — meaning $m + n = 2c$, so $m + n$ is even, as desired.
It’s usually a good idea to play around with a theorem to see how it works in practice.
Both $6$ and $18$ are even, and $6 + 18 = 24 = 2 \cdot 12$, so their sum is also even — matching what we’d expect.
$-3$ is odd and $98$ is even, so the sum should be odd: $-3 + 98 = 95 = 94 + 1 = 2 \cdot 47 + 1$. As predicted.
Both $-17$ and $1983$ are odd, so the sum should be even: $-17 + 1983 = 1966 = 2 \cdot 983$. As predicted.
The next proof involves a product instead of a sum.
If $m$ and $n$ are both odd, then $mn$ is odd.
Proof 2.13.8
Since $m$ and $n$ are both odd, there exist integers $a$ and $b$ such that $m = 2a + 1$ and $n = 2b + 1$. Multiplying $m$ and $n$ together:
\[ \begin{array}{lll} \boldsymbol{mn} & = & (2a + 1)(2b + 1) \\ & = & 4ab + 2a + 2b + 1 \\ & = & 2(2ab + a + b) + 1 \\ & = & 2c + 1 \end{array} \]Because there exists an integer $c$ such that $mn = 2c + 1$, $mn$ is odd by definition, as desired.
Notice that in the last step, we simply replaced the quantity $2ab + a + b$ with the single letter $c$ — since $2$, $a$, and $b$ are integers, $2ab + a + b$ must be an integer too, so we can just refer to it as $c$ to make the subsequent step easier. Just like we can always make substitutions in algebra, we can make substitutions for algebraic expressions in proofs too — we should just make clear what substitution is being used.
Theorems and Proofs Involving Square Numbers
Let’s explore some more theorems involving square numbers, along with even and odd numbers.
If $n$ is even, then $n^2$ is even.
Proof 2.13.9
Because $n$ is even, there’s some integer $k$ such that $n = 2k$. Squaring $n$:
\[ \begin{array}{lll} \boldsymbol{n^2} & = & (2k)^2 \\ & = & 4k^2 \\ & = & 2 \cdot 2k^2 \end{array} \]Since $k$ and $2$ are both integers, $2k^2$ is an integer too, which we can call $k_0$. This means $n^2 = 2k_0$, so $n^2$ is even, as desired.
The algebra in a proof like this can be handled however you feel comfortable — simple steps can be omitted or combined, but anything tricky should be clearly laid out.
If $n$ is odd, then $n^2$ is odd.
Proof 2.13.10
Because $n$ is odd, $n^2 = n \cdot n$, a product of two odd integers. The previous theorem on products of odd integers guarantees $n \cdot n$ is odd, so $n^2$ is odd, as desired.
This proof is another demonstration of how previous theorems can be used in the proofs of other theorems.
The next theorem’s proof has some tricky algebra, so it’ll be laid out more carefully. This theorem is actually just the converse of the previous one — and remember, just because a theorem is true doesn’t mean its converse is automatically true.
If $n^2$ is odd, then $n$ is odd.
Proof 2.13.11
Since $n^2$ is odd, there’s some integer $k$ such that $n^2 = 2k + 1$. Moving the $1$ to the left-hand side gives $n^2 - 1 = 2k$. We have a difference of squares (since $1 = 1^2$), so we can factor the left-hand side:
$$(n - 1)(n + 1) = 2k.$$Notice that $(n - 1) + 2 = (n + 1)$, meaning $(n-1)$ and $(n+1)$ are either both even, or both odd. Since $(n-1)(n+1) = 2k$, whatever integer $(n-1)(n+1)$ equals must be even — meaning at least one of $(n-1)$ and $(n+1)$ is even. But since both must be even or both must be odd, we have that both $(n-1)$ and $(n+1)$ are even.
Since $(n-1)$ is even, and $(n-1) + 1 = n$, the theorem stating that an even integer plus one is odd guarantees that $n$ must be odd. Hence, $n$ is odd, as desired.
This proof required a common algebraic trick — factoring a difference of squares — but just because it’s common doesn’t mean it’s an obvious step. It also required knowing a bit more about even and odd integers than what’s shown here (though these facts aren’t too hard to prove either). Why that trick specifically, and not one of the myriad other tricks available?
If we’re lucky, or clever enough to squint at the problem just right, we might have a flash of insight on how to proceed. But we also could have tried taking the square root of both sides of the first equation: $n = \sqrt{2k+1}$. What do we do with that? Nothing seems like a good next step — we’re stuck. We do have $n$ isolated on the left-hand side, which is generally a good strategy in proofs, but here it leaves us with no way to proceed. Perhaps if we were really good at handling roots in equations we could push through, but nothing comes to mind immediately.
Sometimes we’ll have no choice but to deal with sticky algebraic expressions — but other times, clever logic can free us from having to rely on algebra that might be too clever for us to grasp in a timely manner. One such logical strategy is the subject of the next section.