# 1.6: Proof

- Page ID
- 6713

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Mathematics is unique in that it claims a certainty that is beyond all pos- sible doubt or argument. A mathematical proof shows how some result follows by logic alone from a given set of assumptions, and once the result has been proven, it is as solid as the foundations of logic themselves. Of course, mathematics achieves this certainty by restricting itself to an arti- ficial, mathematical world, and its application to the real world does not carry the same degree of certainty.

Within the world of mathematics, consequences follow from assumptions with the force of logic, and a proof is just a way of pointing out logical consequences. There is an old mathematical joke about this:

This mathematics professor walks into class one day and says “We’ll start today with this result, which is obvious,” and he writes it on the board. Then, he steps back and looks at the board for a while. He walks around the front of the room, stares into space and back at the board. This goes on till the end of class, and he walks out without saying anything else. The next class period, the professor walks into the room with a big smile, writes the same result on the board, turns to the class and says, “I was right. It is obvious.”

For of course, the fact that mathematical results follow logically does not mean that they are obvious in any normal sense. Proofs are convincing once they are discovered, but finding them is often very difficult. They are written in a language and style that can seem obscure to the uninitiated. Often, a proof builds on a long series of definitions and previous results, and while each step along the way might be “obvious,” the end result can be surprising and powerful. This is what makes the search for proofs worthwhile.

In the rest of this chapter, we’ll look at some approaches and techniques that can be used for proving mathematical results, including two important proof techniques known as proof by contradiction and mathematical induc- tion. Along the way, we’ll encounter a few new definitions and notations. Hopefully, you will be left with a higher level of confidence for exploring

The mathematical world and the real world weren’t always quite so separate. Until some time near the middle of the nineteenth century, the statements of mathematics were regarded as statements about the world. A proof was simply a convincing argument, rather than a chain forged of absolute logic. It was something closer to the original meaning of the word “proof”, as a test or trial: To prove something was to test its truth by putting it to the trial of logical argument.

The first rumble of trouble came in the form of **non-Euclidean geometry.** For two thousand years, the geometry of the Greek mathematician Euclid had been accepted, simply, as the geometry of the world. In the middle of the nineteenth century, it was discovered that there are other systems of geometry, which are at least as valid and self-consistent as Eu- clid’s system. Mathematicians can work in any of these systems, but they cannot all claim to be working in the real world.

Near the end of the nineteenth century came another shock, in the form of cracks in the very foundation of mathematics. At that time, mathematician Gottlieb Frege was finishing a book on set theory that represented his life’s work. In Frege’s set theory, a set could be defined by any property. You could have, for example, the set consisting of all sets that contain three objects. As he was finishing his book, Frege received a letter from a young mathematician named Bertrand Russell which described what be- came known as **Russell’s Paradox.** Russell pointed out that the set of all sets—that is, the set that contains every entity that satisfies the property of being a set—cannot logically exist. We’ll see Russell’s reasoning in the following chapter. Frege could only include a postscript in his book stating that the basis of the work had been swept away.

Mathematicians responded to these problems by banishing appeals to facts about the real world from mathematical proof. Mathematics was to be its own world, built on its own secure foundation. The foundation would be a basic set of assumptions or “axioms” from which everything else would follow by logic. It would only be necessary to show that the axioms themselves were logically consistent and complete, and the world of mathematics would be secure. Unfortunately, even this was not to be. In the 1930s, Kurt G ̈odel showed that there is no consistent, finite set of axioms that completely describes even the corner of the mathematical world known as arithmetic. G ̈odel showed that given any finite, consistent set of axioms, there are true statements about arithmetic that do not follow logically from those axioms.

We are left with a mathematical world in which iron chains of logic still bind conclusions to assumptions. But the assumptions are no longer rooted in the real world. Nor is there any finite core of axioms to which the rest of the mathematical world can be chained. In this world, axioms are set up as signposts in a void, and then structures of logic are built around them. For example, instead of talking about the set theory that describes the real world, we have a set theory, based on a given set of axioms. That set theory is necessarily incomplete, and it might differ from other set theories which are based on other sets of axioms.

