Proofwriting Checklist

Mathematical proofs have their own writing conventions. Over the quarter, you will internalize those conventions and learn to write like a theoretician.

The conventions used in mathematical proofs can generally be broken down into two areas. The first are rules on structure and writing style, which give rise to the charactistic language used in proofs. The second are rules that may initially appear stylistic, but which hit at deeper aspects of mathematical reasoning. Learning to write naturally while adhering to these rules thus ensures your writing will conform with mathematical writing expectations and, in many cases, automatically eliminate entire classes of mathematical errors.

We have distilled many aspects of mathematical proofwriting into seven specific items that we will look for when reading (and grading) your proofs. They are as follows:

We will apply this checklist to the proofs that you submit. We recommend you work through this checklist on every proof that you write. Doing so will help you improve your proofwriting and smoke out some underlying logic errors.

The remainder of this guide goes into more detail about what each of these rules mean.

Clearly Articulate Your Assumptions and “Want-to-Shows.”

A proof lays out an argument explaining why some conclusion must be true given a set of starting assumptions. Therefore, most proofs will have the following general structure:

1. Introduce a set of starting assumptions, often introducing some variables in the process.
2. Articulate the overall goal of the proof.
3. Give some line of reasoning that reaches the goal.
4. State you've reached the goal and end the proof.

We refer to part (1) of the proof as the assumptions and part (2) of the proof as the "want-to-show". When you are first learning to write proofs, it is important to explicitly include both of these steps in your proof, with exceptions noted below.

Direct Proofs

In a direct proof, the proof should begin with the assumptions, want-to-show, and conclusion. For example:

Here, our assumptions are that the reader has chosen an odd integer $m$ and an even integer $n\text,$ and our want-to-show is that $mn$ is even. Note that the proof does not explicitly use the terms "assume" or "want-to-show," but still achieves the same result. The proof must end with the statement that $mn$ is even, since that is what we explicitly stated we would prove in our want-to-show.

Proof by Contrapositive

A proof by contrapositive will also include an assumption and want-to-show, which will follow the statement of the contrapositive of the implication. Here is an example:

Note that the proof still ends by saying that we have proved what we set out to prove in our want-to-show.

Proof by Contradiction

A proof by contradiction is different from the other proofwriting styles in that it always includes an assumption, but never includes a want-to-show. It is implicit in a proof by contradiction that the want-to-show is "a contradiction," so it's left out of the proof. Proofs by contradiction are also unusual in that the conclusion of the proof explains what the contradiction shows, which is often the theorem itself.

For example:

Existential Statements

Sometimes, the statement you want to prove is a simple existentially-quantified statement with no universally-quantified parts. For example, you might want to prove that 56 is the sum of four cubes, or that 137 is the sum of two squares. In those cases, you will typically not have anything to assume, and your want-to-show will just be the statement of the theorem itself. In those cases, it's customary to not include an assume or want-to-show statement, since the "assume" bit would have nothing in it and the "Want to show" would be redundant.

Exercises

These exercises are purely optional but will help reinforce the concepts covered in this point.

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $m$ and $n\text,$ if $m$ is even and $n$ is even, then $m + n$ is even.

   Proof: Since $m$ is even and $n$ is even, we know there are integers $r$ and $s$ where $m = 2r$ and $n = 2s\text.$ This means that $m + n = 2r + 2s = 2(r + s)\text.$ Therefore, there is an integer $t$ (namely, $r + s\text)$ such that $m + n = 2t\text,$ so $m + n$ is even. $\qed$

   Solution

   This proof does not adhere to our style conventions. Specifically, it does not include an assume statement, nor does it include a want-to-show. Here is a better version of the proof:

   Theorem: For all integers $m$ and $n\text,$ if $m$ is even and $n$ is even, then $m + n$ is even.

   Proof: Let $m$ and $n$ be arbitrary even integers. We will show that $m+n$ is even.

   Since $m$ is even and $n$ is even, we know there are integers $r$ and $s$ where $m = 2r$ and $n = 2s\text.$ This means that $m + n = 2r + 2s = 2(r + s)\text.$ Therefore, there is an integer $t$ (namely, $r + s\text)$ such that $m + n = 2t\text,$ so $m + n$ is even, as required. $\qed$

   Note that we explicitly introduce $m$ and $n$ here, state that we are going to prove that $m + n$ is even, and conclude once we have arrived at the statement that $m + n$ is even.

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $n\text,$ if $n$ is even, then there exist even integers $r$ and $s$ where $r + s = n^2\text.$

   Proof: Let $n$ be an even integer. Since $n$ is even, as proved in lecture we know that $n^2$ is even. Now let $r = n^2$ and $s = 0\text.$ We know that $r$ is even because $n^2$ is even. We see that $s$ is even because $s = 0 = 2 \cdot 0\text.$ Moreover, $r + s = n^2 + 0 = n^2\text,$ as required. $\qed$

   Solution

   This proof does not adhere to our style conventions. It does include an assume statement, but it does not have a want-to-show. Here is a better way to write this proof:

   Theorem: For all integers $n\text,$ if $n$ is even, then there exist even integers $r$ and $s$ where $r + s = n^2\text.$

   Proof: Let $n$ be an even integer. We need to show that there are even integers $r$ and $s$ where $r + s = n^2\text.$

   Since $n$ is even, as proved in lecture we know that $n^2$ is even. Now let $r = n^2$ and $s = 0\text.$ We know that $r$ is even because $n^2$ is even. We see that $s$ is even because $s = 0 = 2 \cdot 0\text.$ Moreover, $r + s = n^2 + 0 = n^2\text,$ as required. $\qed$

   ---

3. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does. (For reference: an integer $n$ is a multiple of three if there is an integer $k$ where $n = 3k\text{.)}$

   Theorem: For all integers $n\text,$ if $n$ is a multiple of three, then $n^2$ is a multiple of three.

   Proof: Choose any $n$ that is a multiple of three. We need to show that $n^2$ is a multiple of three.

   Since $n$ is a multiple of three, we know there is an integer $k$ where $n = 3k\text.$ We then see that

   \[\begin{aligned} n^2 &= (3k)^2 \\ &= 9k^2 \\ &= 3(3k^2)\text, \end{aligned}\]

   so there is an integer $m\text,$ namely $3k^2\text,$ such that $n^2 = 3m\text.$ This means that $n^2$ is a multiple of three. Therefore, for all integers $n\text,$ if $n$ is a multiple of three, then so is $n^2\text.$ $\qed$

   Solution

   This proof does not adhere to our style conventions. It does include an assume statement and has an accompanying want-to-show. However, the proof does not conclude as soon as it has proved the want-to-show. Specifically, the want-to-show is that $n^2$ is a multiple of three, so as soon as we reach that point, we should stop. This proof, on the other hand, continues onward to explain why this means that the full theorem is true, which is unnecessary. One of the main reasons for having a want-to-show is to have a well-defined endpoint for the proof, after which the reader knows that you have done everything you set out to do.

   Here is a better way to write this proof:

   Theorem: For all integers $n\text,$ if $n$ is a multiple of three, then $n^2$ is a multiple of three.

   Proof: Choose any $n$ that is a multiple of three. We need to show that $n^2$ is a multiple of three.

   Since $n$ is a multiple of three, we know there is an integer $k$ where $n = 3k\text.$ We then see that

   \[\begin{aligned} n^2 &= (3k)^2 \\ &= 9k^2 \\ &= 3(3k^2)\text, \end{aligned}\]

   so there is an integer $m\text,$ namely $3k^2\text,$ such that $n^2 = 3m\text.$ This means that $n^2$ is a multiple of three, as required. $\qed$

   Notice that this proof is shorter than the previous one.

   ---

4. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $m$ and $n\text,$ if $m + n$ is odd, then so is $m - n\text.$

   Proof: We will prove the contrapositive, namely, that if $m - n$ is even, then $m + n$ is even as well.

   Since $m - n$ is even, there is an integer $k$ where $m - n = 2k\text.$ This means that

   \[\begin{aligned} m + n &= m - n + 2n \\ &= 2k + 2n \\ &= 2(k + n)\text, \end{aligned}\]

   so there is an integer $s$ (namely, $m + n\text)$ such that $m + n = 2s\text,$ so $m + n$ is even. $\qed$

   Solution

   This proof does not adhere to our style conventions. It begins (correctly) by stating the contrapositive of the implication, but then does not take that a step further by explicitly listing the assume and want-to-show steps for the proof. Here is a better way to write this:

   Theorem: For all integers $m$ and $n\text,$ if $m + n$ is odd, then so is $m - n\text.$

   Proof: We will prove the contrapositive, namely, that if $m - n$ is even, then $m + n$ is even as well. So pick some integers $m$ and $n$ where $m - n$ is even; we will show that $m + n$ is even.

   Since $m - n$ is even, there is an integer $k$ where $m - n = 2k\text.$ This means that

   \[\begin{aligned} m + n &= m - n + 2n \\ &= 2k + 2n \\ &= 2(k + n)\text, \end{aligned}\]

   so there is an integer $s$ (namely, $m + n\text)$ such that $m + n = 2s\text,$ so $m + n$ is even. $\qed$

   Although this is written as a proof by contrapositive, there is no deep reason it needs to be. This could easily be structured as a direct proof if we wanted to. However, it's not wrong to prove this by contrapositive.

   ---

5. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $m$ and $n\text,$ if $mn + 1$ is even, then $m$ is odd or $n$ is odd.

   Proof: Assume for the sake of contradiction that there are integers $m$ and $n$ where $mn + 1$ is even but $m$ is even and $n$ is even. We will show that this results in a contradiction.

   Since $m$ and $n$ are even, there are integers $r$ and $s$ where $m = 2r$ and $n = 2s\text.$ This means that

   \[\begin{aligned} mn + 1 &= (2r)(2s) + 1 \\ &= 2(2rs) + 1\text, \end{aligned}\]

   which means there's an integer $t$ (namely, $2rs\text)$ where $mn + 1 = 2t + 1\text.$ Thus $mn + 1$ is odd, which is impossible because we know that $mn + 1$ is even.

   We've reached a contradiction, so our assumption was wrong and if $mn + 1$ is even, then $m$ is odd or $n$ is odd. $\qed$

   Solution

   This proof does not adhere to our style conventions. It includes both an assume and want-to-show statement, which is normally correct, but in the context of a proof by contradiction we don't include the want-to-show. Here's a better way to write the proof:

   Theorem: For all integers $m$ and $n\text,$ if $mn + 1$ is even, then $m$ is odd or $n$ is odd.

   Proof: Assume for the sake of contradiction that there are integers $m$ and $n$ where $mn + 1$ is even but $m$ is even and $n$ is even.

   Since $m$ and $n$ are even, there are integers $r$ and $s$ where $m = 2r$ and $n = 2s\text.$ This means that

   \[\begin{aligned} mn + 1 &= (2r)(2s) + 1 \\ &= 2(2rs) + 1\text, \end{aligned}\]

   which means there's an integer $t$ (namely, $2rs\text)$ where $mn + 1 = 2t + 1\text.$ Thus $mn + 1$ is odd, which is impossible because we know that $mn + 1$ is even.

   We've reached a contradiction, so our assumption was wrong and if $mn + 1$ is even, then $m$ is odd or $n$ is odd. $\qed$

   Although this is written as a proof by contrapositive, there is no deep reason it needs to be. This could easily be structured as a direct proof if we wanted to. However, it's not wrong to prove this by contrapositive.

   ---

6. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: There is a natural number $n$ where $n^2 + 56 = 60\text.$

   Proof: Pick $n = 2\text.$ We then see that $n^2 + 56 = 2^2 + 56 = 60\text,$ as required. $\qed$

   Solution

   Yes, this adheres to our standards. Although there is no assume or want-to-show statement, that is correct because this is a purely existentially-quantified statement. We don't need to assume anything, and since the goal is to prove a number $n$ exists with some properties, we can just give a choice of $n$ that works.

   ---

Make Each Sentence Load-Bearing

When you’re writing a proof, you are trying to convey a mathematical argument, and each step in what you write should advance your argument. As a general rule, every statement in a proof should do one of the following things:

• Set up a goal. As mentioned in the preceding pages, your proof should start off with an introduction that clearly articulates a start and end point. In larger proofs, you might find yourself needing to prove an auxiliary result that you’ll use to build up to the larger result, and when you do that, you’ll similarly want to set up what it is that you’re trying to prove.

• Introduce a new variable. Sometimes, in the course of a proof, you’ll need to introduce new variables. If you’re proving something universally-quantified, you might want to say something like “let $x$ be an arbitrary bananafish,” and if you’re proving something existentially-quantified you might want to say something like “since $n$ is even, we know there is an integer $k$ such that $n = 2k$.”

• Combine preceding results into something new. Any sentence that doesn’t set up a new goal or introduce a new variable should make progress toward the result by taking some number of preceding statements and deriving some new, mathematically rigorous result from those preceding statements. For example, you might say something like “since $n = 2k$, we see that $n^2 = 2(2k)^2$” or “since $A \subseteq B$ and $x \in A$, we learn that $x \in B$.”

If you find yourself reading over a sentence that doesn’t accomplish any of these goals, it is likely unnecessary and should be eliminated. This is a great way to reduce the size of your proofs and to make sure that you’re being rigorous. Similarly, if you find yourself doing any of these three things in a way that does not make an appearance later in the proof, it likely means it is unnecessary and that you should remove it. This will make your proof easier to read.

This is a particularly useful check to apply to a proof after you’ve first finished a first draft. Often, in the course of solving a problem and writing up a first proof draft, you’ll go in a direction that ultimately ends up not being necessary, or write out some high-level lines of reasoning that you then make more rigorous later on.

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: There are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}$ and $m$ is odd.

   Proof: Suppose for the sake of contradiction that $m$ and $n$ are natural numbers where $\frac{m}{2^n} = \frac{1}{137}$ and where $m$ is odd. The fraction $\frac{m}{2^n}$ does not necessarily have to be in simplest form. We do know that $\frac{1}{137}$ is in simplest form, though. Cross-multiplying the previous equality gives us that $137m = 2^n\text.$

   • Case 1: $n = 0\text.$ Then $2^n = 2^0 = 1\text,$ which is odd. Since $2^n = 137m\text,$ we see that $1 = 137m\text,$ which we rearrange to $m = \frac{1}{137}\text.$ This is impossible because $m$ is a natural number and $\frac{1}{137}$ is not.

   • Case 2: $n \ge 1\text.$ Then we can write $n = r + 1$ for some natural number $r\text,$ and we see that $2^n = 2^{r+1} = 2 \cdot 2^r\text.$ This means that $2^n$ is even. It would not be even if $n = 0\text,$ though. However, $2^n = 137m$ and $137m$ is odd, since $m$ is odd and $137 = 2 \cdot 68 + 1$ is odd. This means that $2^n$ is both odd and even, which is impossible.

   In either case, we reach a contradiction, so our assumption was wrong. Thus there are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}\text{. } \qed$

   Solution

   This proof does not adhere to our style conventions. There are several statements in this proof that are true but not used anywhere:

   • "The fraction $\frac{m}{2^n}$ does not necessarily have to be in simplest form." True, but not referenced anywhere in the proof.
   • "We do know that $\frac{1}{137}$ is in simplest form, though." True, but not referenced anywhere in the proof.
   • "Then $2^n = 2^0 = 1\text,$ which is odd." We do use the fact that $2^n = 2^0 = 1$ in the next sentence, but the fact that $1$ is odd is not needed anywhere.

   There is one other sentence that is not needed, but for a different reason:

   • "It would not be even if $n = 0\text,$ though." This statement is true, but it's unnecessary. Because we are in Case 2, where we assume $n \ge 1\text,$ we already know that $n \ne 0\text,$ and so statements about what would happen if $n = 0$ aren't needed here. If it needs to be brought up at all, it can be brought up in Case 1 where $n = 0\text.$ Second, the fact that a statement would not be true in some other circumstance is not relevant to the argument.

   After removing those statements, we're left with this slimmer, easier-to-read proof:

   Theorem: There are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}$ and $m$ is odd.

   Proof: Suppose for the sake of contradiction that $m$ and $n$ are natural numbers where $\frac{m}{2^n} = \frac{1}{137}$ and where $m$ is odd. Cross-multiplying the previous equality gives us that $137m = 2^n\text.$

   • Case 1: $n = 0\text.$ Then we see that $2^n = 2^0 = 1\text.$ Since $2^n = 137m\text,$ we see that $1 = 137m\text,$ which we rearrange to $m = \frac{1}{137}\text.$ This is impossible because $m$ is a natural number and $\frac{1}{137}$ is not.

   • Case 2: $n \ge 1\text.$ Then we can write $n = r + 1$ for some natural number $r\text,$ and we see that $2^n = 2^{r+1} = 2 \cdot 2^r\text.$ This means that $2^n$ is even. However, $2^n = 137m$ and $137m$ is odd, since $m$ is odd and $137 = 2 \cdot 68 + 1$ is odd. This means that $2^n$ is both odd and even, which is impossible.

   In either case, we reach a contradiction, so our assumption was wrong. Thus there are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}\text{. } \qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $m$ and $n\text,$ if $m$ is even and $n$ is even, then $m^2 + n^2$ is even.

   Proof: Choose any even integers $m$ and $n\text.$ We need to show that $m^2 + n^2$ is even.

   Since $m$ and $n$ are even, we know there are integers $r$ and $s$ where $m = 2r$ and $n = 2s\text.$ Similarly, since $m$ and $n$ are even, as proved in lecture, we know that $m^2$ and $n^2$ are even. This means that there are integers $j$ and $k$ where $m^2 = 2j$ and $n^2 = 2k\text.$ We then see that $m^2 + n^2 = 2j + 2k = 2(j + k\text{),}$ so letting $t = j + k$ we see that $m^2 + n^2 = 2t\text.$ This means that $m^2 + n^2$ is even, as required. $\qed$

   Solution

   This proof does not adhere to our style conventions. Although it's true that $m$ and $n$ are even and thus can be written as $m = 2r$ and $n = 2s$ for integers $r$ and $s\text,$ we never make use of this fact later in the proof. Those statements should be removed from the proof, reducing in a slimmer proof that includes only relevant details. Here's what this looks like:

   Theorem: For all integers $m$ and $n\text,$ if $m$ is even and $n$ is even, then $m^2 + n^2$ is even.

   Proof: Choose any even integers $m$ and $n\text.$ We need to show that $m^2 + n^2$ is even.

   Since $m$ and $n$ are even, as proved in lecture, we know that $m^2$ and $n^2$ are even. This means that there are integers $j$ and $k$ where $m^2 = 2j$ and $n^2 = 2k\text.$ We then see that $m^2 + n^2 = 2j + 2k = 2(j + k\text{),}$ so letting $t = j + k$ we see that $m^2 + n^2 = 2t\text.$ This means that $m^2 + n^2$ is even, as required. $\qed$

   ---

