Over the years, weâve found many common proofwriting errors that can easily be spotted once you know how to look for them. In this handout, weâve distilled seven major points about proofwriting that we will specifically be looking for when grading your assignments. They are as follows:
- Clearly articulate your assumptions and âwant-to-shows.â
- Make each sentence âload-bearing.â
- Scope and properly introduce variables.
- Make specific claims about specific variables.
- Donât repeat definitions; use them instead.
- Write in complete sentences and complete paragraphs.
- Distinguish between proofs and disproofs.
- Avoid the âContradiction Sandwich.â
Some of the items on this list, like âwrite in complete sentences and complete paragraphs,â are purely stylistic requirements on proofs. Theyâre there because they ensure that youâre writing proofs in the expected mathematical style. Other items on this list, like âscope and properly introduce variables,â are there because theyâre often comorbid with more serious logic errors that can derail a proof. Our hope is that by providing these specific items to look for when checking your proofs, youâll be able to check your own work more effectively and build a better intuition for when thereâs something in a proof that just doesnât feel right.
We will be applying this checklist to the proofs that you submit. We strongly recommend that you work through this checklist on every proof that you write. Doing so will help you improve your proofwriting and possibly smoke out some underlying logic errors.
The remainder of this handout goes into more detail about what each of these rules mean.
Clearly Articulate Your Assumptions and âWant-to-Shows.â
When youâre writing a proof, youâre laying out an argument that explains why a certain result is true. Most proofs have a number of intermediate steps that build up toward a larger result. When writing a proof, itâs important to make sure that the reader has a clear sense of where it is that youâre going and how youâre going to arrive there. Otherwise, your proofs will be extremely hard to read, since while the reader might follow each individual step, they might have no idea where youâre going with things. Think about how you might write an argumentative essay â if you just list a series of facts without giving some idea of where youâre ultimately going, your readers are going to have a heck of a time trying to make sense of what youâre doing!
Letâs illustrate this with an example. Consider the following proof:
â Incorrect! â Proof: Consider an arbitrary $x \in A$. Since $x \in A$ and $A \subseteq B$, we see that $x \in B$. And, since $x \in B$ and $B \subseteq C$, we see that $x \in C$. â
Hereâs a question for you â what exactly is this proof trying to accomplish? Itâs hard to say, since we donât know what $A$, $B$, and $C$ are, it seems like the statements $A \subseteq B$ and $B \subseteq C$ come out of nowhere, and the conclusion doesnât say exactly why any of this matters.
The above proof was written for the following theorem:
Theorem: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
With knowledge of the theorem in mind, the proof makes more sense. We know that $A \subseteq B$ and that $BÂ \subseteq C$ by assumption, and weâre looking at elements of $A$ and trying to get them as elements of $C$ because weâre trying to prove something about the subset relation. But that still shifts a lot of work to the person reading the proof. A better proof would provide more guidance about where everything comes from and where everything is going. Hereâs what that might look like:
Proof: Let $A$, $B$, and $C$ be arbitrary sets where $A \subseteq B$ and $B \subseteq C$. We want to show that $A \subseteq C$. To do so, choose an arbitrary $x \in A$. We need to show that $x \in C$.
Since $x \in A$ and $A \subseteq B$, we see that $x \in B$. And, since $x \in B$ and $B \subseteq C$, we see that $x \in C$, which is what we needed to show. â
Compare this proof to the one before it. Even if you had no idea what the theorem was when going into this proof, you could still see exactly whatâs being done â whatâs being assumed, whatâs being proved, how the logic flows, etc. Thereâs no more mystery about why $A \subseteq B$ and $B \subseteq C$ are true: we can see that theyâre true by assumption.
Thereâs a number of reasons why itâs worthwhile to set up your proofs this way. First, when youâre still working through the problem and trying to figure out why exactly the result is true, this step forces you to write out exactly what it is that youâre assuming and what you need to prove. That makes it much easier to figure out what directions you should consider. It also forces you to articulate very precisely what it is that you need to establish. If you look at the overall theorem to prove here, it might seem, well, kinda obvious. Like, âwell, of course if $A$ is a subset of $B$ and $B$ is a subset of $C$, then $A$ is a subset of $C$ â thatâs just what subset means!â But if you start unpacking the definitions and articulating where specifically youâre going to start and end, it becomes much easier to see what you need to do.
Why we enforce this rule: When youâre first learning how to write proofs, one of the biggest challenges is simply figuring out what it is that youâre supposed to assume and what it is that youâre supposed to prove. By requiring that you articulate this information clearly, we hope to reduce the likelihood that you submit a proof that is a completely correct proof of the completely wrong theorem.
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.
This is a particularly useful check to apply to a proof after youâve first finished writing it, since often times 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.
Why we enforce this rule: We enforce this rule for a number of reasons.
First, this rule is designed to get you to review your proofs after having written a first draft. Itâs common, in writing up the first version of a proof, to include statements that arenât actually needed later on, and by requiring each statement to be load-bearing we hope to encourage you to closely review your work to make sure that everything youâve included ends up getting used.
Second, this rule is there to make sure that you are being precise with your reasoning. If you find that your proofs include sentences that talk about how things tend to work in general, or which describe a mathematical situation without the precision required above, it might indicate that you havenât pinned things down as tightly as you may have expected.
Finally, this rule is here because this is just how proofs are expected to be written these days. Itâs common in mathematics to separate mathematical proofwriting from mathematical expository writing. In an exposition, an author might talk about various intuitions theyâve had, various insights that will make things easier to understand, etc., but in the proof itself itâs common for sentences to be fairly direct and to the point.
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 reader (and the compiler!) know what sort of thing the variable can hold and what it represents. 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 because thereâs something amiss with what youâve done.
Variables in mathematical proofs obey a similar sort of convention. When writing proofs, itâs important that you clearly and precisely 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:
-
An arbitrarily-chosen value. A variable like this doesnât represent some specific number, set, or quantity, but rather an arbitrarily-chosen value. 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 itâs chosen arbitrarily.
-
An existentially instantiated value. Sometimes, you know that some quantity must exist, but you donât know what it is. 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 you write up a proof (or, more generally, when youâre reading something mathematical), itâs important to make sure that you can look at each variable and clearly tell whether that variable is arbitrarily chosen, existentially instantiated, or explicitly chosen. Just like variables in C, C++, or Java, this helps you clearly 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:
For any sets $A$, $B$, and $C$, if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
Hereâs a not-so-great proof of this result:
â Incorrect! â Proof: Let $A$, $B$, and $C$ be arbitrary sets where $A \subseteq B$ and $B \subseteq C$. This means that for any choice of $x$, if $x \in A$, then $x \in B$. Similarly, for any choice of $x$, if $x \in B$, then $x \in C$. We need to show that $A \subseteq C$, which means that we need to prove that for any choice of $x$, if $x \in A$, then $x \in C$.
To show this, consider any $x \in A$. Since $x \in A$ and we know that any $x \in A$ must also be an element of $B$, we see that $x \in B$. Similarly, since $x \in B$ and we know that any $x \in B$ must also be an element of $C$, we see that $x \in C$, which is what we needed to show. â
Letâs focus on a few of sentences. For starters, letâs look at this sentence from the first paragraph:
This ($A \subseteq B$) means that for any choice of $x$, if $x \in A$, then $x \in B$.
What, exactly, is the variable $x$ here? Itâs not an arbitrarily-chosen $x$, since we didnât say something like âchoose an arbitrary $x$.â It's not a value of $x$ we chose - we're saying "for any $x$," which isn't us giving a specific choice. And it's not some value we already know exists that we're just giving a name to.
Instead, the variable $x$ is just a placeholder: it says that if we find some $x$ where $x \in A$, then we can conclude that $x \in B$. All that weâve done here is set up some possible confusion for later on in the case where we do define some variable named $x$.
Think back to Rule Two: Every sentence in a proof should set up a goal, introduce a variable, or combine results together into something new. This sentence doesnât set up a goal. It doesnât introduce a new variable. Itâs just restating the definition of what a subset is. As a result, this sentence probably fails Rule Two and should be cut.
This sentence actually does cause problems later in the proof, specifically in these sentences:
To show this, consider any $x \in A$. Since $x \in A$ and we know that any $x \in A$ must also be an element of $B$, we see that $x â B$.
In the first sentence, we introduce a new variable $x$, which is chosen as an arbitrary element of the set $A$ (that's fine - we're asking the reader to make a choice). You can imagine that the reader is going to look at this and say âokay, Iâm going to pick some specific thing $x$.â In the next sentence, though, the proof talks about âfor any $x \in A$.â Now the reader is going to be confused: âhold on, are you talking about the $x$ that you just asked me to pick in the preceding sentence, or are you talking about some other thing called $x$?â
A good way to think about this: when you tell the reader "consider any $x \in A$," imagine they've picked some concrete value (say, $137$). If you then say "for any $x \in A$, âŠ" it's like saying "for any $137$, ⊠," which just doesn't make any sense.
Another analogy to use: the following code wouldnât be legal in C, C++, or Java:
int x = 137;
int x = 42; // Error!
The issue here is that x
is already defined on the first line, so the second line is a variable redefinition error. If you want to talk about x
going forward, just use its name, not its type:
int x = 137;
x = 42; // Okay!
The same is true of proofs. Phrases like âany $x$,â âevery $x$,â or âany choice of $x$â suggest that youâre introducing some new variable, rather than referring to an existing variable.
A better way to rewrite the above sentences would be to write something like this:
- Before: To show this, consider any $x \in A$. Since $x \in A$ and we know that any $x \in A$ must also be an element of $B$, we see that $x \in B$.
- After: To show this, consider any $x \in A$. Since $x \in A$ and $A \subseteq B$, we see that $x \in B$.
Something to specifically keep an eye out for arises when you switch between telling the reader what youâre going to prove and then actually going and proving it. For example, suppose that you want to prove this claim:
For any sets $A$ and $B$, we have $A \cap B \subseteq A$.
Hereâs a not-so-great way of proving this:
â Incorrect! â Proof: Pick any sets $A$ and $B$. We will show that $A \cap B \subseteq A$ by proving that every $x \in A \cap B$ satisfies $x \in A$. To see this, notice that since $x \in A \cap B$, we know that $x \in A$ and $x \in B$. In particular, this means that $x \in A$, as required. â
Thereâs a subtle but important shift in the meaning of the variable $x$ between the second and third sentences. In the second sentence (âWe will prove that âŠâ), the variable $x$ is a placeholder: it doesnât actually stand for any specific value. In the third sentence (âTo see this, âŠâ), the variable $x$ is being used as though itâs an actual, concrete value. This is a problem, since we donât know precisely what value $x$ has. A better way to write this proof would be to explicitly ask the reader to pick a value for $x$:
Proof: Let $A$ and $B$ be arbitrary sets. We will show that $A \cap B \subseteq A$. To do so, pick an $x \in A \cap B$; we need to show that $x \in A$.
Notice that since $x \in A \cap B$, we know that $x \in A$ and $x \in B$. In particular, this means that $x \in A$, as required. â
Why we enforce this rule: We tend to be fairly strict about this rule, and that can really catch people off-guard who arenât expecting it. So why is that? There are two main reasons.
First, requiring that each variable have a clear, precise, unambiguous meaning tends to markedly improve the precision of the proof. Many mathematical errors arise when talking about how things work âin generalâ or by making overly broad statements about how certain classes of objects work. On the other hand, if youâve singled out some specific object and given it a name, then thereâs no need to make those broad claims. You just need to talk about the specific object that you have, referring to it by the specific name that youâve chosen. From experience, proofs that do not pin things down at this level of detail tend to have more errors and to miss important but subtle details.
Second, this level of precision when speaking about variables requires that you, the writer, have a clear and unambiguous sense of what every term means. Many mistakes in proofs arise from swapping the meaning of one variable for another (for example, using a variable $n$ to refer to two different natural numbers), or confusing a known and unknown quantity (for example, using a variable k that needs to be solved for rather than trying to deduce what it is). Articulating what each variable means makes it harder to make these sorts of mistakes and forces you to slow down as youâre writing to reflect on these details.
Make Specific Claims About Specific Variables
When youâre first learning to write proofs, itâs common to want to write proofs that make broad claims about how things work in general rather than pinning down the specifics. This is best illustrated by example:
Theorem: For any sets $A\text,$ $B\text,$ and $C\text,$ if $A \subseteq B$ and $B \subseteq C\text,$ then $A \subseteq C\text.$
â Incorrect! â Proof: Pick any sets $A\text,$ $B\text,$ and $C$ where $A \subseteq B$ and $B \subseteq C\text.$ We want to show $A \subseteq C\text.$
Since $A \subseteq B\text,$ every element of $A$ is an element of $B\text.$ Since $B \subseteq C\text,$ every element of $B$ is an element of $C\text.$ Therefore, every element of $A$ is an element of $C\text,$ so $A \subseteq C\text,$ which is what we needed to show. $\qed$
The intuition underlying this proof is good, but the way this is written is far too high-level. Specifically, remember that the definition of the statement $A \subseteq C$ is the following:
For every $x\text,$ if $x \in A\text,$ then $x \in C\text.$
In order to prove this claim by calling back to the definition, youâd need to show that if you chose an arbitrary element $x \in A$ that youâd find $x \in C\text.$ The proof given above does not do this. The idea behind it â that anything in $A$ is in $B$ and anything in $B$ is in $C$ â is totally correct, but thatâs not how youâd phrase it in a proof. In proofwriting, if you want to make a claim that something is true in the general case, do so by using arbitrary choices or a proof by contradiction. The above proof would benefit greatly by introducing a variable $x$ that represents some arbitrarily-chosen element of $A\text,$ then tracing it on a magical journey that concludes with a proof that $x \in C\text.$ The lack of that variable $x$ means that the proof repeatedly talks about "every element of $A$" or "every element of $B$" rather than focusing on a specific, precise choice of value.
Why we enforce this rule: This rule â another one that we tend to be fairly strict about â is designed to make sure that youâve properly justified each step of your reasoning by calling back to the appropriate definitions.
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.
Donât Repeat Definitions; Use Them Instead
Mathematical definitions are wonderfully useful. They give us a way to take an intuitive idea like âeven numbersâ and to formalize them in a way that lets us manipulate them in proofs.
Most mathematical proofs will in some way, shape, or form touch on formal definitions. However, you should avoid restating definitions purely in the abstract and instead focus on how those definitions are specifically useful or relevant for what youâre trying to do.
For example, consider the following three (not good) excerpts from three (not good) proofs:
Incorrect Approach 1: We know that $n$ is even. Every even number can be written as twice some integer. Therefore, we see that $n = 2k$ for some integer $k$.
Incorrect Approach 2: We know that $n$ is even. Every even number can be written as $2k$ for some integer $k$. Therefore, we see that $n = 2k$ for some integer $k$.
Incorrect Approach 3: We know that $n$ is even. Every even number $m$ can be written as $m = 2k$ for some integer $k$. Therefore, we know that $n = 2k$ for some integer $k$.
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:
We know $n$ is even, so there is an integer $k$ where $n = 2k$.
"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 can (and should) assume that the person reading the proof 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 options on the left 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?
Why we enforce this rule: In addition to the three factors I just mentioned, there's another reason we enforce this rule: it reduces the space of possible errors you can make. As weâve mentioned earlier, using placeholder variables is an easy way to run into trouble, either by confusing one variable for another or by thinking youâve proved something that you actually havenât. Asking that you apply definitions rather than repeat them reduces the number of placeholder variables you have to work with in your proof, eliminating many potential opportunities for error.
Write In Complete Sentences and Complete Paragraphs
Although proofs exist to convey mathematical arguments, the expectation is that they should be written in grammatically-correct English sentences and in paragraph form.
A good test we recommend applying to your proofs 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:
â Incorrect! â Proof: Since $n$ is even, $n = 2k$. $n^2 = 4k^2$, which is $2(2k^2)$. $2k^2 \in \mathbb{Z}$, so $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 a verb.
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:
â Since $n$ is even, $n$ equals $2k$. â
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 tha $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:
$\because$ $n$ is even, $n = 2k$ for some integer $k$, $\therefore n^2 = 4k^2 = 2(2k^2), \therefore n^2$ is even $\because n^2 = 2m$ for $m = 2k^2$.
This one really, really, really fails the mugga mugga test:
Mugga mugga $n$ is even, mugga mugga for some integer $k$, mugga mmuga, mugga mugga $n^2$ is even mugga mmuga for mugga mugga.
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:
Proof:
- Let $n$ be an even integer.
- Since $n$ is even, we can write $n = 2k$ for some integer $k$.
- Then $n^2 = 4k^2$.
- So $n^2 = 2(2k^2)$.
- Let $m = 2k^2$.
- So $n^2 = 2m$.
- So $n^2$ is even.
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.
Distinguish Between Proofs and Disproofs
The short version of this section goes as follows:
- A proof is an argument that explains why some theorem is true.
- A disproof is an argument that explains why some claim is false.
- Donât write a proof by contradiction when you mean to write a disproof.
Now, the longer version. âș
If you are writing a proof of a result, that result is called a *theorem. The term âtheoremâ specifically refers to a statement that is true under a specific set of assumptions. The general template for writing a proof looks like this:
Theorem: ( statement that you want to prove is true ) Proof: ( some argument establishing why that statement is true )
On the other hand, letâs suppose that you have some statement that is not true, and you want to show that that statement is indeed false. This is called a disproof. Since youâll be showing that a given statement is not true, it is not appropriate to call that statement a âtheorem.â Remember â the term âtheoremâ specifically refers to a statement thatâs true! When youâre writing a disproof, youâd typically refer to the statement in question as a claim (something thatâs being proposed, but which isnât necessarily true) to indicate that the statement should be treated with some suspicion.
The general template for writing a disproof looks like this:
Claim: ( statement that you want to prove is false ) Disproof: ( some argument establishing why that statement is false )
Be very careful not to mix and match the terminology from proofs and disproofs. For example, suppose you want to disprove the (false) claim that if $A$ and $B$ are sets, then $A \cap B = \emptyset$. (Here, this statement is false because itâs implicitly a universally-quantified statement, and there indeed exist pairs of sets with a nonempty intersection). Hereâs how you shouldnât do this:
â Incorrect! â Theorem: If $A$ and $B$ are sets, then $A \cap B = \emptyset$.
â Incorrect! â Proof: We will show that this statement is not true. Consider the sets $A = \mathbb{N}$ and $BÂ =Â \mathbb{N}$. Notice that $A \cap B = \mathbb{N} â© \mathbb{N} = \mathbb{N}$, so $A \cap B \ne \emptyset$. â
The problem with the above setup is that, to a quick glance, it seems like youâre doing exactly the opposite of what youâre actually doing. By labeling the statement as a theorem and the argument as a proof, you are signaling to your reader that you think that the statement is true and that youâre going to provide a justification for it. If they then read your proof, theyâre going to be terribly confused, because youâre starting your proof off by saying that youâre going to show that your theorem â something thatâs supposed to be true â isnât actually true.
A better way to write this would be to do something like this:
Claim: If $A$ and $B$ are sets, then $A \cap B = \emptyset$
Disproof: We will show that the negation of this statement is true, namely, that there exist sets $A$ and $B$ where $A \cap B \ne \emptyset$.
Consider the sets $A = \mathbb{N}$ and $BÂ =Â \mathbb{N}$. Notice that $A \cap B = \mathbb{N} â© \mathbb{N} = \mathbb{N}$, so $A \cap B \ne \emptyset$. â
Take a look at how this argument is laid out. First, the statement in question is marked as a claim, not a theorem, so someone reading over your work will get cued in that youâre simply stating something rather than arguing that itâs true. Next, the argument is explicitly labeled as a disproof, indicating to the reader that theyâre about to see why the claim isnât true. The specifics of that argument then outline a reason why the claim is false â specifically, it says that the negation of the claim is true, then explains why thatâs the case.
Another common error we see people make when writing out disproofs is to mix up two related but different concepts: disproofs (arguments that show why a claim isnât true) and proofs by contradiction (arguments that show that a claim is true by assuming for the sake of argument that it isnât). Although both a disproof and a proof by contradiction will involve working with the negation of a statement, they proceed very differently from one another. In a disproof, you take the negation of the statement in question, then prove that the negation is true. In a proof by contradiction, you assume that the negation is true, derive a contradiction, and then claim that, as a result, the statement must have been true all along. In other words, a disproof explains why something is not true, and a proof by contradiction explains why something is true. As a result, you have to be careful not to mix these concepts up.
For example, hereâs another example of how not to write a disproof:
Claim: If $A$ and $B$ are sets, then $A \cap B = \emptyset$
â Incorrect! â Disproof: Assume for the sake of contradiction that there exist sets $A$ and $B$ where $AÂ \cap B \ne \emptyset$.
Consider the sets $A = \mathbb{N}$ and $BÂ =Â \mathbb{N}$. Notice that $A \cap B = \mathbb{N} â© \mathbb{N} = \mathbb{N}$, so $A \cap B \ne \emptyset$. â
This disproof says that we should start by assuming that the negation of the claim in question here is true. Remember that the whole point of a disproof is to explicitly prove that the negation of the claim is true, so if we start off by assuming the negation of the claim, thereâs nothing left to do!
Why we enforce this rule: This rule is designed to minimize confusion on the part of the person reading your proof. If you are writing a disproof of a result and structure it as though youâre writing a proof of a theorem, the person reading your disproof will go in with completely incorrect expectations about what theyâre going to find. In the best case, a reader will quickly figure this out and begin rereading what you wrote from the top, which isnât the best use of their time. In the worst case, the reader will be totally lost and not understand what it is that youâre trying to do. (Thereâs an even worse case, and thatâs where a TA will look at what you wrote, say âwell, you got the wrong answer, because youâre trying to prove something falseâ and then give you zero points without reading further, but weâll ignore that for now. đ)
Avoid the âContradiction Sandwichâ
Consider the following proof:
Theorem: For any integers $m$ and $n$, if $m$ is even and $n$ is odd, then $m+n$ is odd.
â (Poor Style!) â Proof: Assume for the sake of contradiction that there are integers $m$ and $n$ where $m$ is even, $n$ is odd, but $m+n$ is even. Since $m$ is even, there is an integer $k$ where $m = 2k$. And similarly, since $n$ is odd, we know thereâs an integer $r$ such that $n = 2r + 1$. Then we see that
\[\begin{aligned} m + n & = 2k + 2r + 1 \\ & = 2(k + r) + 1. \end{aligned}\]This means there is an integer $s$ (namely, $k + r$) such that $m + n = 2s + 1$, so $m + n$ is odd. But this is impossible, since earlier we assumed that $m + n$ is even.
Weâve reached a contradiction, so our assumption must have been wrong. Therefore, if $m$ is even and $n$ is odd, then $m + n$ is odd. â
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:
Theorem: For any integers $m$ and $n$, if $m$ is even and $n$ is odd, then $m+n$ is odd.
Proof: (âŠ) Since $m$ is even, there is an integer $k$ where $m = 2k$. And similarly, since $n$ is odd, we know thereâs an integer $r$ such that $n = 2r + 1$. Then we see that
\[\begin{aligned} m + n & = 2k + 2r + 1 \\ & = 2(k + r) + 1. \end{aligned}\]This means there is an integer $s$ (namely, $k + r$) such that $m + n = 2s + 1$, so $m + n$ is odd. (âŠ) â
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:
- Assume, for the sake of contradiction, that the theorem is false.
- Prove the theorem using a direct proof.
- 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.
Why we enforce this rule: A contradiction sandwich is considered poor style because the proof by contradiction doesnât contribute anything needed to the proof. Simply writing the proof as a regular direct proof more directly conveys the line of reasoning and likely requires less total space. Moreover, rereading a proof youâve written to see if itâs a contradiction sandwich is great practice for reviewing your reasoning and making sure there isnât a clearer way to achieve your goal.