Understandably, mathematicians are very picky about getting their proofs right. It’s how they construct their world. Students sometimes object that mathematicians are too picky about proving things that are “obvious.” But the fact that something is obvious in the real world counts for very little in the constructed world of mathematics. Too many ob- vious things have turned out to be dead wrong. (For that matter, even things in the real world that seem “obviously” true are not necessarily true at all. For example, consider the quantity \(f(n) = n2 + n + 41\). When \(n = 0, f(n) = 41\) which is prime; when \(n = 1, f(n) = 43\) which is prime; when \(n = 2, f(n) = 47\), which is prime. By the time you had calculated \( f(3),f(4),...,f(10)\) and found that they were all prime, you might conclude that it is “obvious” that \(f(n)\) is prime for all \(n ≥ 0\). But this is not in fact the case! (See exercises.) Similarly, those of you who are baseball fans might consider it “obvious” that if player A has a higher batting average against left-handers than player \(B\), and player \(A\) has a higher batting average against right-handers than player \(B\), then player \(A\) must have a higher batting average than player \(B\). Again, this is not true!)

As we saw in Section 1.5, a formal proof consists of a sequence of statements where each statement is either an assumption or follows by a rule of logic from previous statements. The examples in that section all worked with unspecified generic propositions (\(p, q,\) etc). Let us now look at how one might use the same techniques to prove a specific proposition about the mathematical world. We will prove that for all integers \(n\), if \(n\) is even then \(n^2\) is even. (Definition: an integer \(n\) is even iff \(n = 2k\) for some integer \(k\). For example, 2 is even since 2 = 2·1; 66 is even since 66 = 2·33; 0 is even since 0 = 2 · 0.)

Proof. This is a proposition of the form \(∀n(P(n) → Q(n))\) where \(P(n)\) is “\(n\) is even” and \(Q(n)\) is “\(n^2\) is even.” We need to show that \(P(n) → Q(n)\) is true for all values of \(n\). In the language of Section 1.5, we need to show that for any \(n\), \(P(n)\) logically implies \(Q(n)\); or, equivalently, that \(Q(n)\) can be logically deduced from \(P(n)\); or, equivalently, that

\(n\) is even

___________

\(∴ n2 is even\)

is in fact a valid argument for any value of \(n\):

Let \(n\) be an arbitrary integer.

1. \(n\) is even | premise |

2. if \(n\) is even,then \(n=2k\) |
definition of even |

3. \(n =2k\) for some integer\(k) | from 1, 2 (modus ponens) |

4. if \(n = 2k\) for some integer \(k\) the \(n^2 = 4k^2\) for some integer \(k\) |
basic algebra |

5. \(n^2 = 4k^2\) for some integer \(k\) | from 3,4 (modus ponens) |