Scope and Properly Introduce Variables

In programming languages like C, C++, and Java, you’re required to declare variables before you use them. The type of the variable lets the compiler know what sorts of values the variable can hold. If you try to use a variable you haven’t declared, or if you try to treat a variable of one type as though it had a different type, you get a compiler error.

Variables in mathematical proofs obey similar conventions. When writing proofs, it’s important that you clearly articulate what each variable stands for and, additionally, where it comes from. When you use a variable in a proof, you should explicitly articulate

• the name of the variable,
• what value it represents, and
• where it comes from.

Those last two points are critical in writing proofs. Every variable that you use should be of one of the following types:

• A universally-instantiated value. A variable like this has a value that the reader of the proof chooses, but which you as the proof writer don't get to control. Variables like these often arise in the context of proving universally-quantified statements. For example, if you want to prove the claim “for any natural number $n$, if $n$ is even, then $n^2$ is even,” you might introduce a variable n like this:

  Pick an even natural number $n$.

  Let $n$ be an arbitrary even natural number.

  Consider an even natural number $n$.

  Let $n$ be an even natural number.

  Here, we’re indicating that the variable is named $n$, its value is some even natural number, and that the reader, not the writer, picks the value. This is called a universally-instantiated variable because in principle it could have any value.

• An existentially instantiated value. Sometimes, you and the reader each know that some quantity exists, but you don't know its exact value. For example, if you know that $n$ is an even natural number, you know that $n$ must be twice some other natural number, and so you might give it a name, as shown here:

  Since $n$ is even, there is some integer $k$ such that $n = 2k$.

  It’s important to note that this number $k$ is not chosen arbitrarily. That would imply that any choice of $k$ would work here, but that’s not true: there’s only one choice of $k$ you can pick where $n = 2k$. Rather, $k$ is called an existentially instantiated variable, because we know that there exists some value with some property and we’re introducing the variable $k$ as a way of saying what that value is.

• An explicitly chosen value. Sometimes, you’ll introduce a variable simply as a simpler way of referring to some other quantity. For example, we might say something like this:

  Let $m = 2k^2\text.$

  Or, we could say something like this:

  Consider the set $D = \Set{ x \in S \ \vert \ x \notin f(x) }$.

  Here, we’re just giving a name to an existing quantity, which functions like a constant in a language like C, C++, or Java.

When writing or reviewing a proof, make sure you can clearly tell whether which of these three sorts of values that variable has. Just like variables in C, C++, or Java, this helps you indicate what your variables mean, what they store, and where they’re coming from.

You might find it helpful to view a proof as a dialog between two people. The first is you, the writer of the proof, and the second is whoever is reading the proof. Whenever you introduce a variable, it will be one of three types:

• A variable whose value the reader picks. For example, if you say something like “pick a natural number $n$” or “consider an arbitrary set $A$,” then you are telling the reader “hey reader, you can choose whatever value you’d like for this variable.”

• A variable whose value you pick. For example, if you say something like “let $r = k+1$,” then you are telling the reader “hey reader, you do not have a choice here. I have selected the value $k+1$ for $r$.”

• A variable whose value neither of you pick. For example, suppose you say something like “since $n$ is even, there is an integer $k$ such that $n = 2k$.” Here, you and the reader both agree that there is some choice of $k$ that works here, and you’re agreeing that the value of $k$ will be selected to meet that requirement. However, you yourself didn’t say “I want you to pick this value as $k$,” nor did you tell the reader “please pick a value of $k$ for me.”

To see how these rules come into play, let’s look at one possible proof of this result:

Theorem: For any integer $n\text,$ if $n$ is even, then $n^2$ is even.

Here’s a not-so-great proof of this result:

Let’s focus on a few of sentences. For starters, let’s look at this sentence from the first paragraph:

The intent here is clear: we're trying to prove something about all integers $n\text,$ so the proof talks about "every even integer $n\text.$" However, this is not the correct way to do this. Specifically, this way of discussing $n$ means $n$ does not fall into any of the three aforementioned categories:

• It's not universally-instantiated: we haven't asked the reader to choose $n\text,$ nor have we said something like "let $n$ be an even integer."

• It's not existentially-instantiated: there is no value the reader and writer agree exists that we are just giving a new name to.

• It's not a specifically-chosen value: we are not giving a new name to an existing quantity.

If, in the course of writing a proof, you wish to make a claim that works for all choices of some value, the correct way to do it is to ask the reader to make the choice and then show the result works regardless of what that choice is. That's not done by saying "for every even integer $n\text,$" but by saying something like "let $n$ be an even integer" or "pick some even integer $n\text.$"

Let's continue onward in this proof. In the next sentence, we see the following:

There are two issues here. The first is a repeat of the same error from earlier: we should not be talking about "any even integer $n\text,$" but instead ask the reader to choose some value for $n$ that we then use throughout the proof. The second is how we talk about $k\text.$ As before, we should not say "for any integer $k\text.$" That's generally not a good idea. More importantly, though, this is the wrong way to introduce $k\text.$ In this proof, $k$ should be existentially-introduced: we know $n$ is even, so some integer $k$ exists where $n = 2k\text.$ The value of $k$ is not something that we the proof writer get to pick: we can't choose $k$ to be whatever we want to be, since only one choice of $k$ will make $n = 2k\text.$ We therefore should not be talking about "for all integers $k$."

Let's continue on in the sentence:

Here, we've reached the point where we know $n^2 = 2(2k^2)\text.$ If we specifically pick $m = 2k^2\text,$ then we can get some result. But the way we do that here is incorrect. Writing "for any arbitrary integer $m$ where $m = 2k^2$" makes the same mistakes as before: avoid talking about "for any arbitrary integer $m$", and this doesn't work for every integer $m$ but only the specific choice of $m = 2k^2\text.$ It's like the famous quote attributed to Henry Ford: "the customer can have any color they want as long as it's black."

The last sentence of this proof makes the same mistake:

