Guide to Proofs


Writing mathematical proofs is a skill that combines both creative problem-solving and standardized, formal writing. When you’re first learning to write proofs, this can seem like a lot to take in. However, there are certain patterns in proof writing that, once internalized, make the whole endeavor a lot easier. This page covers those patterns and is designed to help you take your first steps into Theoryland.

Direct Proofs: Implications

Implications are one of the most common types of statements you’ll encounter when writing mathematical proofs. As a reminder, an implication is a statement of the form

If $P$ is true, then $Q$ is true.

As a reminder, the antecedent of this implication is the statement “$P$ is true,” and the consequent of this implication is the statement “$Q$ is true.” For example, all of the following are implications:

If $n$ is an even integer, then $n^2$ is even.

If $m \in \mathbb{N}$, then there is a positive integer $n$ where $m^2 + mn$ is a perfect square.

If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Take a minute to confirm that you can identify the antecedents and consequents of these implications.

Because implications are so common, writing direct proofs of implications is fairly common as well. While the particulars of how to prove any individual implication vary, the good news is that all these proofs more or less follow the same basic structure. Specifically, you assume the antecedent is true, and then you prove the consequent is true. And indeed, that’s so core to how to prove implications using a direct proof that you can actually make progress on writing a proof of any implication even if you have no idea why the implication is true.

For example, let’s take the following (nonsense) implication:

If $x$ is a pizkwat, then $x$ is a squigglebah.

Even if we have no idea what a pizkwat or squigglebah are (spoiler: these aren’t real things), we could still start off a proof of this statement. Here’s what one might look like:

Proof: Assume that $x$ is a pizkwat. We need to show that $x$ is a squigglebah. […]

How do we know to do this? Well, if we want to prove this implication via a direct proof, we need to tell the reader to (1) we’re assuming the antecedent is true, and (2) we’re going to somehow establish that the consequent is true.

We call the first part of this proof (“Assume that $x$ is a pizkwat”) the assume step and the second part of this proof (“We need to show that $x$ is a squigglebah”) the want-to-show. The idea is that we’re making some assumption in the assume step, and our want-to-show now becomes the thing we need to prove with the rest of the argument.

When you’re first getting started writing proofs, we recommend wording things along the lines of what we’ve shown above. However, there are other equivalent ways of expressing this same idea. Here are some alternatives. Make sure you see why each of these says the same thing as what we’ve written above.

Proof (Alternate): Suppose $x$ is a pizkwat. We need to prove $x$ is a squigglebah. […]

Proof (Alternate): Let $x$ be a pizkwat. We’ll show that $x$ is also a squigglebah. […]

But regardless of what specific wording you use, the important thing is to

  1. clearly state to your reader that you are assuming the antecedent is true, and
  2. that you are going to prove that the consequent is true.

As in the case of this silly implication with pizkwats and squigglebahs, this applies even in the case where the implication is sufficiently complex that you don’t yet know why it’s true.

After we’ve written out the assume and want-to-show steps, we need to provide some line of reasoning that proves the want-to-show is true. In the case of the silly proof about pizkwats and squigglebahs, we’d need to show that x is indeed a squigglebah. Once we’ve done that, we can just tell the reader “hey, I did the thing I said I was going to do” and call it a day. That might look like this:

Proof: Assume that $x$ is a pizkwat. We need to show that $x$ is a squigglebah.

(the actual logic of the proof goes here)

This means that $x$ is a squigglebah, which is what we needed to show. â– 

This last sentence therefore closes off the narrative arc. Our want-to-show told the reader that we’re done once we show $x$ is a squigglebah. Therefore, once we’ve done that, we can say “just like I promised!” and call it a day. Of course, the specific wording here isn’t required. Here’s another way we could do this:

Proof (Alternate): Suppose $x$ is a pizkwat. We will prove $x$ is a squigglebah.

(the actual logic of the proof goes here)