6. if \(n^2 = 4k^2\) for some integer \(k\) then \(n^2 = 2(2k^2) for that \(k\) | basic algebra |

7. \(n^2 = 2(2k^2) for some integer \(k\) | from 5,6 (modus ponens) |

8. if \(n2 = 2(2k2)\) for some integer \(k\), then \(n2 = 2k′\) for some integer \(k′\) |
basic fact about integers |

9. \(n^2 = 2k'\) for some integer \(k'\) | from 7,8 (modus ponens) |

10. if \(n^2 = 2k'\) for some integer \(k'\), then \(n^2\) is even | definition of even |

11. \(n^2\) is even | from 9, 10 (modus ponens) |

(The “basic fact about integers” referred to above is that the product of integers is again an integer.) Since \(n\) could be replaced by any integer throughout this argument, we have proved the statement “if \(n\) is even then \(n^2\) is even” is true for all integers \(n\). (You might worry that the argument is only valid for even \(n\); remind yourself that \(P (n) → Q(n)\) is automatically true if \(P(n)\) is false.)

Mathematical proofs are rarely presented with this degree of detail and formality. A slightly less formal proof of our proposition might leave out the explicit implications and instances of *modus ponens* and appear as follows:

*Proof*. Let n be an arbitrary integer.

1. \(n\) is even | premise |

2. \(n = 2k\) for some integer \(k) | definition of even |

3. \(n^2 = 4k^2\) for that integer \(k\) | basic algebra |

4. \(n^2 = 2(2k^2)\) for that \(k\) | basic algebra |

5. \(n^2 =2k'\) for some integer \(k'\) | substituting \(k' = 2k^2\) |

6. \(n^2\) is even | definition of even |

Since \(n\) was an arbitrary integer, the statement is true for all integers.

A more typical proof would take the argument above and present it in prose rather than list form:

*Proof. *Let \(n\) be an arbitrary integer and assume \(n\) is even. Then \(n = 2k\) for some integer \(k\) by the definition of even, and \(n^2 = 4k^22 = 2(2k^2)\). Since the product of integers is an integer, we have \(n^2 = 2k′\) for some integer \(k′\). Therefore \(n^2\) is even. Since \(n\) was an arbitrary integer, the statement is true for all integers.

Typically, in a “formal” proof, it is this kind of (relatively) informal discussion that is given, with enough details to convince the reader that a complete, formal proof could be constructed. Of course, how many details the reader can be expected to fill in depends on the reader, and reading proofs is a skill that must be developed and practiced. Writing a proof is even more difficult. Every proof involves a creative act of discovery, in which a chain of logic that leads from assumptions to conclusion is discovered. It also involves a creative act of expression, in which that logic is presented in a clear and convincing way. There is no algorithm for producing correct, coherent proofs. There are, however, some general guidelines for discovering and writing proofs.

One of the most important pieces of advice to keep in mind is, “Use the definition.” In the world of mathematics, terms mean exactly what they are defined to mean and nothing more. Definitions allow very complex ideas to be summarized as single terms. When you are trying to prove things about those terms, you generally need to “unwind” the definitions. In our example above, we used the definition of even to write \(n = 2k\), and then we worked with that equation. When you are trying to prove something about equivalence relations in Chapter 2, you can be pretty sure that you will need to use the fact that equivalence relations, by definition, are symmetric, reflexive, and transitive. (And, of course, you’ll need to know how the term “relation” is defined in the first place! You’ll get nowhere if you work from the idea that “relations” are something like your aunt and uncle.)

More advice along the same line is to check whether you are using the assumptions of the theorem. An assumption that is made in a theorem is called an** hypothesis**. The hypotheses of the theorem state conditions whose truth will guarantee the conclusion of the theorem. To prove the theorem means to assume that the hypotheses are true, and to show, under that assumption, that the conclusion must be true. It’s likely (though not guaranteed) that you will need to use the hypotheses explicitly at some point in the proof, as we did in our example above.\(^12\) Also, you should keep in mind that any result that has already been proved is available to be used in your proof.

A proof is a logical argument, based on the rules of logic. Since there are really not all that many basic rules of logic, the same patterns keep showing up over and over. Let’s look at some of the patterns.

The most common pattern arises in the attempt to prove that something is true “for all” or “for every” or “for any” entity in a given category. In terms of logic, the statement you are trying to prove is of the form \(∀x P (x)\). In this case, the most likely way to begin the proof is by saying something like, “Let \(x\) be an arbitrary entity in the domain of discourse. We want to show that \(P(x)\).” In the rest of the proof, \(x\) refers to some unspecified but definite entity in the domain of discourse. Since \(x\) is arbitrary, proving \(P(x)\) amounts to proving \(∀xP(x)\). You only have to be careful that you don’t use any facts about \(x\) beyond what you have assumed. For example, in our proof above, we cannot make any assumptions about the integer \(n\) except that it is even; if we had made such assumptions, then the proof would have been incorrect, or at least incomplete.

Sometimes, you have to prove that an entity exists that satisfies certain stated properties. Such a proof is called an existence proof . In this case, you are attempting to prove a statement of the form \(∃x P (x)\). The way to do this is to find an example, that is, to find a specific entity a for which \(P(a)\) is true. One way to prove the statement “There is an even prime number” is to find a specific number that satisfies this description. The same statement could also be expressed “Not every prime number is odd.” This statement has the form \(¬(∀x P (x))\), which is equivalent to the statement \(∃x (¬P (x))\). An example that proves the statement \(∃x (¬P (x))\) also proves \(¬(∀x P (x))\). Such an example is called a counterexample to the statement \(∀xP(x)\): A counterexample proves that the statement \(∀x P(x)\) is false. The number 2 is a counterexample to the statement “All prime numbers are odd.” In fact, 2 is the only counterexample to this statement; many statements have multiple counterexamples.

\(^{12}\)Of course, if you set out to discover new theorems on your own, you aren’t given the hypotheses and conclusion in advance, which makes things quite a bit harder—and more interesting.

Note that we have now discussed how to prove and disprove universally quantified statements, and how to prove existentially quantified statements. How do you disprove ∃x \(P (x)\)? Recall that \(¬∃x P (x)\) is logically equivalent to \(∀x (¬P (x))\), so to disprove \(∃x P (x)\) you need to prove \(∀x (¬P (x))\).

Many statements, like that in our example above, have the logical form of an implication, \(p → q\). (More accurately, they are of the form “\(∀x (P (x) → Q(x))\)”, but as discussed above the strategy for proving such a statement is to prove \(P(x) → Q(x)\) for an arbitrary element \(x\) of the domain of discourse.) The statement might be “For all natural numbers \(n\), if \(n\) is even then \(n^2\) is even,” or “For all strings \(x\), if \(x\) is in the language \(L\) then \(x\) is generated by the grammar \(G\),” or “For all elements s, if \(s ∈ A\) then \(s ∈ B\).” Sometimes the implication is implicit rather than explicit: for example, “The sum of two rationals is rational” is really short for “For any numbers \(x\) and \(y\), if \(x\) and \(y\) are rational then \(x + y\) is rational.” A proof of such a statement often begins something like this: “Assume that \(p\). We want to show that \(q\).” In the rest of the proof, \(p\) is treated as an assumption that is known to be true. As discussed above, the logical reasoning behind this is that you are essentially proving that

\(p\)

____

\(∴q\)

is a valid argument. Another way of thinking about it is to remember that \(p → q\) is automatically true in the case where \(p\) is false, so there is no need to handle that case explicitly. In the remaining case, when \(p\) is true, we can show that \(p → q\) is true by showing that the truth of \(q\) follows from the truth of \(p\).

A statement of the form p ∧ q can be proven by proving p and q sepa- rately. A statement of the form p∨q can be proved by proving the logically equivalent statement (¬p) → q: to prove p ∨ q, you can assume that pis false and prove, under that assumption, that q is true. For example, the statement “Every integer is either even or odd” is equivalent to the statement “Every integer that is not even is odd.”

Since \(p ↔ q\) is equivalent to \((p → q)∧(q → p)\), a statement of the form \(p ↔ q\) is often proved by giving two proofs, one of \(p → q\) and one of \(q → p\). In English, \(p ↔ q\) can be stated in several forms such as “\(p\) if and only if \(q\)”, “if \(p\) then \(q\) and conversely,” and “\(p\) is necessary and sufficient for \(q\).” The phrase “if and only if” is so common in mathematics that it is often abbreviated **iff**.

You should also keep in mind that you can prove \(p → q\) by displaying a chain of valid implications \(p→r→s→···→q\). Similarly, \(p↔q\) can be proved with a chain of valid biconditionals \(p ↔ r ↔ s ↔ ··· ↔ q\).

We’ll turn to a few examples, but first here is some terminology that we will use throughout our sample proofs:

- The
**natural numbers**(denoted \(mathbb{N}\) are the numbers 0, 1, 2, . . .. Note that the sum and product of natural numbers are natural numbers. - The
**integers**(denoted \(mathbb{Z}\) are the numbers 0,−1,1,−2,2,−3,3,.... Note that the sum, product, and difference of integers are integers. - The
**rational numbers**(denoted \(mathbb{Q}\) are all numbers that can be written in the form \(\frac{m}{n}\) where \(m\) and \(n\) are integers and \(n \ne 0\). So \(\frac{1}{3}\) and \(\frac{-65}{7}\) are rationals; so, less obviously, are 6 and \(\frac{\sqrt{27}}{\sqrt{12}}\) since 6 = \(\frac{6}{1}\) (or, for that matter, 6 = \(\frac{-12}{-2}\)), and \(\frac{\sqrt{27}}{\sqrt{12}}\) = \(\sqrt{\frac{27}{12}}\) = \(\sqrt{\frac{9}{4}}\) = \(\frac{3}{2}\). Note the restriction that the number in the denominator cannot be 0: \(\frac{3}{0}\) is not a number at all, rational or otherwise; it is an undefined quantity. Note also that the sum, product, difference, and quotient of rational numbers (provided you don't attempt to divide by 0.) - The
**real numbers**(denoted \(\mathbb{R}\)) are numbers that can be written in decimal form, possibly with an infinite number of digits after the decimal point. Note that the sum, product, difference, and quotient of real numbers are real numbers (provided you don’t attempt to divide by 0.) - The
**irrational numbers**are real numbers that are not rational, i.e. that cannot be written as a ratio of integers. Such numbers include \(\sqrt{3}\) (which we will prove is not rational) and \(π\) (if anyone ever told you that \(π = \frac{22}{7}\) , they lied— \(\frac{22}{7}\) is only an approximation of the value of \(π\)). - An integer \(n\) is
**divisible by**\(m\) iff \(n = mk\) for some integer \(k\). (This can also be expressed by saying that \(m\) evenly divides \(n\).) So for example, \(n\) is divisible by \(2\) iff \(n = 2k\) for some integer \(k\); \(n\) is divisible by 3 iff \(n = 3k\) for some integer \(k\), and so on. Note that if \(n\) is \(not\) divisible by 2, then \(n\) must be 1 more than s multiple of 2 so \(n = 2k +1\) for some integer \(k\). Similarly, if \(n\) is not divisible by 3 then \(n\) must be 1 or 2 more than a multiple of 3, so \(n = 2k+1\) or \(n=2k+2\) for some integer k. - An integer is
**even**iff it is divisible by 2 and**odd**iff it is not. - An integer n > 1 is
**prime**if it is divisible by exactly two positive integers, namely 1 and itself. Note that a number must be greater than 1 to even have a chance of being termed “prime”. In particular, neither 0 nor 1 is prime.

Let’s look now at another example: prove that the sum of any two rational numbers is rational.

**Proof**. We start by assuming that x and y are arbitrary rational numbers. Here’s a formal proof that the inference rule

\(x\) is rational

\(y\) is rational

_______________

\(∴ x+y\) is rational

is a valid rule of inference:

1. \(x\) is rational | premise |

2. if \(x\) is rational, then x = \(\frac{a}{b}\) for some integers \(a\) and \(b \ne 0\) | definiton of rationals |

3. \(x = \frac{a}{b}\) for some integers \(a\) and \(b \ne 0\) | from 1,2 (modus ponens) |

4. \(y\) is rational | premise |

5. if \(y\) is rational, then y = \(\frac = {c}{d}\) for some integers \(c\) and \(d \ne \) | definition of rational |

6. \(y = \frac{c}{d}\) for some \(c\) and \(d \ne 0\) | from 4,5 (modus ponens) |

7. \(x = \frac{a}{b}\) for some \(a\) and \(b \ne 0\) and \(y = \frac{c}{d}\) for \(c\) and \(d \ne 0\) | from 3,6 |

8. if \(x = \frac{a}{b} for some \(a\) and \(b \ne 0\) and \(y = \frac{c}{d}\) for \(c\) and \(d \ne 0\)then \(x +y = \frac{ad+bc}{bd}\) where \(a, b, c, d\) are integers and \(b, d \neg 0\) | basic algebra |

9. \(x +y = \frac{ad+bc}{bd}\) for some \(a, b, c, d\) where \(b,d \neg 0\) | from 7,8 ( modus ponens) |

10. if \(x + y = \frac{ad +bc}{bd}\) for some \(a,b,c,d\) where \(b,d \ne 0\) then \(x+y = \frac{m}{n} where \(m,n\) are integers and \(n \ne 0\) | properties of integers |

11. \(x +y = \frac{m}{n}\) where \(m\) and \(n\) are integers and \(n \ne 0\) | from 9,10 ( modus ponens) |

12. if \(x +y = \frac{m}{n}\) where \(m\) and \(n\) are integers and \(n \ne 0\) then \(x + y\) is rational | definition of rational |

13. \(x+y\) is rational | from 11,12 (modus ponens) |

So the rule of inference given above is valid. Since \(x\) and \(y\) are arbitrary rationals, we have proved that the rule is valid for all rationals, and hence the sum of any two rationals is rational.

Again, a more informal presentation would look like:

Proof. Let x and y be arbitrary rational numbers. By the definition of rational, there are integers \(a,b \ne 0\), \(c,d \ne 0\) such that \(x = \frac{a}{b}\) and \(y = \frac{c}{d}\). Then \(x+y = \frac{ad+bc}{bd}\) ; we know \(ad+bc\) and \(bd\) are integers since the sum and product of integers are integers, and we also know \(bd \ne 0\) since neither \(b\) nor \(d\) is 0. So we have written \(x+y\) as the ratio of two integers, the denominator being non-zero. Therefore, by the definition of rational numbers, \(x + y\) is rational. Since \(x\) and \(y\) were arbitrary rationals, the sum of any two rationals is rational.

And one more example: we will prove that any 4-digit number \(d_{1} d_{2} d_{3} d_{4}\) is divisible by 3 iff the sum of the four digits is divisible by 3.

**Proof. **This statement is of the form \(p ↔ q\); recall that \(p ↔ q\) is logically equivalent to \((p → q) ∧ (q → p)\). So we need to prove for any 4-digit number \(d_{1} d_{2} d_{3} d_{4}\) that (1) if \(d_{1} d_{2} d_{3} d_{4}\) is divisible by 3 then \(d_{1} +d_{2} +d_{3} +d_4\) is divisible by 3, and (2) if \(d_{1} +d_{2} +d_{3} +d_4\) is divisible by 3 then \(d_{1} d_{2} d_{3} d_{4}\) is divisible by 3. So let \(d_{1} d_{2} d_{3} d_{4}\) be an arbitrary 4-digit number.

(1) Assume \(d_{1} d_{2} d_{3} d_{4}\) is divisible by 3, i.e. \(d_{1} d_{2} d_{3} d_{4}\) = 3k for some integer k. The number \(d_{1} d_{2} d_{3} d_{4}\) is actually \(d_{1}×1000+d_{2}×100+d_{3}×10+d_{4}\), so we have the equation

\[d_{1} ×1000+d_{2} ×100+d_{3} ×10+d_{4} =3k.\]

Since 1000 = 999+1, 100 = 99+1, and 10 = 9+1, this equation can be rewritten

\[999d_{1} +d_{1} +99d_{2} +d_{2} +9d_{3} +d_{3} +d_{4} =3k.\]

Rearranging gives

\[d_{1} +d_{2} +d_{3} +d_{4} =3k−999d_{1} −99d_{2} −9d_{3} = 3k − 3(333d_{1}) − 3(33d_{2}) − 3(3d_{3})\]

We can now factor a 3 from the right side to get

\[d1 +d2 +d3 +d4 =3(k−333d_{1} −33d_{2} −d_{3}).\]

Since (k−333d_{1}−33d_{2}−d_{3}) is an integer, we have shown that \(d_{1}+d_{2}+d_{3}+d_{4}\) is divisible by 3.

(2) Assume \(d_{1} + d_{2} + d_{3} + d_{4} is divisible by 3. Consider the number \(d_{1} d_{2} d_{3} d_{4}\). As remarked above,

\[\(d_{1} d_{2} d_{3} d_{4}\) = d_{1} ×1000+d_{2} ×100+d_{3} ×10+d_{4}\)\]

so

\[d_{1}d_{2}d_{3}d_{4} = 999d_{1} +d_{1} +99d_{2} +d_{2} +9d_{3} +d_{3} +d_{4} = 999d_{1} +99d_{2} +9d_{3} +(d_{1} +d_{2} +d_{3} +d_{4})\]

We assumed that \(d_{1} +d_{2} +d_{3} +d_{4} =3k\) for some integer \(k\), so we can substitute into the last equation to get

\[d_{1} d_{2} d_{3} d_{4} = 9999d_{1}+99d_{2} +9d_{3} +3k=3(333d_{1} +33d_{2} +3d_{3} +k).\]

Since the quantity in parentheses is an integer, we have proved that \(d_{1}d_{2}d_{3}d_{4}\) is divisible by 3.

In (1) and (2) above, the number \(d_{1}d_{2}d_{3}d_{4}\) was an arbitrary 4-digit integer, so we have proved that for all 4-digit integers, \(d_{1}d_{2}d_{3}d_{4}\) is divisible by 3 iff the sum of the four digits is divisible by 3.

Now suppose we wanted to prove the statement “For all integers \(n\), \(n^2\) is even if and only if \(n\) is even.” We have already proved half of this statement (“For all integers \(n\), if \(n\) is even then \(n^2\) is even”), so all we need to do is prove the statement “For all integers \(n\), if \(n^2\) is even then \(n\) is even” and we’ll be done. Unfortunately, this is not as straightforward as it seems: suppose we started in our standard manner and let \(n\) be an arbitrary integer and assumed that \(n^2 = 2k\) for some integer \(k\). Then we’d be stuck! Taking the square root of both sides would give us n on the left but would leave a \(\sqrt{2k}\) on the right. This quantity is not of the form \(2k′\) for any integer \(k′\); multiplying it by \(\frac{\sqrt{2}}{\sqrt{2}}\) would give \(2\frac{\sqrt{k}}{\sqrt{2}}\) but there is no way for us to prove that \(\frac{\sqrt{k}}{\sqrt{2}}\) is an integer. So we've hit a dead end. What do we do now?

The answer is that we need a different proof technique. The proofs we have written so far are what are called direct proofs: to prove \(p → q\) you assume \(p\) is true and prove that the truth of \(q\) follows. Sometimes, when a direct proof of \(p → q\) fails, an indirect proof will work. Recall that the contrapositive of the implication \(p → q\) is the implication \(¬q → ¬p\), and that this proposition is logically equivalent to \(p → q\). An indirect proof of \(p → q\), then, is a direct proof of the contrapositive \(¬q → ¬p\). In our current example, instead of proving “if \(n^2\) is even then \(n\) is even” directly, we can prove its contrapositive “if \(n\) is not even (i.e. n is odd) then \(n^2\) is not even (i.e. \(n^2\) is odd.)” The proof of this contrapositive is a routine direct argument which we leave to the exercises.

## Exercises

- Find a natural number \(n\) for which \(n^2 + n + 41\) is not prime.
- Show that the propositions \(p ∨ q\) and \((¬p) → q\) are logically equivalent.
- Show that the proposition \((p∨q) → r\) is equivalent to \((p → r)∧(q → r)\).
- Determine whether each of the following statements is true. If it true, prove it. If it is false, give a counterexample.

**a)**Every prime number is odd

**b)**Every prime number greater than 2 is odd

**c)**If \(x\) and \(y\) are integers with \(x < y\), then there is an integer \(z\) such that \(x < z < y\).

**d)**If \(x\) and \(y\) are real numbers with \(x < y\), then there is a real number \(z\) such that \(x < z < y\). - Suppose that \(r, s\), and \(t\) are integers, such that \(r\) evenly divides \(s\) and \(s\) evenly divides \(t\). Prove that \(r\) evenly divides \(t\).
- Prove that for all integers \(n\), if \(n\) is odd then \(n^2\) is odd.
- Prove that an integer \(n\) is divisible by 3 iff \(n^2\) is divisible by 3. (Hint: give an indirect proof of “if \(n^2\) is divisible by 3 then \(n\) is divisible by 3.”)
- Prove or disprove each of the following statements.

a) The product of two even integers is even.

b) The product of two integers is even only if both integers are even.

c) The product of two rational numbers is rational.

d) The product of two irrational numbers is irrational.

e) For all integers \(n\), if \(n\) is divisible by 4 then \(n^2\) is divisible by 4.

f) For all integers \(n\), if \(n^2\) is divisible by 4 then \(n\) is divisible by 4.