We shouldn't be talking about "any even integer $n$" and should have, much earlier in the proof, asked the reader to choose $n$ for us. Similarly, it's not the case that $n^2 = 2m$ for every integer $m\text.$ Only one specific choice works.

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: There are no nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$

   Proof: Assume for the sake of contradiction that there are nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$ Then for all nonzero real numbers $x$ and $y$ we can cross-multiply to get $(x + y)^2 = xy\text.$ We consider three cases:

   • Case 1: $xy \lt 0\text.$ We know $(x + y)^2 \ge 0\text,$ which means that $(x + y)^2 \ge 0 \gt xy\text,$ so $(x + y)^2 \ne xy\text.$ This contradicts the fact that $(x + y)^2 = xy\text.$

   • Case 2: $xy = 0\text.$ This means that $x = 0$ or that $y = 0\text,$ contradicting that $x$ and $y$ are nonzero.

   • Case 3: $xy \gt 0\text.$ In particular, this means that $-xy \lt 0\text.$ Notice that $(x + y)^2 = x^2 + 2xy + y^2\text,$ so since $(x + y)^2 = xy\text,$ we see that $xy = x^2 + 2xy + y^2\text.$ In particular, this means that $-xy = x^2 + y^2\text.$ Because $x^2 \ge 0$ and $y^2 \ge 0\text,$ we see that $x^2 + y^2 \ge 0\text,$ so we have that $x^2 + y^2 \ge 0 \gt -xy\text,$ contradicting that $x^2 + y^2 = -xy\text.$

   In all cases, we reach a contradiction, so our assumption was wrong. Thus for all nonzero real numbers $x$ and $y\text,$ we have $\frac{x+y}{x} \ne \frac{y}{x+y}\text{. } \qed$

   Solution

   This proof does not adhere to our style conventions. Notice that in the second sentence, we talk about "for all nonzero real numbers $x$ and $y\text,$" but in the previous sentence we already existentially-introduced $x$ and $y\text.$ In a sense, we're redefining variables that already exist, which is not permitted.

   Notice that in the concluding sentence of the proof we talk about "all nonzero real numbers $x$ and $y\text.$" This is actually perfectly fine; the convention in a proof by contradiction is that after you reach a contradiction, you state what conclusion should be drawn from it. The conclusion really is that something holds for all real numbers $x$ and $y\text.$

   Here's a revised version of the proof that corrects the error:

   Theorem: There are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}$ and $m$ is odd.

   Proof: Suppose for the sake of contradiction that $m$ and $n$ are natural numbers where $\frac{m}{2^n} = \frac{1}{137}$ and where $m$ is odd. Cross-multiplying the previous equality gives us that $137m = 2^n\text.$

   • Case 1: $n = 0\text.$ Then we see that $2^n = 2^0 = 1\text.$ Since $2^n = 137m\text,$ we see that $1 = 137m\text,$ which we rearrange to $m = \frac{1}{137}\text.$ This is impossible because $m$ is a natural number and $\frac{1}{137}$ is not.

   • Case 2: $n \ge 1\text.$ Then we can write $n = r + 1$ for some natural number $r\text,$ and we see that $2^n = 2^{r+1} = 2 \cdot 2^r\text.$ This means that $2^n$ is even. However, $2^n = 137m$ and $137m$ is odd, since $m$ is odd and $137 = 2 \cdot 68 + 1$ is odd. This means that $2^n$ is both odd and even, which is impossible.

   In either case, we reach a contradiction, so our assumption was wrong. Thus there are no natural numbers $m$ and $n$ where $\frac{m}{2^n} = \frac{1}{137}\text{. } \qed$

   ---

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $m$ and $n\text,$ if $m + n$ is even, then either $m$ and $n$ are even or $m$ and $n$ are odd.

   Proof: We proceed by contrapositive and will prove that if one of $m$ and $n$ is even and the other is odd, then $m + n$ is odd. We consider two cases:

   • Case 1: $m$ is even and $n$ is odd. Then for all integers $r$ and $s\text,$ we have $m = 2r$ and $n = 2s + 1\text.$ We then see that $m + n = 2r + 2s + 1 = 2(r + s) + 1\text.$ Now pick any integer $t$ where $t = r + s\text.$ We then see that $m + n = 2t + 1\text,$ so for every even integer $m$ and odd integer $n\text,$ we see that $m + n$ is odd.

   • Case 2: $m$ is odd and $n$ is even. Pick $m = 137$ and $n = 106\text.$ We then see that $m + n = 243 = 2 \cdot 121 + 1\text,$ so for every odd integer $m$ and even integer $n$ we see that $m + n$ is odd.

   In each case $m + n$ is odd, as required. $\qed$

   Solution

   This proof does not adhere to our style conventions. There are several errors here:

   • After introducing the contrapositive of our implication, we never actually ask the reader to choose values for $m$ and $n\text.$ We need to do that for two separate reasons: we need to state our assumptions and want-to-show, and at present $m$ and $n$ have not been given values.

   • In Case 1, we say "for all integers $r$ and $s\text,$ we have $m = 2r$ and $n = 2s+1\text.$ But this is not true: given $m$ and $n\text,$ there's exactly one choice of $r$ and $s$ that works. More fundamentally, we have universally-introduced $r$ and $s\text,$ which is what we do if want to prove something about all choices of $r$ and $s\text,$ rather than existentially-introduced $r$ and $s\text,$ which is what we do if we know values exist and just need to give names to them.

   • In Case 1, we say "now pick any integer $t$ where $t = r + s\text.$" Asking the reader to make a choice is what we do for universal instantiation. Here, we are just giving a new name $(t)$ to an already-existing quantity $(r+s)\text,$ so we shouldn't frame it as a choice to the reader. Instead, we should just say what $t$ is.

   • In Case 1, we conclude by talking about "every even integer $m$ and odd integer $n\text,$" which we should not do. We should treat $m$ and $n$ as though they have specific values, just one we didn't pick.

   • In Case 2, we give specific values for $m$ and $n\text.$ This is not permitted: this proof needs to work regardless of what $m$ and $n$ are, so we should treat them as though they are chosen by the reader. Here, we're acting as though we get to pick them.

   Here's a revised version of the proof that corrects the error:

   Theorem: For all integers $m$ and $n\text,$ if $m + n$ is even, then either $m$ and $n$ are even or $m$ and $n$ are odd.

   Proof: We proceed by contrapositive and will prove that if one of $m$ and $n$ is even and the other is odd, then $m + n$ is odd. So choose any integers $m$ and $n$ where one of $m$ and $n$ is even and the other is odd. We consider two cases:

   • Case 1: $m$ is even and $n$ is odd. Then there are integers $r$ and $s$ where $m = 2r$ and $n = 2s + 1\text.$ We then see that $m + n = 2r + 2s + 1 = 2(r + s) + 1\text.$ Thus there is an integer $t$ (namely, $t = r + s\text)$ where $m + n = 2t + 1\text,$ so $m + n$ is odd.

   • Case 2: $m$ is odd and $n$ is even. Then there are integers $r$ and $s$ where $m = 2r + 1$ and $n = 2s\text.$ This means that $m + n = 2s + 1 + 2r = 2r + 2s + 1\text,$ and by the reasoning from Case 1 we see that $m + n$ is odd.

   In each case $m + n$ is odd, as required. $\qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: There are no nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$

   Proof: Assume for the sake of contradiction that there are nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$ Then for all nonzero real numbers $x$ and $y$ we can cross-multiply to get $(x + y)^2 = xy\text.$ We consider three cases:

   • Case 1: $xy \lt 0\text.$ We know $(x + y)^2 \ge 0\text,$ which means that $(x + y)^2 \ge 0 \gt xy\text,$ so $(x + y)^2 \ne xy\text.$ This contradicts the fact that $(x + y)^2 = xy\text.$

   • Case 2: $xy = 0\text.$ This means that $x = 0$ or that $y = 0\text,$ contradicting that $x$ and $y$ are nonzero.

   • Case 3: $xy \gt 0\text.$ In particular, this means that $-xy \lt 0\text.$ Notice that $(x + y)^2 = x^2 + 2xy + y^2\text,$ so since $(x + y)^2 = xy\text,$ we see that $xy = x^2 + 2xy + y^2\text.$ In particular, this means that $-xy = x^2 + y^2\text.$ Because $x^2 \ge 0$ and $y^2 \ge 0\text,$ we see that $x^2 + y^2 \ge 0\text,$ so we have that $x^2 + y^2 \ge 0 \gt -xy\text,$ contradicting that $x^2 + y^2 = -xy\text.$

   In all cases, we reach a contradiction, so our assumption was wrong. Thus for all nonzero real numbers $x$ and $y\text,$ we have $\frac{x+y}{x} \ne \frac{y}{x+y}\text{. } \qed$

   Solution

   This proof does not adhere to our style conventions. Notice that in the second sentence, we talk about "for all nonzero real numbers $x$ and $y\text,$" but in the previous sentence we already existentially-introduced $x$ and $y\text.$ In a sense, we're redefining variables that already exist, which is not permitted.

   Notice that in the concluding sentence of the proof we talk about "all nonzero real numbers $x$ and $y\text.$" This is actually perfectly fine; the convention in a proof by contradiction is that after you reach a contradiction, you state what conclusion should be drawn from it. The conclusion really is that something holds for all real numbers $x$ and $y\text.$

   Here's a revised version of the proof that corrects the error:

   Theorem: There are no nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$

   Proof: Assume for the sake of contradiction that there are nonzero real numbers $x$ and $y$ where $\frac{x+y}{x} = \frac{y}{x+y}\text.$ We can cross-multiply to get $(x + y)^2 = xy\text.$ We consider three cases:

   • Case 1: $xy \lt 0\text.$ We know $(x + y)^2 \ge 0\text,$ which means that $(x + y)^2 \ge 0 \gt xy\text,$ so $(x + y)^2 \ne xy\text.$ This contradicts the fact that $(x + y)^2 = xy\text.$

   • Case 2: $xy = 0\text.$ This means that $x = 0$ or that $y = 0\text,$ contradicting that $x$ and $y$ are nonzero.

   • Case 3: $xy \gt 0\text.$ In particular, this means that $-xy \lt 0\text.$ Notice that $(x + y)^2 = x^2 + 2xy + y^2\text,$ so since $(x + y)^2 = xy\text,$ we see that $xy = x^2 + 2xy + y^2\text.$ In particular, this means that $-xy = x^2 + y^2\text.$ Because $x^2 \ge 0$ and $y^2 \ge 0\text,$ we see that $x^2 + y^2 \ge 0\text,$ so we have that $x^2 + y^2 \ge 0 \gt -xy\text,$ contradicting that $x^2 + y^2 = -xy\text.$

   In all cases, we reach a contradiction, so our assumption was wrong. Thus for all nonzero real numbers $x$ and $y\text,$ we have $\frac{x+y}{x} \ne \frac{y}{x+y}\text{. } \qed$

   ---