Thus $x$ is a squigglebah, as required. â– 

To summarize, to prove an implication, do the following:

  1. Write your assume step. This is where you assume the antecedent is true.
  2. Write your want-to-show step. This is where you say that you will show the consequent is true.
  3. Write the actual reasoning. Manipulate what you’re given in your assume step until you arrive at the claim you made in your want-to-show step. This is the creative part of the proof.
  4. Return to your want-to-show. Indicate to the reader that you ended up where you said you were going to end up, and end the proof with a nice â–  symbol.

As an (optional, not graded) exercise, try applying this rule to start off proofs of the following statements. As in the above cases, your goal isn’t to write the full proof. Instead, just write the first sentence or two, along with the last sentence.

  1. If the Riemann Hypothesis is true, then P = NP. (These are real mathematical terms. We have no reason to believe that they’re related.)

  1. If every peganil number is also a retract, then each requint is wobbly. (These are nonsense terms. I made them up because they sound funny.)

  1. If $M$ is a TM that halts on a string $w$, then $U_{TM}$ accepts $\langle M, w \rangle$. (You'll know what this means later in the quarter!)

Direct Proofs: Universally-Quantified Statements

A universally-quantified statement is a statement that makes a claim about all objects of some type. Here are some examples:

For any integer $n$, the number $n(n + 1)$ is even.

For every set $S$, we have $\vert S \vert \lt \vert \wp(S) \vert$.

This first statement says something about all integers, and the second statement talks about all sets.

You might notice that these statements give a name to one of the objects being discussed. That first one talks about “for any integer $n$” and then goes on to use $n$ as a placeholder meaning “some integer,” while the second one talks about “for every set $S$,” allowing $S$ later on to refer back to some set. More generally, each universally-quantified statement will consist of two parts:

  • A placeholder variable representing an object of some type.
  • A claim about that placeholder variable that is true regardless of the choice made.

In some cases, you might not explicitly see a placeholder variable. For example, consider this universally-quantified statement:

Every natural number can be written as the sum of four perfect squares.

While this version doesn’t have a placeholder, we can easily add one in:

Every natural number $n$ can be written as the sum of four perfect squares.

The general pattern for proving a universally-quantified statement with a direct proof is as follows:

  1. Instruct the reader to pick an arbitrary object of the appropriate type and give it a name.
  2. Prove the object the reader has picked necessarily has the required property.

For example, let’s look at the most recent universally-quantified statement, the one about sums of four perfect squares. We could start off a proof of that result like this:

Theorem: Every natural number $n$ can be written as the sum of four perfect squares.

Proof: Pick a natural number $n$. We want to show that $n$ can be written as the sum of four perfect squares. […]

Let’s break down why this is written this way. We’ll begin with the first sentence (“Pick a natural number $n$.”) Why are we asking the reader to pick a natural number $n$? This convention has two purposes. First, it indicates that you, the person writing the proof, are not actually selecting any specific natural number to reason about. Instead, you’re telling the person reading your proof that they have full control here. They could choose $n$ to be whatever it is that they want it to be, with the tacit understanding that it’s not going to matter and that you’ll prove $n$ has some nice property regardless of that choice. Second, it gives a concrete meaning to the variable name $n$. In the statement of the theorem, the variable $n$ doesn’t actually refer to anything. It’s a placeholder for “whatever number you want it to be.” Therefore, to use $n$ in the proof, we need to ensure that $n$ is given some specific meaning so that its value can’t change from sentence to sentence.

As a note, “pick a natural number $n$” is not the only way to write this out. All of the following work just as well here:

  • Consider a natural number $n$.
  • Let $n \in \mathbb{N}$ be an arbitrary natural number.
  • Fix some $n \in \mathbb{N}$. (Note: “fix” here means “pin down,” not “repair.”)
  • Choose some $n \in \mathbb{N}$.

Now, let’s look at the next sentence (“We want to show that […]”). This sentence articulates what our new goal is – all we have to do to get the proof to work is show that this value $n$ that the reader picked can be written as the sum of four squares. Although the statement we’re proving, as written, isn’t an implication, this sentence functions as a “want-to-show” step for the rest of the proof. Once you have established the claim you’ve made here, you’re done, and the proof is over. So, for example, the general shape of the proof here should look like this:

Theorem: Every natural number $n$ can be written as the sum of four perfect squares.

Proof: Pick a natural number $n$. We want to show that $n$ can be written as the sum of four perfect squares.

( the actual logic of the proof goes here )

Thus $n$ is the sum of four perfect squares, as required. â– 

To summarize, a proof of a universally-quantified statement proceeds in these steps:

  1. Tell the reader to make an arbitrary choice. This is where you introduce a variable representing some value that the reader gets to pick. Importantly, state what the name of the variable is, and clearly indicate that you as the proof writer aren’t telling the reader which specific choice to make.
  2. State your want-to-show. This will be that the variable introduced in the previous sentence has some specific property.
  3. Write the actual reasoning. This is where you use properties common to the type of object being chosen to arrive at the destination. It’s the creative step of the proof.
  4. Call back to your want-to-show. Once you’ve arrived at the statement you said you were going to arrive at, you’re done! Point that out and draw a nice box.

The general shape of your proof will look like this even if you don’t know the specifics of why it’s true. As another (optional, not graded) exercise, take the statements shown here and sketch out what the shape of the proof might look like.

  1. For every NFA $N$, there is a DFA $D$ where ${\scr{L}}(N) = {\scr{L}}(D)$. (You'll learn what this means later this quarter!)

  1. For every integer $n$, there are integers $r$ and $s$ where $r^2 - s^2 = 4n$. (Great exercise!)

  1. Every Siegel field has a cofinal attractor. (These are mathy-sounding terms I made up. They aren’t real things.)

For that last one – remember that if you don’t see a named variable in the universally-quantified statement, it’s probably a good idea to rewrite the statement to add one.

Unpacking Compound Statements

It’s common to see statements that combine together a universally-quantified statement and an implication. For example, take this statement:

For any integer $n$, if $n$ is even, then $n^2$ is even.

This statement is a mix of a universally-quantified statement on the outside and an implication on the inside. You can see this here:

\[\begin{aligned} &\text{For all integers }n, && \text{(a universally-quantified statement)} \\ &\quad\text{if }n\text{ is even,} && \text{(the antecedent of an implication)} \\ &\quad\quad\text{then }n^2\text{ is even.} && \text{(the consequent of an implication)} \end{aligned}\]

So – how should we prove this? If we follow the template for a universally-quantified statement, we’d write out the following:

Proof: Pick an integer $n$. We will show that if $n$ is even, then $n^2$ is even. […] ■

Notice that our want-to-show here is itself an implication, and our goal is now to prove the want-to-show. So we can then ask – how do you prove an implication? Well, we saw that earlier as well: you assume the antecedent and prove the consequent. That looks like this:

Proof: Pick an integer $n$. We will show that if $n$ is even, then $n^2$ is even. To do so, assume $n$ is even. We need to show that $n^2$ is even.

( the actual logic of the proof goes here )

Thus $n^2$ is even, as required. â– 

Notice what we did here. Immediately after our initial want-to-show, we said that we are going to assume $n$ is even (assuming the antecedent of our implication) and then show that $n^2$ is even (making the consequent of our implication the new want-to-show). From this point, all we have to do is prove that $n^2$ is even, and we’re done.

This pattern – writing out an initial want-to-show and then expanding that out into another want-to-show – is something we call unpacking. You can think of it as breaking a larger problem down into some simpler pieces. The original, big goal is “prove a universally-quantified statement.” We simplified that to “prove an implication.” We’ve reduced further to “prove $n^2$ is even.” We’re therefore “unpacking” our want-to-show statement to reveal the smaller pieces it’s made of.

In the specific case of a universally-quantified implication (“for any $x$, if $P$ is true, then $Q$ is true”), it’s often a bit easier to combine the introduction of the variable from the quantified bit and the assumption from the antecedent. For example, the above proof could also be written in the following way:

Proof: Pick an even integer $n$. We will show that $n^2$ is even.

( the actual logic of the proof goes here )

Thus $n^2$ is even, as required. â– 

This means exactly the same thing as what was shown above, since in both cases we end up with $n$ being (1) an integer (2) whose value we don’t control and (3) that is even.

As another example, consider this (nonsense) implication:

For any woozle $x$, if $x$ is cretacular, then $x$ is whiphithi.

We could unpack this as follows:

Theorem: For any woozle $x$, if $x$ is cretacular, then $x$ is whiphithi. Proof: Consider some cretacular woozle $x$. We need to show that $x$ is whiphithi.

( the actual logic of the proof goes here )

Therefore $x$ is whiphithi, as required. â– 

Take a minute to look back at the statement of the theorem. How did we get from there to our assume step? How did we get from there to our want-to-show step? And, importantly, note that we don’t have to have even the faintest inkling of what these terms mean to get to this point in the reasoning.

Based on what you’ve seen here, try setting up proofs of the following statements. Again, you aren’t required to do so, and it’s not graded, but it is great practice.

  1. For all languages $L$, if $L$ is regular, then $\bar{L}$ is regular. (You’ll understand this by Week 7.)

  1. For any rectible integer $x$, if $x$ is Egan-prime, then $G[x, 2]$ is unobserved. (These are mathy-sounding terms that I made up and have no basis in reality.)

  1. For any integers $x$, $y$, and $z$, if $x^2 + y^2 = z^2$, then $(x+1)^2 + (y+1)^2 \ne (z + 1)^2$. (This is actually a great problem to try on your own!)

Direct Proofs; Existentially-Quantified Statements

An existentially-quantified statement is one that states that there is at least one object with some property. As opposed to universal statements, which say that something is always true, an existential statement just says that it’s true at least once.

For example, here are some sample existential statements:

There is a positive integer $n$ equal to the sum of all smaller positive integers. There is a one-state NFA $N$ that does not accept all strings.

As with universally-quantified statements, an existentially-quantified statement consists of two pieces:

  • A placeholder variable representing an object of some type.
  • A claim about that placeholder variable that is true for at least one choice of that variable.

As with universally-quantified statements, some existentially-quantified statements don’t explicitly include a variable. In that case, you can just add one in. For example, take this (nonsense) statement:

There is a swipestone that is edurable.

We could rewrite this as

There is a swipestone $x$ such that $x$ is edurable.

Because existentially-quantified statements claim that some object exists with some property, the general pattern for proving an existentially-quantified statement with a direct proof is to simply find what that object is and then prove it indeed has the needed properties. You typically do this by writing something to this effect:

Theorem: There is a swipestone $x$ such that $x$ is edurable. Proof: Pick $x = \blank$. We need to show that $x$ is a swipestone and $x$ is edurable.

( the actual proof that $x$ has those properties )

Thus $x$ is an edurable swipestone, as required. â– 

The key difference between this style of proof and a proof of a universally-quantified statement is that, in this case, we are specifically telling the reader what object we’re picking. We very specifically do not want to tell the reader “pick anything you’d like here,” because chances are the claim isn’t going to be true for most choices!

Things get most interesting when you combine together a universally-quantified statement and an existentially-quantified statement. For example, consider this statement:

For any integer $n$, there are integers $r$ and $s$ where $r^2 - s^2 = 4n$.

Notice how this is structured:

\[\begin{aligned} &\text{For all integers }n, && \text{(a universally-quantified statement)} \\ &\quad \text{there are integers }r\text{ and }s\text{ where }r^2 - s^2 = 4n && \text{(an existentially-quantified statement)} \end{aligned}\]

Since we have one statement nested inside another, we will have to unpack as we go. We’ll begin by writing out our general template for a universally-quantified statement:

Proof: Pick some integer $n$. We want to show that there are integers $r$ and $s$ where $r^2 - s^2 = 4n$.

( the actual logic goes here )

Thus $r^2 - s^2 = 4n$, as required. â– 

Now, what will that actual logic look like? This is where we need to get creative and actually find choices of $r$ and $s$ that work here. But even if we don’t know what the ultimate choices of $r$ and $s$ will be, we can still outline the rest of the proof. It will look something like this:

Proof: Pick some integer $n$. We want to show that there are integers $r$ and $s$ where $r^2 - s^2 = 4n$.

Pick $r = \blank$ and $s = \blank$. We then see that

( some proof that $r^2 - s^2 = 4n$ )

Thus $r^2 - s^2 = 4n$, as required. â– 

A great exercise: what choices of $r$ and $s$ should you make here?

Direct Proofs: Biconditionals

A biconditional is a statement of the form

$P$ is true if and only if $Q$ is true.

In other words, it's a statement that says "whenever $P$ is true $Q$ is true, and whenever $Q$ is true $P$ is true." For example, we might have something like one of these statements:

If $n$ is an integer, then $n$ is even if and only if $n^2$ is even.

There is a DFA $D$ for a language $L$ if and only if there is an NFA $N$ for language $L$.

Statements like these say that two things are equivalent to one another - the expression on the right means the exact same thing as the expression on the left.

How do you prove a biconditional statement? Well, if you think about it, a biconditional consists of two separate implications. The statement

$P$ is true if and only if $Q$ is true

is equivalent to

If $P$ is true then $Q$ is true, and if $Q$ is true then $P$ is true.

Because a biconditional essentially boils down to two separate and smaller implications, the general strategy for proving a biconditional is to write out two separate proofs, one for each of the two implications.

To see what this looks like, let's take this (nonsense) biconditional:

For any $x$, $x$ is spirocontractive if and only if $x$ is chiroshrinking.

Here's how we might set up a proof of that result:

Proof: Pick an arbitrary $x$. We will prove both directions of implication.

First, we will prove that if $x$ is spirocontractive, then $x$ is chiroshrinking. (Insert a proof of that implication here. You can do this directly by then assuming the antecedent and proving the consequent, or using the contrapositive, or using a proof by contradiction, whichever floats your boat.)

Next, we will prove that if $x$ is chiroshrinking, then $x$ is spirocontractive. (Insert a proof of that implication here. As above, you can prove this using whatever technique you'd like.) â– 

In other words, it's basically two proofs of two separate implications, essentially glued together one after the other.

Proof by Contrapositive

(Covered in Lecture 02)

Sometimes, when proving an implication, you’ll find that your reasoning via a direct proof is getting messy and complicated, or you’ll just flat-out get stuck and unable to make progress. If that happens, save what you have somewhere, and then try instead to write a proof by contrapositive.

In a proof by contrapositive, instead of proving the original implication, you'll prove a different implication. Specifically, instead of proving the statement

If $P$ is true, then $Q$ is true,

you'll prove the statement

If $Q$ is false, then $P$ is false.

This second statement is called the contrapositive of the first statement, hence “proof by contrapositive.”

When writing a proof by contrapositive, we recommend structuring the proof as follows:

  1. Start off by announcing that you're going to prove the contrapositive of the statement you wish to prove. For example, you could say something like “We will prove the contrapositive of this statement, namely, that …” or “By contrapositive; we will instead prove that …”

    Don't skip this step! It's important for several reasons. First, it communicates to the reader what they should expect in the proof: you're not going to prove the original statement, and instead that you're going to prove the contrapositive. Second, it forces you to write out the contrapositive of the statement that you're trying to prove, reducing the likelihood that you accidentally take the contrapositive incorrectly.

  2. Using any proof technique you'd like, prove the contrapositive of the statement. Often, you'll prove the contrapositive of the statement using a direct proof. Overall, this means that if you want to prove the statement “If P is true, then Q is true,” you'll start off by assuming that Q is false and will prove that P is false.

Proof by contrapositive is useful for proving implications, but can also be used to prove certain other results that don't necessarily look like implications. For example, consider this (nonsense) statement:

All omnesiacs are amniscient.

This statement doesn't look like an implication, but it can actually be thought of as one. Specifically, it's equivalent to the statement

For all $x$, if $x$ is an omnesiac, then $x$ is amniscient.

Now, it's clearer that there's an implication here, so if we chose to do so, we could prove it using a proof by contrapositive. That proof might start out like this:

Proof: We will prove that if $x$ is an omnesiac, then $x$ is amniscient. To do so, we will instead prove the contrapositive, that if $x$ is not amniscient, then $x$ is not an amnesiac.

Pick any $x$ that is not amniscient. We want to show that $x$ is not an omnesiac.

( the actual logic goes here )

So $x$ is not an omnesiac, as required. â– 

Proof by Contradiction

(Covered in Lecture 02)

One of the most common and most powerful forms of indirect proof is the proof by contradiction. In a proof by contradiction, to prove that some statement $X$ is true, you instead assume that $X$ is false, then proceed to derive an impossible statement (a contradiction). This means that $X$ cannot be false, and therefore $X$ has to be true.

We recommend writing proofs by contradiction along these lines:

  1. Start off by saying that you're going to write a proof by contradiction. For example, you could write “Assume for the sake of contradiction that …” or “By contradiction; assume that ….” Then, explicitly write out the negation of the statement you're trying to prove.

    Analogously to a proof by contrapositive, it's important to actually write out the negation of what you want to prove. This communicates to the reader what assumptions you're making and forces you to put into writing what you believe the negation of the statement is. It therefore makes the proof easier to read and reduces the chances that you accidentally take the negation of the statement incorrectly.

  2. Starting with your assumption from part (1), proceed to conclude something impossible, such as that $1 = 0$, that a number is both even and odd, that something is an element of the empty set, that $\vert S \vert = \vert \wp(S) \vert$, etc.

  3. State that you've reached a contradiction and, if it's not obvious, explain why it's a logical contradiction. This explains to the reader why your assumption couldn't possibly be right.

  4. Conclude the proof. I commonly say something to the effect of “We have reached a contradiction, so our assumption must have been wrong, so […].” You can put whatever you'd like here as long as it explains why the contradiction you arrived at actually shows that the original assumption was incorrect.

One of the trickiest parts of writing a proof by contradiction is properly assuming the opposite of what you want to prove. When we talk about first-order logic later in a few weeks, you'll see several techniques for negating statements and you'll get a better feel for how to do this in general. For now, though, we recommend that you use the following set of rules and your own intuition.

Here are some common types of statements and their negations.

\[\begin{array}{c | c} \textbf{If you want to prove this by contradiction...} & \textbf{... assume this.} \\ \hline \text{All }P\text{'s are }Q\text{'s} & \text{Some }P\text{ is not a }Q \\ \hline \text{No }P\text{'s are }Q\text{'s} & \text{Some }P\text{ is a }Q \\ \hline \text{Some }P\text{'s are }Q\text{'s} & \text{All }P\text{'s are not }Q\text{'s} \\ \hline \text{Some }P\text{ is not a }Q & \text{All }P\text{'s are }Q\text{'s} \\ \hline \text{If }P\text{ is true, then }Q\text{ is true} & P\text{ is true and }Q\text{ is false} \\ \hline P\text{ is true and }Q\text{ is true} & P\text{ is false, or }Q\text{ is false, or both are false} \\ \hline P\text{ is true, }Q\text{ is true, or both are true} & P\text{ is false and }Q\text{ is false} \\ \end{array}\]