Consider a statement such as

p → q.

How would we be able to show that implication to always be true? In other words, how do we show that

p ⟹ q?

Suppose that we (somehow) knew that

p ⟹ r
r ⟹ q.

This basically reduces down to the Law of the Syllogism. Since we have p ⟹ r, we know that the proposition p → r is always true. Similarly, we know that the proposition r → q is always true. Hence:

This proof strategy is called a direct proof because the proposition we’re trying to show has p as the hypothesis and q as the conclusion. The first premise has p as the hypothesis, and the last premise has q as the conclusion. We’re essentially chaining a bunch of implications together to get from p to q.

Let’s break down a simple example of a proof that can be supplied for a mathematical proposition. Since we’re providing a proof for this mathematical proposition, we can call the proposition a theorem.

Consider the following statement:

If n is an even integer, then n + 1 is an odd integer.

First, let’s make clear what our universe is. Because we have an implication where the hypothesis and conclusion are talking about integers, our universe of discourse will be the collection of all integers, which is commonly denoted by ℤ (we are not using the general symbol 𝒰 for this universe since the collection of integers has a pretty well-established symbol at this point in time.)

Implicit as usual is the universal quantifier in the implication, so the proposition

If n is an even integer, then n + 1 is an odd integer

can be rewritten as

∀n [e(n) → o(n + 1)]

Also worth noting is that, as usual, we didn’t write ∀n ∈ ℤ [e(n) → o(n + 1)] because it should be clear from the problem’s context that we are only considering integers, and so when we choose a value for n, we will choose integer numbers.

So, how do we show that ∀n [e(n) → o(n + 1)] is always true? In other words, how do we show that

e(n) ⟹ o(n + 1)?

Something we can try is to appeal to the definition of even number and odd number. Since we are asserting that n is an even integer (if n were not an even integer, then the above implication is trivially true,) we know that there exists some other integer k such that

n = 2k.

But wait, if n is equal to 2k, then n + 1 would have to be equal to 2k + 1. This is always true because we can substitute 2k for n whenever we see an n in an equation.

Now notice that we have 2k + 1, which satisfies the definition of an odd integer. Thus, since n + 1 is equal to 2k + 1, and 2k + 1 is an odd integer, then n + 1 is an odd integer. We don’t necessarily know what particular integer 2k + 1 is, but we also don’t know what particular integer n is either, except that n must be even. Thus, everything we did for n was applicable to all even integers, meaning anytime we add one to an even integer, we get an odd integer. This completes our proof, and so we have a theorem. Whenever n is an even integer, n + 1 must be an odd integer.

So, how would we write this argument out in mathematical logic notation? First, let’s define some open statements. We can pick out four open statements in particular:

e(n):	n is even
o(n):	n is odd
p(n):	∃k [n = 2k]
q(n):	∃k [n = 2k + 1]

Note that the n used in defining the open statements is not referring to the n used throughout this proof. The letter n is being used in the open statements to show what happens when a number is substituted in for n. It is a common occurrence in mathematics to reuse certain letters for different purposes. Usually, we strive to pick different letters, but that can also be a hassle. It should be clear from context which variables are being used, but it is something to get used to. For example, we have that

e(x):	x is even
o(α):	α is odd
p(n0):	∃k [n0 = 2k]
q(m + 1):	∃k [m + 1 = 2k + 1]

The statement we’re trying to prove is

∀n [e(n) → o(n + 1)].

When trying to write out our argument in tabular form, we need some premises. One premise we can assume is e(n₀) where n₀ is a specific integer that is arbitrarily chosen. This is because as discussed in the section on Universal Generalization, there’s no point in working with ∀n [e(n) → o(n + 1)] if we’re working with some integer n₀ where e(n₀) = 0 because then the implication e(n₀) → o(n₀ + 1) is trivially true. We want to make sure that when e(n₀) is true, then so is o(n₀ + 1), and so any situation where e(n₀) is false is pointless. Hence, we have the argument

Now, we’ll validate the above argument using the rules of inference, along with the definitions of even integer and odd integer:

There are a couple of things to observe about this argument. The reasons listed for steps (3), (7), and (12) use the letters p, q, n, and k. Note that in the given reasons, the letters do not necessarily refer to the exact same variables being used in the propositions. The letters in the reasons are just general placeholders. We could have used other letters such as w, x, y, and z. However, letters n and k are very commonly used to represent integers, and letters e and o seem convenient to denote even and odd integers respectively.

In steps (3) and (12), we made use of the logical equivalence between a biconditional and the conjunction of two implications:

x ↔ y ⟺ (x → y) ∧ (y → x)

Remember, logical equivalencies can be used as reasons in arguments. This is because in any logical expression, two propositions that are logically equivalent can always be substituted for one another.

The reason given in step (7) is a result of basic algebra. Remember if any two numbers are equal to each other, then we can add one to both numbers, and those two new numbers will also be equal to each other. The truth of this result is near-axiomatic. For example, we obviously have that

5 = 5

We can’t just add 1 to only a single side of the equation:

5 + 1 ≠ 5 (6 ≠ 5)

We must add 1 to both sides in order for the equation to be true:

5 + 1 = 5 + 1 (6 = 6)