Make Specific Claims About Specific Variables

Mathematical proofs work by taking specific quantities, represented as expressions of variables, and manipulating those quantities to arrive at a result. Therefore, statements made in a mathematical proof need to be made in reference to specific values rather than stated in the abstract. A common mistake when writing proofs is to instead describe, at a high level, why a result ought to be true, then conclude that the result is indeed true. Here's an example of this:

Notice that this entire proof discusses numbers in general at a high level. None of the statements here, except the very last one, reference any variables. As a result, while this proof may have some good ideas in it, it's written too abstractly to be rigorous. Unfortunately, there really isn't a way to salvage this proof. We pretty much have to scrap it and start over, operating at a lower level, and with a higher degree of precision.

In the example proof above, the statements made happen to be true. However, it's easy to reach incorrect conclusions when reasoning this way and not focusing on concrete, specific values. We'll see more examples of this later in the quarter.

When you’re first studying proof-based mathematics, you’ll likely have a number of intuitions about how different types of objects behave. Some of these intuitions are great, and you should keep using them. Other intuitions, on the other hand, can be at odds with what the math says, and when that happens, you should refine those intuitions so that they guide you in the right direction.

The only way to know which of your intuitions are good and which need tuning is to explicitly validate those intuitions by attempting to formalize them mathematically. To do so, we ask that you speak with mathematical precision and to show how specific applications of definitions give you your result. If you’re able to do this, great! It likely means your intuition is pointing you the right way. If not, that might indicate that your intuition might be suggesting something that the math says isn’t true, in which case it’s a good thing that you tried formalizing things! At that point, you should back up, pause, and see whether the result is still true for some other reason or whether you need to reshape your intuition for the future.

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   In what follows, we say that a natural number $n$ is called a Hilbert number if there is a natural number $k$ where $n = 4k + 1\text.$

   Theorem: For all natural numbers $m$ and $n\text,$ if $m$ and $n$ are Hilbert numbers, then so is $mn\text.$

   Proof: Let $m$ and $n$ be Hilbert numbers. We need to show that $mn$ is also a Hilbert number.

   When multiplying numbers together that have some property, the product also has that property. For example, the product of two even numbers is even, the product of two odd number is odd, the product of two numbers between 0 and 1 inclusive is between 0 and 1 inclusive, etc. Thus since $m$ and $n$ are Hilbert numbers, their product must be as well. $\qed$

   Solution

   This proof does not adhere to our style conventions. The crux of this argument is the high-level statement "when multiplying numbers together that have some property, the product also has that property." This is both far abstract (what counts as a "property?") and is not true in general. For example, the product of two negative numbers will not be negative, the product of two numbers between 1 and 2 is not necessarily between 1 and 2, etc. Because this line of reasoning is not sufficient, rewriting this proof is a more difficult exercise. We essentially need to scrap the proof and start over.

   There are many other issues here (e.g. we don't state our assumptions and want-to-show), but given that we need to rewrite the proof from scratch we won't go into those details here.

   Here's a more proper way to prove this result:

   Theorem: For all natural numbers $m$ and $n\text,$ if $m$ and $n$ are Hilbert numbers, then so is $mn\text.$

   Proof: Let $m$ and $n$ be Hilbert numbers. We need to show that $mn$ is a Hilbert number.

   Since $m$ and $n$ are Hilbert numbers, there exist natural numbers $r$ and $s$ such that $m = 4r + 1$ and $n = 4s + 1\text.$ We then see that

   \[\begin{aligned} mn &= (4r + 1)(4s + 1) \\ &= 16rs + 4r + 4s + 1 \\ &= 4(4rs + r + s) + 1\text. \end{aligned}\]

   This means there is a natural number $t\text,$ namely, $4rs + r + s\text,$ such that $mn = 4t + 1\text.$ Thus $mn$ is a Hilbert number. $\qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: There exists a Hilbert number $n \gt 1$ such that there are Hilbert numbers $p, q \gt 1$ where $n = pq\text.$

   Proof: We are asked to show that some Hilbert number is the product of two other Hilbert numbers (all excluding 1, which would make this trivial because $1 \cdot 1 = 1\text{.)}$ Earlier we proved that the product of two Hilbert numbers is also a Hilbert number. Since there are infinitely many pairs of Hilbert numbers we could multiply together and infinitely many Hilbert numbers, there must be some Hilbert number $n \gt 1$ where $n = pq$ for Hilbert numbers $p$ and $q$ other than 1. $\qed$

   Solution

   This proof does not adhere to our style conventions. This argument does not engage with the formal definition of a Hilbert number - it never talks about numbers of the form $4k + 1$ - and so it can't be a rigorous proof. The argument works at a high level by restating other results we've already proved and talking about how there's infinitely many numbers of two different forms, so there must be some overlap. That isn't true: for example, there are infinitely many prime numbers, but the product of two prime numbers is never prime. As before, we pretty much have to start over from scratch here by throwing out this proof and writing a new one.

   Finding numbers that work here is more or less an exercise in trial and error - or a quick Python script:

   for i in range (1, 10):
       for j in range(1, 10):
           num1    = 4*i + 1
           num2    = 4*j + 1
           product = num1 * num2
           
           if product % 4 == 1:
               print(f"{num1} * {num2} = {product}")
   

   This outputs a bunch of numbers that work. I personally like $21 \cdot 37 = 777$ and so that's what I've put in the revised proof.

   Theorem: There exists a Hilbert number $n \gt 1$ such that there are Hilbert numbers $p, q \gt 1$ where $n = pq\text.$

   Proof: Pick $n = 777\text,$ $p = 21\text,$ and $q = 37\text.$ We see by inspection that $pq = n\text,$ and we also have $n \gt 1\text,$ $p \gt 1\text,$ and $q \gt 1\text.$ Finally, note that these are all Hilbert numbers: $21 = 4 \cdot 5 + 1\text,$ $37 = 4 \cdot 9 + 1\text,$ and $777 = 4 \cdot 194 + 1\text{. } \qed$

   ---

Don’t Repeat Definitions; Use Them Instead

When writing a proof, make sure that you do not restate definitions in the abstract. Instead, apply them to specific circumstances to draw specific conclusions.

For example, consider the following three (not good) excerpts from three (not good) proofs:

In each of these cases, we begin with the fact that $n$ is even, and we arrive at the endpoint that $n = 2k$ for some integer $k$. The issue is in the middle sentences. In each case, we're essentially restating the definition of what an even number is. This is unnecessary and makes our proof longer. Here's a much shorter, cleaner way to do this:

"But wait!," you might say, "don't I need to tell the reader where that integer $k$ is coming from?" The answer is "no, you don't." When you're writing a proof, you should assume that the reader is familiar with all the relevant terms and definitions. Your goal isn't to say what those definitions are, but rather how those definitions work together to give your result. Think of it this way: the mathematical definitions we have are like the rules of a game. The proof should be you playing the game with the reader, rather than pausing every few minutes to remind the reader what the rules of the game are. (Imagine watching a sports match where the players keep interrupting the action to explain why they're allowed to do what they're doing!)

There's a further reason not to repeat definitions in your proof: you run the risk of violating other checklist rules. Let’s go one at a time through the three examples above that we advise against. The first one is far too general (“Every even number can be written as twice some integer”) and therefore breaks our advice of making specific claims about specific variables. The second one (“Every even number can be written as $2k$ for some integer $k$”) is a variable scoping error – $k$ is a placeholder here for "the number that some abstract even integer is twice as big as." The third one is making specific claims about the variable $m$, but in that case $m$ is a placeholder (you didn't pick it, the reader didn't pick it, and it isn't something already known to exist).

