This video will start looking at basic methods for proving or disproving claims.

Disproving a universal claim

At the end of the last video, we saw how to disprove a claim by showing a concrete counter-example. We can use a similar method to prove an existential claim. For example:

Claim: There is an integer p such that \(p^2 > 30\) and \(p < 0\).

To prove this, we give a specific example of an integer and briefly explain why it has the required properties. For example:

Proof: Consider \( p = -10\). \(p < 0\). Also \(p^2 = (10)^2 = 100 > 30\).

It is best to use an example that is as specific as possible. Pick an example for which the reader can easily verify the required properties. But the example does not have to be the smallest or the simplest one possible. For example, \(p=-100\) would have worked just as well.

You can also pick silly examples, as long as they are easy for the reader to verify. For example, we could choose \(p = -1347\). Then clearly \(p^2 \ge 10^2 = 100 > 30\).

You do not need to provide a general description of all possible examples. This is often much harder to do correctly. It's harder for the reader to verify. And it's completely unnecesary, because the claim only says that there is at least one example.

Methods of proof

When writing a proof, there are four different situations, shown in the table below. We can prove an existential claim by showing a concrete example. We can disprove a universal claim by showing a concrete counter-example. The other two situations require a general argument that works for any input value.

Direct proof of universal claim

Consider this claim:

Claim: For any real numbers p,q, if p,q are rational, then p+q is rational.

Notice that we have a universal claim consisting of an if/then statement. The standard "direct proof" outline is to introduce the variables, then assume the information in the hypothesis, and reason from there to the conclusion. For our claim, this would look like:

Proof: Let p,q be real numbers.
Suppose p,q are rational.
....
So p+q is rational.

Notice that we've written out our goal for the end of the proof. It's important to write this down, so that you remember where you are headed when you're writing the middle of the proof. Write your goal where you can't mistake it for a fact that is known at the start of the proof. For example, write it at the bottom of your answer area. Some people write it to the side or on scratch paper.

You've probably watched instructors write proofs entirely in forwards order. This is because they already know how to do the proof and they are keeping the end goal in their head. So it's not a good model for doing a proof as a beginner, or a harder proof even when you are experienced.

Now we need to fill in the middle part of the proof. Very soon, we will be proving claims about unfamiliar concepts. But we haven't introduced any yet. So let's pretend that we know a lot about integers but don't yet know much about rational numbers. That's why we're trying to prove this very basic "closure" fact about the rationals.

To fill in the middle of this proof, we need a definition of "rational." Here's our textbook definition of "rational":

Definition: A real number x is rational if and only if it can be written as \(x=\frac{n}{m}\) where m and n are integers and m is not zero.

Let's use this definition to rewrite the two statements involving "rational" in terms of basic arithmetic.

Proof: Let p,q be real numbers.
Suppose p,q are rational.
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
...
So \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
So p+q is rational.

We used the definition of rational in three places. The first time, it happened that we could use the original variable names from the definition (n and m). However, we can't re-use these variable names when we do the other two substitutions. For example, if we wrote the following, we would be forcing p and q to be equal. That can't be right, because our claim was about any pair of rational numbers p and q.

\(p = \frac{n}{m}\), where n,m are integers, m non-zero.
\(q = \frac{n}{m}\), where n,m are integers, m non-zero.

Let's try to finish filling in the proof. Notice that our goal at the end of the gap involves finding a value for p+q. So let's try adding p and q, and see what we get.

...
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
Then \( p+q = \frac{n}{m} + \frac{j}{k} = \frac{nk+jm}{mk} \)
...
So if we set \(s=nk+jm\) and \(t = mk\), then \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
...

Now we clean up the details. There's a bit of missing reasoning in the middle, because we need to justify why s and t are integers, and t is non-zero. To do this, we'll use closure properties of the integers: adding two integers produces an integer, multiplying two non-zero integers produces a non-zero integer. Here's our final proof:

Proof: Let p,q be real numbers.
Suppose p,q are rational.
Then \(p = \frac{n}{m}\), where n,m are integers, m non-zero.
Similarly \(q = \frac{j}{k}\), where j,k are integers, k non-zero.
Then \( p+q = \frac{n}{m} + \frac{j}{k} = \frac{nk+jm}{mk} \)
\(nk + jm\) is an integer because n,k,j,m are integers
mk is an integer because m,k are integers.
mk is not zero because m,k are non-zero
So if we set \(s=nk+jm\) and \(t = mk\), then \(p+q = \frac{s}{t}\) where s,t integers, t non-zero
So p+q is rational.

Disproof of existential example

The final situation to consider is disproving an existential example. In this case, we need to provide a general argument. Usually this is presented as rephrasing "disproving the claim" as "proving the negation of the claim."

Consider this example:

Claim: There is an integer k such that \(k^2 + 2k + 1 < 0\).

Let's negate the claim:

Negation of claim: for all integers, \(k^2 + 2k + 1 \ge 0\).

To set up our proof, we first tell the reader that we're switching to proving the negation of the claim, and then set up the standard outline for a direct proof:

Disproof of (original) claim: We will disprove the claim by proving its negation, which is

For all integers, \(k^2 + 2k + 1 \ge 0\).

So let k be an integer.
...
So \(k^2 + 2k + 1 \ge 0\).

When you use an outline other than a simple direct proof, it's important to tell the reader what you are planning. In a later math/theory class, we might just say that we're proving the negation. In this class, you will need to write out the negation, because it's still easy for you to make mistakes constructing it.

We now have our outline. But how will we get to the conclusion? All we know is that k is an integer. We'll use an important trick: working backwards on scratch paper. Your final proof needs to be written in logical order. But your scratch work can be more free-form.

On our scratch paper:
What is this \(k^2 + 2k + 1 \)?
Oh, yeah, it's the square of \(k+1\). Squares can't be negative.

Now that we understand our argument, let's rewrite it in logical order:

Consider \(k+1\).
\((k+1)^2 \ge 0\) because squares of real numbers are never negative.
But \((k+1)^2 = k^2 + 2k + 1\).
So \(k^2 + 2k + 1 \ge 0\).

Notice the word "consider." It often appears in mathematical writing when the next step may seem unmotivated because a section of the proof was constructed backwards.

Our full draft proof:

Disproof of (original) claim: We will disprove the claim by proving its negation, which is

For all integers, \(k^2 + 2k + 1 >= 0\).

So let k be an integer.
Consider k+1.
\((k+1)^2 \ge 0\) because squares of real numbers are never negative.
But \((k+1)^2 = k^2 + 2k + 1\).
So \(k^2 + 2k + 1 \ge 0\).

Let's polish this up a bit more. Professional looking proofs are written as paragraphs. And we often end them with a statement indicating that we're done. So our final proof looks like:

Disproof of (original) claim: We will disprove the claim by proving its negation, which is

For all integers, \(k^2 + 2k + 1 \ge 0\).

So let k be an integer. Consider k+1. \((k+1)^2 \ge 0\) because squares of real numbers are never negative. But \((k+1)^2 = k^2 + 2k + 1\). So \(k^2 + 2k + 1 \ge 0\). This is what we needed to show.

We could have replaced "This is what we needed to show" with "QED." QED is simply an abbreviation of the Latin translation of "What we needed to show." Some people use a small box at the end of their proof. And sometimes the end of a proof is indicated in other ways, e.g. by indenting in typed text or because the proof is the only thing in an exam answer box.