We’ll re-write this proof in a more conventional style later in this section where we won’t explicitly point out this fact. We only listed this reason for the sake of total completeness in the tabular argument provided above. Usually in a conventionally written proof, these kinds of obvious facts are left out of the detail because most readers will just assume this knowledge to be true (in further, more deep and nuanced study of mathematical logic, these facts are not assumed, but must also be proven, though that is well beyond the scope of this book.) Usually, basic arithmetic and algebra doesn’t need explicit mention, though trickier and more careful arithmetic and algebra should be fully worked out.

One last thing to note is that when we invoked the rule of Universal Specification in steps (2), (8), and (11), along with the assumed premise in step (5), we used the same placeholder n₀. In this validation, we are using the exact same arbitrarily chosen integer in all steps because we want to show that when an integer is even, the integer that is one more is an odd integer. Hence, we must do all of our manipulations on the exact same element. If we used different numbers throughout the argument, then we wouldn’t know that the result holds.

And there we have it, a fully worked out proof for a simple result. Whenever we want to provide a proof for a theorem, we can always carefully write out several propositions and layout a formal argument as we did above. Most of the time, proof-writing will use a mixture of English language, arithmetic, and algebraic manipulation written out in a paragraph format. We showed how to write out a proof using formal logic because if we’re ever unsure of the correctness of a given proof, we can use the tools of mathematical logic for analysis.

From here on out, fully written out tabular arguments will be rarely presented, if at all. Instead, we will write out proofs for theorems using a more conventional paragraph style.

Let’s rewrite the above, very lengthy proof in a more conventional style.

The proof given is much more compact and much easier to follow. Again, if we’re ever unsure if a given proof is correct, we can write out the open statements, refer to the rules of inference, and write out an argument in tabular form.

As noted in this style guide, we will present theorems and their proofs in specially marked magenta boxes. If you wish to try and provide a proof before seeing one (always an excellent learning exercise,) you can leave the proof hidden until you are ready to see one. This is the preferred style for these books. Other books and authors have their own styles for presenting proofs in books and papers.

Our next few theorems expand on the idea of even and odd numbers.

Let’s quickly discuss Theorem 2.9.1 and Theorem 2.9.2. These results seem obvious to anyone with a high school education, but they give us a chance to practice writing proofs using easy results. This means we can easily check that the logic used in the proofs is valid. The main tool we used in the proof were the definitions of even integer and odd integer. Of course, there was a little bit of algebra involved too, but not much. We just had to make sure that the relevant equations remained balanced after adding 1 to n.

Theorem 2.9.3 had an interesting proof. There, we used two previous theorems. This is completely valid, since those are theorems (meaning they are already proven to be true.) Hence, since they are true, we can use those as facts in our proof.

Finally, the proof given for Theorem 2.9.4 is perhaps the simplest proof given so far. Of course, we could just invoke Theorem 2.9.4 first on n, and then invoke Theorem 2.9.3 on n + 1 to get the desired result, but that seems like a minor enough detail that we can almost simply copy and paste the proof from Theorem 2.9.3. Sometimes this is warranted, other times there may be enough differences to necessitate writing out an original proof.

Let’s expand our understanding of even and odd numbers even further!

It’s usually a good idea to play around with a theorem to see how it can work in practice, so let’s go over a quick example.

The next proof involves a product instead of a sum.

Notice that in the last step in the chain of equations in the proof for Theorem 2.9.8, we simply replaced the quantity (2ab + a + b) with the single letter c. Since 2, a, and b are integers, we also know that the quantity (2ab + a + b) must also be an integer. We can just use the letter c to refer to that integer, which makes the subsequent steps a bit easier.

Just like we can always make substitutions in algebra, we can also make substitutions for algebraic and arithmetic expressions in proofs. We should just make clear what substitution is being used.

Let’s explore some more theorems and proofs that involve square numbers along with even and odd numbers.

The algebra in the above proof can be handled however we feel comfortable. Simple steps can be omitted or combined as desired, but again, anything tricky should be clearly laid out.

Theorem 2.9.10 provides another demonstration of how previous theorems can be used in the proofs of other theorems.

The next theorem’s proof has some tricky algebra, and as such, the algebra and arithmetic will be more clearly laid out. The next theorem is actually just the converse of Theorem 2.9.10. Remember, just because a theorem is true, does not mean its converse is automatically true. A proposition is not necessarily logically equivalent to its converse.

The proof for Theorem 2.9.11 required a common algebraic trick (factoring a difference of squares), but just because it is common, does not mean it’s an obvious step for the proof. It also required knowing some more about even and odd integers than what we showed here, though those results are not too hard to prove. Furthermore, why that algebraic trick? Why not one of the other myriad of tricks that are available to us?

If we’re lucky or clever enough to squint at the problem just right, we may have a flash of insight on how to proceed as we did. But something else we could have tried doing is taking the square root of both sides of the first equation in the proof:

What exactly do we do with that? Nothing seems like a good next step, so we’re stuck here. Yeah, we have n on the left-hand side, which is good, because we’re trying to show that n satisfies some property. In general, it’s actually a good strategy in proofs to try and express the quantity of interest in an equation where it is isolated on one side of the equation. However, in this particular problem, it leaves us stuck with no way to proceed. Perhaps if we’re really good at handling roots in equations, then we could proceed, but nothing comes to mind immediately.

Sometimes, we’ll have no choice but to try and deal with these sticky algebraic expressions, but other times, we can sidestep a lot of algebra. As a matter of fact, the use of clever logic frees us from having to rely on clever algebra, which may be too clever for us to grasp in a timely manner. One such logical strategy is the subject of the next section.