And one more reason to not restate definitions: it makes proofs shorter. Often, when we see students struggling with proofwriting, our advice is to write less rather than more, and it's often because of this specific rule.

To summarize - avoiding restating definitions in the abstract makes the proof flow more clearly for the reader, avoids variable scoping errors, and reduces the amount of writing required. Isn't that great?

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For every odd natural number $n\text,$ the sum of $n$ and the next four natural numbers is odd.

   Proof: Pick an odd natural number $n\text.$ We need to show that the sum $n + (n+1) + (n+2) + (n+3) + (n+4)$ is odd.

   An odd natural number $m$ is one where $m = 2k+1$ for some integer $k\text.$ Therefore, since $n$ is odd, we can write $n = 2k+1$ for some integer $k\text.$

   Next, note that $n + (n+1) + (n+2) + (n+3) + (n+4) = 5n + 10\text.$ We then see that

   \[\begin{aligned} 5n + 10 &= 5(2k+1) + 10 \\ &= 10k + 5 + 10 \\ &= 10k + 15 \\ &= 2(5k + 7) + 1\text. \end{aligned}\]

   Thus there is an integer $m\text,$ namely, $5k + 7\text,$ such that $5n + 10 = 2m + 1\text.$ An odd number is one that can be written as twice an integer plus one, which means that $5n + 10$ is odd, as required. $\qed$

   Solution

   This proof does not adhere to our style conventions. In particular, it restates the definition of an odd number in two separate places: the first sentence of the second paragraph, and the last sentence of the last paragraph. (The first sentence of the second paragraph could also be said to violate the "Scope and Properly Introduce Variables" rule, since $m$ is a placeholder.)

   Here is a better way to write this proof:

   Theorem: For every odd natural number $n\text,$ the sum of $n$ and the next four natural numbers is odd.

   Proof: Pick an odd natural number $n\text.$ We need to show that the sum $n + (n+1) + (n+2) + (n+3) + (n+4)$ is odd.

   Since $n$ is odd, we can write $n = 2k+1$ for some integer $k\text.$ Next, note that $n + (n+1) + (n+2) + (n+3) + (n+4) = 5n + 10\text.$ We then see that

   \[\begin{aligned} 5n + 10 &= 5(2k+1) + 10 \\ &= 10k + 5 + 10 \\ &= 10k + 15 \\ &= 2(5k + 7) + 1\text. \end{aligned}\]

   Thus there is an integer $m\text,$ namely, $5k + 7\text,$ such that $5n + 10 = 2m + 1\text.$ This means that $5n + 10$ is odd, as required. $\qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   In the context of this theorem, a Pythagorean triple is a triple $(a, b, c)$ of positive natural numbers where $a^2 + b^2 = c^2\text.$

   Theorem: For every odd natural number $a \gt 1\text,$ there exist natural numbers $b$ and $c$ where $(a, b, c)$ is a Pythagorean triple.

   Proof: Pick an odd natural number $a \gt 1\text.$ We need to find natural numbers $b$ and $c$ where $(a, b, c)$ is a Pythagorean triple.

   In lecture, we proved that the square of every odd number is odd. This means that $a^2$ is odd, and therefore that there is a natural number $k$ where $a^2 = 2k + 1\text.$ Now, let $b = k$ and $c = k+1\text.$ We need to show that $(a, b, c)$ is a Pythagorean triple.

   First, notice that

   \[\begin{aligned} a^2 + b^2 &= (2k + 1) + k^2 \\ &= k^2 + 2k + 1 \\ &= (k+1)^2 \\ &= c^2\text.$ \end{aligned}\]

   In a Pythagorean triple, all terms must be greater than zero. We know that $a \gt 1\text,$ so $a$ is positive. We also can see that $c = k+1 \ge 1\text,$ so $c \gt 0\text.$ To see that $b \ge 0\text,$ suppose for the sake of contradiction that $b = 0\text.$ This means that $a^2 = k = 0\text,$ which means that $a = 0\text.$ This is impossible, since by assumption we know $a \gt 1\text.$ We've reached a contradiction, so our assumption was wrong and $b \gt 0\text.$

   Overall, we have shown that $a^2 + b^2 = c^2$ and that $a \gt 0\text,$ $b \gt 0\text,$ and $c \gt 0\text,$ which means that $(a, b, c)$ is a Pythagorean triple, as required. $\qed$

   Solution

   This proof does not adhere to our style conventions. There are two spots worth focusing on:

   1. The first sentence of the second paragraph ("In lecture, we proved that the square of every odd number is odd") restates a general result in the abstract. The proof is fine referencing that result, but it should apply it rather than just stating it a second time at a high level.

   2. The first sentence of the penultimate paragraph ("In a Pythagorean triple, all terms must be greater than zero") restates a general property of Pythagorean triples. The proof has the right idea to say something about this because it's necessary to prove this, but the way in which this is done is incorrect. This should be introduced as a goal in which the proof states it will prove something about $a\text,$ $b\text,$ and $c$ specifically.

   Here's how to touch up this proof:

   Theorem: For every odd natural number $a \gt 1\text,$ there exist natural numbers $b$ and $c$ where $(a, b, c)$ is a Pythagorean triple.

   Proof: Pick an odd natural number $a \gt 1\text.$ We need to find natural numbers $b$ and $c$ where $(a, b, c)$ is a Pythagorean triple.

   As we proved in lecture, since $a$ is odd, we know that $a^2$ is odd, and therefore that there is a natural number $k$ where $a^2 = 2k + 1\text.$ Now, let $b = k$ and $c = k+1\text.$ We need to show that $(a, b, c)$ is a Pythagorean triple.

   First, notice that

   \[\begin{aligned} a^2 + b^2 &= (2k + 1) + k^2 \\ &= k^2 + 2k + 1 \\ &= (k+1)^2 \\ &= c^2\text. \end{aligned}\]

   Next, we will prove that $a \gt 0\text,$ that $b \gt 0\text,$ and that $c \gt 0\text.$ We know that $a \gt 1\text,$ which tells us $a \gt 0\text.$ We also can see that $c = k+1 \ge 1\text,$ so $c \gt 0\text.$ To see that $b \ge 0\text,$ suppose for the sake of contradiction that $b = 0\text.$ This means that $a^2 = k = 0\text,$ which means that $a = 0\text.$ This is impossible, since by assumption we know $a \gt 1\text.$ We've reached a contradiction, so our assumption was wrong and $b \gt 0\text.$

   Overall, we have shown that $a^2 + b^2 = c^2$ and that $a \gt 0\text,$ $b \gt 0\text,$ and $c \gt 0\text,$ which means that $(a, b, c)$ is a Pythagorean triple, as required. $\qed$

   ---

Write In Complete Sentences and Paragraphs

Although proofs convey mathematical arguments, they should be written in grammatically-correct English sentences and in paragraph form.

A good check for this is what we call the mugga mugga test. Take your proof and try reading it out loud, replacing all the mathematical content with the phrase “mugga mugga.” If what comes back is grammatically correct, then you’re on the right track. On the other hand, if what you write is hard to read aloud, or just plain doesn’t sound right, it means that you might need to go back and correct things. As an example, here’s an excerpt from a not-so-great proof that if $n$ is even, then $n^2$ is even:

Let’s apply the mugga mugga test to this proof, one sentence at a time. Here’s the first sentence:

• Original: Since $n$ is even, $n = 2k$.
• Mugga Mugga Version: Since $n$ is even, mugga mugga.

The mugga-muggaified version of this sentence isn’t grammatically correct – it has no subject and no verb. The reason for this is that the subject of the original sentence is $n$ and the verb is “equals,” but since we’ve written out the equality using the equals sign, it got mugga-muggified in the updated version of the sentence.

More generally:

Tip: Avoid writing sentences where mathematical notation must be treated as the verb in the sentence.

So what should we do instead? Let’s begin with what you shouldn’t do. Don’t rewrite the sentence like this in order to pass the mugga mugga test:

This technically passes the mugga mugga test, but it’s doing so by taking a clear mathematical statement ($n = 2k$) and rendering the unambiguous, precise mathematical symbol $=$ in English. The whole reason for having mathematical symbols in the first place is so that we can be precise with our notation, and this is a step in the wrong direction.

Instead, consider rewriting the sentence in a way that introduces a new subject and a new verb. There are many ways that we can do this. Here are a few options to choose from:

• Option 1: Since $n$ is even, we can write $n = 2k$.

  Mugga Mugga Version: Since $n$ is even, we can write mugga mugga. (The subject is "we" and the verb is "can write")

• Option 2: Since $n$ is even, we see that there is some integer $k$ such that $n = 2k$.

  Mugga Mugga Version: Since $n$ is even, we see that there is some integer $k$ such that mugga mugga. *(The subject is "we" and the verb is "see")

• Option 3: Since $n$ is even, there is some integer $k$ where $n = 2k$.

  Mugga Mugga Version: Since $n$ is even, there is some integer $k$ where mugga mugga. (The subject is the integer $k$ and the verb is "is.")

Notice how in each sentence we’ve introduced an explicit subject and verb in a way that passes the mugga mugga test.

Let’s look at this second sentence:

• Original: $n^2 = 4k^2$, which is $2(2k^2)$.
• Mugga Mugga Version: Mugga mugga, which is mugga mugga.

This sentence has no subject and no verb, since the verb here is again the equality between $n^2$ and $4k^2$. To fix this, let's restructure the sentence to include a new subject and new verb. Here are some options:

• Option 1: Notice that $n^2 = (4k^2)$, which we can rewrite as $n^2 = 2(2k^2)$.

  Mugga Mugga Version: Notice that mugga mugga, which we can rewrite as mugga mugga.

• Option 2: We see that $n^2 = 4(k^2)$, which means $n^2 = 2(2k^2)$.

  Mugga Mugga Version: We see that mugga mugga, which means mugga mugga.

A common theme in the mugga mugga test is that you should avoid using math notation as the verb in a sentence. Similarly, you should avoid using mathematical notation or shorthands to abbreviate parts of sentences. There are a number of shorthands that have been developed over the years, primarily for use on blackboards where writing out longhand can take a while. For example, the word “therefore” is often abbreviated $\therefore$, and the word “because” is often abbreviated $\because$. These shorthands are just that – they’re shorthands – and should not be used in mathematical proofs except if you’re trying to write something up quickly and on a blackboard. For example, please, please, please don’t write the following:

This one really, really, really fails the mugga mugga test:

This almost reads like a parody of a terrible math lecture. So please don’t write proofs like this. ☺

Just as you’re expected to write in complete sentences, you’re expected to write in complete paragraphs. This means that your proofs should not consist of bulleted or numbered lists of statements. For example, please don’t write proofs like these:

Although we can see what this proof is saying, this just isn’t the format that’s expected and so you shouldn’t structure things this way.

Why we enforce this rule: We primarily enforce this rule because this is the standard convention in mathematical writing and we’re hoping to train you to communicate mathematics effectively. Additionally, this rule makes proofs much easier to read by requiring you, the writer, to link your ideas together in a way that helps the argument flow.

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   In the context of this theorem, a perfect square is a natural number $n$ where there is a natural number $k$ such that $n = k^2\text.$

   Theorem: For all natural numbers $n \ge 1,$ the number $n(n+1)$ is not a perfect square.

   Proof: Assume for the sake of contradiction that there is a natural number $n$ that is $\ge 1$ and where $n(n+1)$ is a perfect square. Because $n(n+1)$ is a perfect square, there is a natural number $k$ where $n(n+1) = k^2\text.$

   \[n(n+1) = k^2\] \[n^2 + n = k^2\]

   Also, $n^2 + n \lt n^2 + n + 1 \le n^2 + 2n + 1 = (n + 1)^2\text.$ So $k^2 \lt (n+1)^2\text,$ so $k \lt n+1\text.$

   Because $n \ge 1\text,$ $n(n+1) = n^2 + n \ge n^2 + 1 \gt n^2\text.$ So $k^2 \gt n^2$ so $k \gt n\text.$

   Collectively, this means that $n \lt k \lt n+1\text,$ which is impossible because $k$ is an integer. We have reached a contradiction, so our assumption was wrong. Thus if $n \ge 1$ is a natural number, then $n(n+1)$ is not a perfect square. $\qed$

   Solution

   This proof does not adhere to our style conventions. Here's what this reads as if we apply the mugga mugga test. Each instance in red is a sentence with no subject or verb. Each instance in blue is not a sentence at all. Each instance in purple is a spot where a mathematical operator was used as a verb.

   Proof: Assume for the sake of contradiction that there is a natural number $n$ that is mugga mugga and where mugga mugga is a perfect square. Because mugga mugga is a perfect square, there is a natural number $k$ where mugga mugga.

   mugga mugga

   mugga mugga

   Also, mugga mugga. So mugga mugga, so mugga mugga.

   Because mugga mugga, mugga mugga. So mugga mugga.

   Collectively, this means that mugga mugga, which is impossible because $k$ is an integer. We have reached a contradiction, so our assumption was wrong. Thus if mugga mugga is a natural number, then mugga mugga is not a perfect square. $\qed$

   Correcting each of these errors gives the following proof, which is a lot easier to read:

   Theorem: For all natural numbers $n \ge 1,$ the number $n(n+1)$ is not a perfect square.

   Proof: Assume for the sake of contradiction that there is a natural number $n \ge 1$ and where $n(n+1)$ is a perfect square. Because $n(n+1)$ is a perfect square, there is a natural number $k$ where $n(n+1) = k^2\text.$

   First, notice that

   \[\begin{aligned} k^2 &= n(n+1) \\ &= n^2 + n \\ &\lt n^2 + n + 1 \\ &\le n^2 + 2n + 1 \\ &= (n+1)^2\text, \end{aligned}\]

   which shows overall that $k^2 \lt (n+1)^2\text.$ This in turn means that $k \lt n+1\text.$

   Next, notice that

   \[\begin{aligned} k^2 &= n(n+1) \\ &= n^2 + n \\ &\ge n^2 + 1 && \text{(since } n \ge 1 \text) \\ &\gt n^2\text, \end{aligned}\]

   which means that $k^2 \gt n^2\text.$ This tells us that $k \gt n\text.$

   Collectively, this means that $n \lt k \lt n+1\text,$ which is impossible because $k$ is an integer. We have reached a contradiction, so our assumption was wrong. Thus if $n \ge 1$ is a natural number, then $n(n+1)$ is not a perfect square. $\qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   This proof makes use of the following theorem: there are no integers $p, q$ where $q \ne 0$ and where $p^2 = 2q^2\text.$ It also makes use of the following definition: a rational number is a real number $x$ for which there are integers $p$ and $q$ where $q \ne 0$ and $x = \frac{p}{q}\text.$

   Theorem: $2^\frac{1}{12}$ is not a rational number. (This means it's not possible to precisely tune a piano.)

   Proof: Assume for the sake of contradiction that $2^\frac{1}{12}$ is rational. Then $2^\frac{1}{12} = \frac{p}{q}\text,$ $p \in \integers\text,$ $q \in \integers\text,$ and $q \ne 0\text.$

   \[(2^\frac{1}{12})^{12} = \left(\frac{p}{q}\right)^{12}\] \[2 = \frac{p^{12}}{q^{12}}\] \[2q^{12} = p^{12}\]

   Now let $q' = q^{12}$ and $p' = p^{12}\text.$ $q \ne 0 \Rightarrow q^{12} \ne 0 \Rightarrow q' \ne 0\text,$ same with $p$ and $p'\text.$ But $2q' \ne p'$ with $q' \ne 0\text,$ $\therefore$ contradiction. $\qed$

   Solution

   This proof does not adhere to our style conventions. Here's what this reads as if we apply the mugga mugga test. Each instance in red is a sentence with no subject or verb. Each instance in blue is not a sentence at all. Each instance in purple is a spot where a mathematical operator was used as a verb.

   Proof: Assume for the sake of contradiction that mugga mugga is rational. Then mugga mugga, mugga mugga, and mugga mugga

   mugga mugga

   mugga mugga

   mugga mugga

   Now let mugga mugga and mugga mugga. mugga mugga, same with $p$ and $p'\text.$ But mugga mugga with mugga mugga mugga mugga contradiction. $\qed$

   Beyond the fact that this proof fails the mugga mugga test, it also violates the "scope and properly introduce variables" rule when introducing $p$ and $q$ in the top paragraph, the "clearly articulate your assumptions and want-to-shows" by not restating what the contradiction entails, and the "make each sentence load-bearing" rule by stating that $p' \ne 0$ even though this is not used anywhere.

   Correcting each of these errors gives the following proof:

   Theorem: $2^\frac{1}{12}$ is not a rational number.

   Proof: Assume for the sake of contradiction that $2^\frac{1}{12}$ is rational. Then there exist integers $p$ and $q$ where $2^\frac{1}{12} = \frac{p}{q}$ and $q \ne 0\text.$

   We can manipulate our original equality to see that

   \[(2^\frac{1}{12})^{12} = \left(\frac{p}{q}\right)^{12}\text,\]

   which means that

   \[2 = \frac{p^{12}}{q^{12}}\]

   or, equivalently, that

   \[2q^{12} = p^{12}\text.\]

   Now let $q' = q^{12}$ and $p' = p^{12}\text.$ Since $q \ne 0\text,$ we know that $q^12 \ne 0\text,$ so $q' \ne 0\text.$ However, this means that there are integers $q'$ and $p'$ where $q' \ne 0$ and where $2q' = p'\text,$ which we know is impossible.

   We've reached a contradiction, so our assumption was wrong and $2^{\frac{1}{12}}$ is not rational. $\qed$

   ---

Avoid the “Contradiction Sandwich”

Consider the following proof:

This proof, as written, is logically correct. We begin by assuming the negation of our theorem, obtain some values $m$ and $n$ to work with, and reach a contradiction between what we show and what we assumed.

All would be right and well in the universe if not for one key fact. Look at the central part of this proof, with the first and last sentences removed. That gives this:

This is almost literally a complete and correct direct proof of the theorem we’re trying to prove. (We’re missing our assume and want to show steps, but those can be added in pretty easily.)

Because the core line of reasoning in this proof works just as well as a direct proof, we call the original proof a contradiction sandwich. Essentially, the proof proceeds like this:

1. Assume, for the sake of contradiction, that the theorem is false.
2. Prove the theorem using a direct proof.
3. This contradicts that the theorem is false, so the theorem is true.

Here, the “meat” of the proof is in step (2), the actual direct proof. That’s “sandwiched” between the start and end of a proof by contradiction, which doesn’t add anything substantial to the proof.

The takeaway here is that if you finish writing a proof by contradiction, take a minute or two to read over your proof. Is it a contradiction sandwich? If so, simply remove the contradiction bits and present the direct proof on its own.

This is not to say that you shouldn't write proofs by contradiction, or that you're expected to use direct proofs whenever possible. Rather, we ask that after writing a proof you pause, reflect on what you've written, and see whether there is a clear way to simplify it in the specific case that it's a contradiction sandwich.

Exercises

1. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all real numbers $a$ and $b\text,$ we have $\abs{a + b} \le \abs{a} + \abs{b}\text.$

   Proof: Assume for the sake of contradiction that there exist $a, b \in \reals$ where $\abs{a + b} \gt \abs{a} + \abs{b}\text.$

   First, we note that $a \le \abs{a}$ and that $b \le \abs{b}\text.$ To see this, note that if $a \ge 0$ then $a = \abs{a}\text,$ and that if $a \lt 0$ then $a \lt 0 \le \abs{a}\text;$ similar reasoning establishes this for $b$ as well.

   We now consider two cases:

   • Case 1: $a + b \ge 0\text.$ In that case, we see that

     \[\abs{a + b} = a + b \le \abs{a} + \abs{b}\text.\]

   • Case 2: $a + b \le 0\text.$ In that case, we see that

     \[\abs{a + b} = -(a + b) = -a + -b \le \abs{-a} + \abs{-b} = \abs{a} + \abs{b}\text.\]

   In each case, we see that $\abs{a + b} \le \abs{a} + \abs{b}\text.$ But this is impossible, since we know that $\abs{a + b} \gt \abs{a} + \abs{b}\text.$

   We have reached a contradiction, so our assumption was wrong and for all $a, b \in \reals$ we have $\abs{a + b} \le \abs{a} + \abs{b}\text{. } \qed$

   Solution

   This proof does not adhere to our style conventions because it's a contradiction sandwich. We assume the theorem is false and, without relying on that assumption, reach the conclusion that the theorem is true. We can thus remove the contradiction layer like this:

   Theorem: For all real numbers $a$ and $b\text,$ we have $\abs{a + b} \le \abs{a} + \abs{b}\text.$

   Proof: Let $a$ and $b$ be real numbers. We need to show that $\abs{a + b} \le \abs{a} + \abs{b}\text.$

   First, we note that $a \le \abs{a}$ and that $b \le \abs{b}\text.$ To see this, note that if $a \ge 0$ then $a = \abs{a}\text,$ and that if $a \lt 0$ then $a \lt 0 \le \abs{a}\text;$ similar reasoning establishes this for $b$ as well.

   We now consider two cases:

   • Case 1: $a + b \ge 0\text.$ In that case, we see that

     \[\abs{a + b} = a + b \le \abs{a} + \abs{b}\text.\]

   • Case 2: $a + b \le 0\text.$ In that case, we see that

     \[\abs{a + b} = -(a + b) = -a + -b \le \abs{-a} + \abs{-b} = \abs{a} + \abs{b}\text.\]

   In each case, we see that $\abs{a + b} \le \abs{a} + \abs{b}\text,$ as required. $\qed$

   ---

2. Does the following proof adhere to the style expectation outlined in this section? If not, rewrite it so that it does.

   Theorem: For all integers $n\text,$ if $n^2$ is even, then $n$ is even.

   Proof: Assume for the sake of contradiction that there is an integer $n$ where $n^2$ is even but $n$ is odd.

   Since $n$ is odd, there is an integer $k$ where $n = 2k+1\text.$ This means that

   \[\begin{aligned} n^2 &= (2k+1)^2 \\ &= 4k^2 + 4k + 1 \\ &= 2(2k^2 + 2k) + 1\text. \end{aligned}\]

   This means that there is an integer $m\text,$ namely $2k^2 + 2k\text,$ such that $n^2 = 2m + 1\text.$ This means that $n^2$ is odd, contradicting the fact that $n^2$ is even.

   We have reached a contradiction, or our assumption was wrong and if $n^2$ is even, then $n$ is even. $\qed$

   Solution

   This proof does adhere to our style requirements. This is not a contradiction sandwich: the proof actively relies on the assumption that $n$ is odd to reach a contradiction, and we could not assume $n$ was odd in a direct proof.

   That being said, this could be rewritten as a proof by contrapositive, and indeed I personally think it's more elegant when written out that way. However, there's no requirement that we use a proof by contrapositive here.

   ---