Proofs

Section 1.4 Proofs

Subsection Introduction

Investigate!

Decide which of the following are valid proofs of the following statement:

If $a b$ is an even number, then $a$ or $b$ is even.

Suppose $a$ and $b$ are odd. That is, $a=2k+1$ and $b=2m+1$ for some integers $k$ and $m\text{.}$ Then

\begin{align*} ab \amp =(2k+1)(2m+1)\\ \amp =4km+2k+2m+1\\ \amp =2(2km+k+m)+1\text{.} \end{align*}

Therefore $ab$ is odd.
Assume that $a$ or $b$ is even - say it is $a$ (the case where $b$ is even will be identical). That is, $a=2k$ for some integer $k\text{.}$ Then

\begin{align*} ab \amp =(2k)b\\ \amp =2(kb)\text{.} \end{align*}

Thus $ab$ is even.
Suppose that $ab$ is even but $a$ and $b$ are both odd. Namely, $ab = 2n\text{,}$ $a=2k+1$ and $b=2j+1$ for some integers $n\text{,}$ $k\text{,}$ and $j\text{.}$ Then

\begin{align*} 2n \amp =(2k+1)(2j+1)\\ 2n \amp =4kj+2k+2j+1\\ n \amp = 2kj+k+j+\frac{1}{2}\text{.} \end{align*}

But since $2kj+k+j$ is an integer, this says that the integer $n$ is equal to a non-integer, which is impossible.
Let $ab$ be an even number, say $ab=2n\text{,}$ and $a$ be an odd number, say $a=2k+1\text{.}$

\begin{align*} ab \amp =(2k+1)b\\ 2n \amp =2kb+b\\ 2n-2kb\amp =b\\ 2(n-kb)\amp =b\text{.} \end{align*}

Therefore $b$ must be even.

Checkpoint 1.4.1.

After reading the Investigate! activity above, which of the four proofs do you think are valid? Which do you think are valid proofs of the statement they claim to prove? Briefly explain your thinking.

Anyone who doesn’t believe there is creativity in mathematics clearly has not tried to write proofs. Finding a way to convince the world that a particular statement is necessarily true is a mighty undertaking and can often be quite challenging. There is not a guaranteed path to success in the search for proofs. For example, in the summer of 1742, a German mathematician by the name of Christian Goldbach wondered whether every even integer greater than 2 could be written as the sum of two primes. Centuries later, we still don’t have a proof of this apparent fact (computers have checked that “Goldbach’s Conjecture” holds for all numbers less than $4\times 10^{18}\text{,}$ which leaves only infinitely many more numbers to check).

Writing proofs is a bit of an art. Like any art, to be truly great at it, you need some sort of inspiration, as well as some foundational technique. Just as musicians can learn proper fingering, and painters can learn the proper way to hold a brush, we can look at the proper way to construct arguments. A good place to start might be to study a classic.

Theorem 1.4.2.

There are infinitely many primes.

Proof.

Suppose this were not the case. That is, suppose there are only finitely many primes. Then there must be a last, largest prime, call it $p\text{.}$ Consider the number

\begin{equation*} N = p! + 1 = (p \cdot (p-1) \cdot \cdots 3\cdot 2 \cdot 1) + 1\text{.} \end{equation*}

Now $N$ is certainly larger than $p\text{.}$ Also, $N$ is not divisible by any number less than or equal to $p\text{,}$ since every number less than or equal to $p$ divides $p!\text{.}$ Thus the prime factorization of $N$ contains prime numbers (possibly just $N$ itself) all greater than $p\text{.}$ So $p$ is not the largest prime, a contradiction. Therefore there are infinitely many primes.

This proof is an example of a proof by contradiction, one of the standard styles of mathematical proof. First and foremost, the proof is an argument. It contains sequence of statements, the last being the conclusion which follows from the previous statements. The argument is valid so the conclusion must be true if the premises are true. Let’s go through the proof line by line.

Suppose there are only finitely many primes. [this is a premise. Note the use of “suppose.”]
There must be a largest prime, call it $p\text{.}$ [follows from line 1, by the definition of “finitely many.”]
Let $N = p! + 1\text{.}$ [basically just notation, although this is the inspired part of the proof; looking at $p! + 1$ is the key insight.]
$N$ is larger than $p\text{.}$ [by the definition of $p!$]
$N$ is not divisible by any number less than or equal to $p$ . [by definition, $p!$ is divisible by each number less than or equal to $p\text{,}$ so $p! + 1$ is not.]
The prime factorization of $N$ contains prime numbers greater than $p\text{.}$ [since $N$ is divisible by each prime number in the prime factorization of $N\text{,}$ and by line 5.]
Therefore $p$ is not the largest prime. [by line 6, $N$ is divisible by a prime larger than $p\text{.}$]
This is a contradiction. [from line 2 and line 7: the largest prime is $p$ and there is a prime larger than $p\text{.}$]
Therefore there are infinitely many primes. [from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.]

We should say a bit more about the last line. Up through line 8, we have a valid argument with the premise “there are only finitely many primes” and the conclusion “there is a prime larger than the largest prime.” This is a valid argument as each line follows from previous lines. So if the premises are true, then the conclusion must be true. However, the conclusion is NOT true. The only way out: the premise must be false.

The sort of line-by-line analysis we did above is a great way to really understand what is going on. Whenever you come across a proof in a textbook, you really should make sure you understand what each line is saying and why it is true.

Thinking about the proof as a whole, we can analyze the proof through two distinct but intersecting lenses. First, we can think about the logical structure of the proof. Recognizing the above proof as a proof by contradiction is an example of this. Second, we can look at the mathematical content of the proof. How does the proof illustrate understanding of mathematical concepts? Does it use definitions of mathematical objects correctly? How do the definitions interact with each other? Recall that in Section 1.2 we said that a tautology is a necessarily true statement, but doesn’t tell us anything interesting. Similarly, if a proof relied entirely on the logical form of the statement it was proving, it wouldn’t tell us anything interesting about mathematics. Thus all the proofs we consider must involve some combining of mathematical concepts in addition to their logical structure.

In this section will will see examples of how the interaction between logical and mathematical structure plays out. We will think of the logical structure as the skeleton or scaffolding of the proof, and look at the different shapes this skeleton can take. We will then see how the mathematical content of the proof fills in the details of the skeleton; how it adds meat to the bones.

Objectives

After completing this section, you should be able to do the following.

Identify the logical structure of, and distinguish between, direct proofs, a proof by contrapositives and a proof by contradictions.
Identify flaws in a incorrect proof and determine whether they are flaws in logic or mathematical concepts.
Apply definitions of mathematical objects to prove statements using basic proof styles.

Subsection Direct Proof

The simplest (from a logic perspective) style of proof is a direct proof. Often all that is required to prove something is a systematic explanation of what everything means. You look at the definitions, carefully explain and unpack their meaning, until you see that the conclusion is true.

To see where to start a direct proof, it is useful to express the statement you are proving as an implication. The general format to prove $P \imp Q$ is this:

Assume $P\text{.}$ Explain, explain, …, explain. Therefore $Q\text{.}$

For example, if we wanted to prove that, “all squares are rectangles,”, first realize that this is the same as saying, “for any shape, if the shape is a square, then it is a rectangle.” In symbols, $\forall x (S(x) \imp R(x))\text{.}$ Often we want to prove universal statements, perhaps of the form $\forall x (P(x) \imp Q(x))\text{.}$ Again, we will want to assume $P(x)$ is true and deduce $Q(x)\text{.}$ But what about the $x\text{?}$ We want this to work for all $x\text{.}$ We accomplish this by fixing $x$ to be an arbitrary element (of the sort we are interested in).

Here are a few examples. First, we will set up the proof structure for a direct proof, then fill in the details.

Example 1.4.3.

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

Solution.

The format of the proof will be this: Let $n$ be an arbitrary integer. Assume that $n$ is even. Explain explain explain. Therefore $n^2$ is even.

To fill in the details, we explain what it means for $n$ to be even, and then see what that means for $n^2\text{.}$ The definition that is relevant here is, “an integer $n$ is even if there is an integer $k$ such that $n = 2k\text{.}$” Here is a complete proof.

Proof.

Let $n$ be an arbitrary integer. Suppose $n$ is even. Then $n = 2k$ for some integer $k\text{.}$ Now $n^2 = (2k)^2 = 4k^2 = 2(2k^2)\text{.}$ Since $2k^2$ is an integer, $n^2$ is even.

Example 1.4.4.

Prove: For all integers $a\text{,}$ $b\text{,}$ and $c\text{,}$ if $a|b$ and $b|c$ then $a|c\text{.}$ (Here $x|y\text{,}$ read “$x$ divides $y$” means that $y$ is a multiple of $x\text{,}$ i.e., that $x$ will divide into $y$ without remainder).

Solution.

Even before we know what the divides symbol means, we can set up a direct proof for this statement. It will go something like this: Let $a\text{,}$ $b\text{,}$ and $c$ be arbitrary integers. Assume that $a|b$ and $b|c\text{.}$ Dot dot dot. Therefore $a|c\text{.}$

How do we connect the dots? We say what our hypothesis ($a|b$ and $b|c$) really means and why this gives us what the conclusion ($a|c$) really means. Another way to say that $a|b$ is to say that $b = ka$ for some integer $k$ (that is, that $b$ is a multiple of $a$). What are we going for? That $c = la\text{,}$ for some integer $l$ (because we want $c$ to be a multiple of $a$). Here is the complete proof.

Proof.

Let $a\text{,}$ $b\text{,}$ and $c$ be integers. Assume that $a|b$ and $b|c\text{.}$ In other words, $b$ is a multiple of $a$ and $c$ is a multiple of $b\text{.}$ So there are integers $k$ and $j$ such that $b = ka$ and $c = jb\text{.}$ Combining these (through substitution) we get that $c = jka\text{.}$ But $jk$ is an integer, so this says that $c$ is a multiple of $a\text{.}$ Therefore $a|c\text{.}$

Subsection Proof by Contrapositive

Recall that an implication $P \imp Q$ is logically equivalent to its contrapositive $\neg Q \imp \neg P\text{.}$ There are plenty of examples of statements which are hard to prove directly, but whose contrapositive can easily be proved directly. This is all that proof by contrapositive does. It gives a direct proof of the contrapositive of the implication. This is enough because the contrapositive is logically equivalent to the original implication.

The skeleton of the proof of $P \imp Q$ by contrapositive will always look roughly like this:

Assume $\neg Q\text{.}$ Explain, explain, … explain. Therefore $\neg P\text{.}$

As before, if there are variables and quantifiers, we set them to be arbitrary elements of our domain. Here are two examples:

Example 1.4.5.

Is the statement “for all integers $n\text{,}$ if $n^2$ is even, then $n$ is even” true?

Solution.

This is the converse of the statement we proved in Example 1.4.3 above using a direct proof. From trying a few examples, this statement definitely appears to be true. So let’s prove it.

A direct proof of this statement would require fixing an arbitrary $n$ and assuming that $n^2$ is even. But it is not at all clear how this would allow us to conclude anything about $n\text{.}$ Just because $n^2 = 2k$ does not in itself suggest how we could write $n$ as a multiple of 2.

Try something else: write the contrapositive of the statement. We get, for all integers $n\text{,}$ if $n$ is odd then $n^2$ is odd. This looks much more promising.

We need a definition of a number being odd: an integer $n$ is odd provided $n = 2k+1$ for some integer $k\text{.}$ Our proof will look something like this:

Let $n$ be an arbitrary integer. Suppose that $n$ is not even. This means that …. In other words …. But this is the same as saying …. Therefore $n^2$ is not even.

Now we fill in the details:

Proof.

We will prove the contrapositive. Let $n$ be an arbitrary integer. Suppose that $n$ is not even, and thus odd. Then $n= 2k+1$ for some integer $k\text{.}$ Now $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\text{.}$ Since $2k^2 + 2k$ is an integer, we see that $n^2$ is odd and therefore not even.

Example 1.4.6.

Prove: for all integers $a$ and $b\text{,}$ if $a + b$ is odd, then $a$ is odd or $b$ is odd.

Solution.

The problem with trying a direct proof is that it will be hard to separate $a$ and $b$ from knowing something about $a+b\text{.}$ On the other hand, if we know something about $a$ and $b$ separately, then combining them might give us information about $a+b\text{.}$ The contrapositive of the statement we are trying to prove is: for all integers $a$ and $b\text{,}$ if $a$ and $b$ are even, then $a+b$ is even. Thus our proof will have the following format:

Let $a$ and $b$ be integers. Assume that $a$ and $b$ are both even. la la la. Therefore $a+b$ is even.

Here is a complete proof:

Proof.

Let $a$ and $b$ be integers. Assume that $a$ and $b$ are even. Then $a = 2k$ and $b = 2l$ for some integers $k$ and $l\text{.}$ Now $a + b = 2k + 2l = 2(k+l)\text{.}$ Since $k + l$ is an integer, we see that $a + b$ is even, completing the proof.

Note that our assumption that $a$ and $b$ are even is really the negation of $a$ or $b$ is odd. We used De Morgan’s law here.

We have seen how to prove some statements in the form of implications: either directly or by contrapositive. Some statements are not written as implications to begin with.

Example 1.4.7.

Consider the following statement: for every prime number $p\text{,}$ either $p = 2$ or $p$ is odd. We can rephrase this: for every prime number $p\text{,}$ if $p \ne 2\text{,}$ then $p$ is odd. Now try to prove it.

Use this as the definition of a prime number: an integer $p \gt 1$ is prime provided it has exactly two factors: $1$ and $p\text{.}$

Solution.

Proof.

Let $p$ be an arbitrary prime number. Assume $p$ is not odd. So $p$ is divisible by 2. Since $p$ is prime, it must have exactly two divisors, and it has 2 as a divisor, so $p$ must be divisible by only 1 and 2. Therefore $p = 2\text{.}$ This completes the proof (by contrapositive).

Subsection Proof by Contradiction

There might be statements which really cannot be rephrased as implications. For example, “$\sqrt 2$ is irrational.” In this case, it is hard to know where to start. What can we assume? Well, say we want to prove the statement $P\text{.}$ What if we could prove that $\neg P \imp Q$ where $Q$ was false? If this implication is true, and $Q$ is false, what can we say about $\neg P\text{?}$ It must be false as well, which makes $P$ true!

This is why proof by contradiction works. If we can prove that $\neg P$ leads to a contradiction, then the only conclusion is that $\neg P$ is false, so $P$ is true. That’s what we wanted to prove. In other words, if it is impossible for $P$ to be false, $P$ must be true.

Here are three examples of proofs by contradiction:

Example 1.4.8.

Prove that $\sqrt{2}$ is irrational.

Solution.

Proof.

Suppose not. Then $\sqrt 2$ is equal to a fraction $\frac{a}{b}\text{.}$ Without loss of generality, assume $\frac{a}{b}$ is in lowest terms (otherwise reduce the fraction). So,

\begin{equation*} 2 = \frac{a^2}{b^2} \end{equation*}

\begin{equation*} 2b^2 = a^2\text{.} \end{equation*}

Thus $a^2$ is even, and as such $a$ is even. So $a = 2k$ for some integer $k\text{,}$ and $a^2 = 4k^2\text{.}$ We then have,

\begin{equation*} 2b^2 = 4k^2 \end{equation*}

\begin{equation*} b^2 = 2k^2\text{.} \end{equation*}

Thus $b^2$ is even, and as such $b$ is even. Since $a$ is also even, we see that $\frac{a}{b}$ is not in lowest terms, a contradiction. Thus $\sqrt 2$ is irrational.

Example 1.4.9.

Prove: There are no integers $x$ and $y$ such that $x^2 = 4y + 2\text{.}$

Solution.

Proof.

We proceed by contradiction. So suppose there are integers $x$ and $y$ such that $x^2 = 4y + 2 = 2(2y + 1)\text{.}$ So $x^2$ is even. We have seen that this implies that $x$ is even. So $x = 2k$ for some integer $k\text{.}$ Then $x^2 = 4k^2\text{.}$ This in turn gives $2k^2 = (2y + 1)\text{.}$ But $2k^2$ is even, and $2y + 1$ is odd, so these cannot be equal. Thus we have a contradiction, so there must not be any integers $x$ and $y$ such that $x^2 = 4y + 2\text{.}$

Example 1.4.10.

The Pigeonhole Principle: If more than $n$ pigeons fly into $n$ pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!

Solution.

Proof.

Suppose, contrary to stipulation, that each of the pigeon holes contain at most one pigeon. Then at most, there will be $n$ pigeons. But we assumed that there are more than $n$ pigeons, so this is impossible. Thus there must be a pigeonhole with more than one pigeon.

While we phrased this proof as a proof by contradiction, we could have also used a proof by contrapositive since our contradiction was simply the negation of the hypothesis. Sometimes this will happen, in which case you can use either style of proof. There are examples however where the contradiction occurs “far away” from the original statement.

Subsection Proof by (counter) Example

It is almost NEVER okay to prove a statement with just an example. Certainly none of the statements proved above can be proved through an example. This is because in each of those cases we are trying to prove that something holds of all integers. We claim that $n^2$ being even implies that $n$ is even, no matter what integer $n$ we pick. Showing that this works for $n = 4$ is not even close to enough.

This cannot be stressed enough. If you are trying to prove a statement of the form $\forall x P(x)\text{,}$ you absolutely CANNOT prove this with an example.³

However, existential statements can be proven this way. If we want to prove that there is an integer $n$ such that $n^2-n+41$ is not prime, all we need to do is find one. This might seem like a silly thing to want to prove until you try a few values for $n\text{.}$

$n$	1	2	3	4	5	6	7
$n^2 - n + 41$	41	43	47	53	61	71	83

So far we have gotten only primes. You might be tempted to conjecture, “For all positive integers $n\text{,}$ the number $n^2 - n + 41$ is prime.” If you wanted to prove this, you would need to use a direct proof, a proof by contrapositive, or another style of proof, but certainly it is not enough to give even 7 examples. In fact, we can prove this conjecture is false by proving its negation: “There is a positive integer $n$ such that $n^2 - n + 41$ is not prime.” Since this is an existential statement, it suffices to show that there does indeed exist such a number.

In fact, we can quickly see that $n = 41$ will give $41^2$ which is certainly not prime. You might say that this is a counterexample to the conjecture that $n^2 - n + 41$ is always prime. Since so many statements in mathematics are universal, making their negations existential, we can often prove that a statement is false (if it is) by providing a counterexample.

Example 1.4.11.

Above we proved, “for all integers $a$ and $b\text{,}$ if $a+b$ is odd, then $a$ is odd or $b$ is odd.” Is the converse true?

Solution.

The converse is the statement, “for all integers $a$ and $b\text{,}$ if $a$ is odd or $b$ is odd, then $a + b$ is odd.” This is false! How do we prove it is false? We need to prove the negation of the converse. Let’s look at the symbols. The converse is

\begin{equation*} \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b))\text{.} \end{equation*}

We want to prove the negation:

\begin{equation*} \neg \forall a \forall b ((O(a) \vee O(b)) \imp O(a+b))\text{.} \end{equation*}

Simplify using the rules from the previous sections:

\begin{equation*} \exists a \exists b ((O(a) \vee O(b)) \wedge \neg O(a+b))\text{.} \end{equation*}

As the negation passed by the quantifiers, they changed from $\forall$ to $\exists\text{.}$ We then needed to take the negation of an implication, which is equivalent to asserting the if part and not the then part.

Now we know what to do. To prove that the converse is false we need to find two integers $a$ and $b$ so that $a$ is odd or $b$ is odd, but $a+b$ is not odd (so even). That’s easy: 1 and 3. (remember, “or” means one or the other or both). Both of these are odd, but $1+3 = 4$ is not odd.

Subsection Proof by Cases

We could go on and on and on about different proof styles (we will discuss combinatorial proofs and proofs by induction in later sections), but instead we will end with one final useful technique: proof by cases. The idea is to prove that $P$ is true by proving that $Q \imp P$ and $\neg Q \imp P$ for some statement $Q\text{.}$ So no matter what, whether or not $Q$ is true, we know that $P$ is true. In fact, we could generalize this. Suppose we want to prove $P\text{.}$ We know that at least one of the statements $Q_1, Q_2, \ldots, Q_n$ is true. If we can show that $Q_1 \imp P$ and $Q_2 \imp P$ and so on all the way to $Q_n \imp P\text{,}$ then we can conclude $P\text{.}$ The key thing is that we want to be sure that one of our cases (the $Q_i$’s) must be true no matter what.

If that last paragraph was confusing, perhaps an example will make things better.

Example 1.4.12.

Prove: For any integer $n\text{,}$ the number $(n^3 -n)$ is even.

Solution.

It is hard to know where to start this, because we don’t know much of anything about $n\text{.}$ We might be able to prove that $n^3 - n$ is even if we knew that $n$ was even. In fact, we could probably prove that $n^3-n$ was even if $n$ was odd. But since $n$ must either be even or odd, this will be enough. Here’s the proof.

Proof.

We consider two cases: if $n$ is even or if $n$ is odd.

Case 1: $n$ is even. Then $n = 2k$ for some integer $k\text{.}$ This give

\begin{align*} n^3 - n \amp = 8k^3 - 2k\\ \amp = 2(4k^3 - k)\text{,} \end{align*}

and since $4k^3 - k$ is an integer, this says that $n^3-n$ is even.

Case 2: $n$ is odd. Then $n = 2k+1$ for some integer $k\text{.}$ This gives

\begin{align*} n^3 - n \amp = (2k+1)^3 - (2k+1)\\ \amp = 8k^3 + 12k^2 + 6k + 1 - 2k - 1\\ \amp = 2(4k^3 + 6k^2 + 2k)\text{,} \end{align*}

and since $4k^3 + 6k^2 + 2k$ is an integer, we see that $n^3 - n$ is even again.

Since $n^3 - n$ is even in both exhaustive cases, we see that $n^3 - n$ is indeed always even.

Reading Questions Reading Questions

1.

Which of the following would be the best first line of a direct proof if you wanted to prove the statement, “For all sets $A$ of single digit numbers, if $|A| = 6\text{,}$ then $A$ contains an even number.”

Suppose there exists a set $A$ of single digit numbers with $|A| = 6$ but that contains only odd numbers.
Incorrect. A direct proof starts by assuming the hypothesis of the implication you wish to prove. Try again.
Fix an arbitrary set $A$ of single digit numbers and assume $|A| = 6\text{.}$
Correct! A direct proof starts by assuming the hypothesis of the implication you wish to prove.
Suppose $A$ is a set of single digit numbers with $|A| \ne 6\text{.}$
Incorrect. What is the “if” part of the statement you are trying to prove? Try again.
Let $A$ be a set of single digit numbers that contains an even number.
Incorrect. Try again.
Let $A$ be a set of single digit numbers, and assume that $A$ does not contain any even numbers.
Incorrect. Try again.

2.

Which of the following would be the best first line of a proof by contrapositive if you wanted to prove the statement, “For all sets $A$ of single digit numbers, if $|A| = 6\text{,}$ then $A$ contains an even number.”

Suppose there exists a set $A$ of single digit numbers with $|A| = 6$ but that contains only odd numbers.
Incorrect. What is the contrapositive of what we are trying to prove? Try again.
Fix an arbitrary set $A$ of single digit numbers and assume $|A| = 6\text{.}$
Incorrect. We are trying to prove the contrapositive, so assume the if part of the contrapositive. Try again.
Suppose $A$ is a set of single digit numbers with $|A| \ne 6\text{.}$
Incorrect. The contrapositive of $P \imp Q$ is $\neg Q \imp \neg P\text{.}$ Proofs by contrapositive should start by assuming $\neg Q\text{.}$ Try again.
Let $A$ be a set of single digit numbers that contains an even number.
Incorrect. The contrapositive of $P \imp Q$ is $\neg Q \imp \neg P\text{.}$ Proofs by contrapositive should start by assuming $\neg Q\text{.}$ Try again.
Let $A$ be a set of single digit numbers, and assume that $A$ does not contain any even numbers.
Correct!

3.

Which of the following would be the best first line of a proof by contradiction if you wanted to prove the statement, “For all sets $A$ of single digit numbers, if $|A| = 6\text{,}$ then $A$ contains an even number.”

Suppose there exists a set $A$ of single digit numbers with $|A| = 6$ but that contains only odd numbers.
Correct! This is the negation of the statement we are trying to prove.
Fix an arbitrary set $A$ of single digit numbers and assume $|A| = 6\text{.}$
Incorrect. A proof by contradiction should start by assuming the negation of what we are trying to prove. Try again.
Suppose $A$ is a set of single digit numbers with $|A| \ne 6\text{.}$
Incorrect. A proof by contradiction should start by assuming the negation of what we are trying to prove. Try again.
Let $A$ be a set of single digit numbers that contains an even number.
Incorrect. A proof by contradiction should start by assuming the negation of what we are trying to prove. Try again.
Let $A$ be a set of single digit numbers, and assume that $A$ does not contain any even numbers.
Incorrect. A proof by contradiction should start by assuming the negation of what we are trying to prove. Try again.

4.

What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

Exercises Practice Problems

1.

Drag some of the statements from the left to the right to form a correct proof of the following statement: “For any integer $n\text{,}$ if $n$ is even, then $7n$ is even.”

Let \(n\) be an arbitrary integer and assume \(n\) is even.
---
Since the product of any number with an even number is even,
---

\(7n\) must be even.
---
Let \(n\) be an arbitrary integer and assume \(7n\) is even. #distractor
---
Let \(n\) be an arbitrary integer and assume \(7n\) is odd. #distractor
---
Since \(7\) is odd and the product of an odd number and an odd number is odd, #distractor
---
Since an even number divided by \(7\) must be odd, #distractor
---

\(n\) must be even. #distractor
---

\(7n\) must be odd.
 #distractor

2.

Drag some of the statements from the left to the right to form a correct proof of the following statement: “For any integer $n\text{,}$ if $7n$ is even, then $n$ is even.”

Let \(n\) be an arbitrary integer and assume \(n\) is even. #distractor
---
Since the \(7\) is odd and the product of an odd number with an even number is even, #distractor
---

\(7n\) must be even. #distractor
---
Let \(n\) be an arbitrary integer and assume \(7n\) is even. #distractor
---
Let \(n\) be an arbitrary integer and assume \(n\) is odd.
---
Since \(7\) is odd and the product of an odd number and an odd number is odd,
---
Since an even number divided by \(7\) must be even, #distractor
---

\(n\) must be even. #distractor
---

\(7n\) must be odd.

3.

Consider the statment, “For any numbers $a$ and $b\text{,}$ if $a+b$ is odd, then either $a$ or $b$ is odd”.

Give a valid proof of the statement using a proof by contrapositive. Drag statements from the left to the right and put them in the right order.

Let \(a\) and \(b\) be integers and assume that \(a+b\) is odd. #distractor
---
Let \(a\) and \(b\) be integers and assume that if \(a+b\) is odd, then either \(a\) or \(b\) is odd. #distractor
---
Let \(a\) and \(b\) be integers and assume both are even.
---
The sum of two even integers must also be even.
---
Therefore \(a+b\) is even.
---
Let \(a\) and \(b\) be integers and assume that \(a+b\) is odd but \(a\) and \(b\) are both even. #distractor
---
The sum of two odd integers must be even. #distractor
---
But then \(a+b\) is both even and odd, a contradiction.
 #distractor

4.

Consider the same statement, “For any numbers $a$ and $b\text{,}$ if $a+b$ is odd, then either $a$ or $b$ is odd”.

Give a valid proof of the statement, this time using a proof by contradiction. Drag statements from the left to the right and put them in the right order.

Let \(a\) and \(b\) be integers and assume that \(a+b\) is odd. #distractor
---
Let \(a\) and \(b\) be integers and assume that if \(a+b\) is odd, then either \(a\) or \(b\) is odd. #distractor
---
Let \(a\) and \(b\) be integers and assume both are even. #distractor
---
Let \(a\) and \(b\) be integers and assume that \(a+b\) is odd but \(a\) and \(b\) are both even.
---
Therefore \(a+b\) is even. #distractor
---
The sum of two even integers must also be even.
---
The sum of two odd integers must be even. #distractor
---
But then \(a+b\) is both even and odd, a contradiction.

5.

Below are three statements together with a possible first line of a proof of that statement. In each case, say whether the first line is the start of a direct proof, a proof by contrapositive, or a proof by contradiction.

Statement: For every integer $n\text{,}$ the number $7n-1$ is divisible by 6.

First line: Suppose there were some integer $n$ for which $7n-1$ was not divisible by 6.
Statement: For any integer $n\text{,}$ if $n$ is prime, then $n$ is solitary

First line: Let $n$ be an integer, and assume $n$ is prime.
Statement: If $f$ is a differentiable function, then $f$ is continuous.

First line: Let $f$ be a function and assume $f$ is not continuous.

6.

What would the first line be for a proof in each style, of the following statement: “If a function $f:A \to B$ is a bijection, then $|A| = |B|\text{.}$”

Assume $f: A \to B$ is a bijection
Direct Proof
Assume $|A| \ne |B|$
Proof by contrapositive
Assume $f: A \to B$ is a bijection and $|A|\ne|B|$
Proof by contradiction

Exercises Additional Exercises

1.

Consider the statement “for all integers $a$ and $b\text{,}$ if $a + b$ is even, then $a$ and $b$ are even”

Write the contrapositive of the statement.
Write the converse of the statement.
Write the negation of the statement.
Is the original statement true or false? Prove your answer.
Is the contrapositive of the original statement true or false? Prove your answer.
Is the converse of the original statement true or false? Prove your answer.
Is the negation of the original statement true or false? Prove your answer.

2.

For each of the statements below, say what method of proof you should use to prove them. Then say how the proof starts and how it ends. Bonus points for filling in the middle.

There are no integers $x$ and $y$ such that $x$ is a prime greater than 5 and $x = 6y + 3\text{.}$
For all integers $n\text{,}$ if $n$ is a multiple of 3, then $n$ can be written as the sum of consecutive integers.
For all integers $a$ and $b\text{,}$ if $a^2 + b^2$ is odd, then $a$ or $b$ is odd.

3.

Consider the statement: for all integers $n\text{,}$ if $n$ is even then $8n$ is even.

Prove the statement. What sort of proof are you using?
Is the converse true? Prove or disprove.

4.

The game TENZI comes with 40 six-sided dice (each numbered 1 to 6). Suppose you roll all 40 dice.

Prove that there will be at least seven dice that land on the same number.
How many dice would you have to roll before you were guaranteed that some four of them would all match or all be different? Prove your answer.

5.

Prove that for all integers $n\text{,}$ it is the case that $n$ is even if and only if $3n$ is even. That is, prove both implications: if $n$ is even, then $3n$ is even, and if $3n$ is even, then $n$ is even.

Hint.

One of the implications will be a direct proof, the other will be a proof by contrapositive.

6.

Prove that $\sqrt 3$ is irrational.

Hint.

This is really an exercise in modifying the proof that $\sqrt{2}$ is irrational. There you proved things were even; here they will be multiples of 3.

7.

Consider the statement: for all integers $a$ and $b\text{,}$ if $a$ is even and $b$ is a multiple of 3, then $ab$ is a multiple of 6.

Prove the statement. What sort of proof are you using?
State the converse. Is it true? Prove or disprove.

Hint.

Part (a) should be a relatively easy direct proof. Look for a counterexample for part (b).

8.

Prove the statement: For all integers $n\text{,}$ if $5n$ is odd, then $n$ is odd. Clearly state the style of proof you are using.

9.

Prove the statement: For all integers $a\text{,}$ $b\text{,}$ and $c\text{,}$ if $a^2 + b^2 = c^2\text{,}$ then $a$ or $b$ is even.

Hint.

A proof by contradiction would be reasonable here, because then you get to assume that both $a$ and $b$ are odd. Deduce that $c^2$ is even, and therefore a multiple of 4 (why? and why is that a contradiction?).

10.

Suppose that you would like to prove the following implication:

For all numbers $n\text{,}$ if $n$ is prime then $n$ is solitary.

Write out the beginning and end of the argument if you were to prove the statement,

Directly
By contrapositive
By contradiction

You do not need to provide details for the proofs (since you do not know what solitary means). However, make sure that you provide the first few and last few lines of the proofs so that we can see that logical structure you would follow.

11.

Suppose you have a collection of rare 5-cent stamps and 8-cent stamps. You desperately need to mail a letter and having no other stamps available, decide to dip into your collection. The question is, what amounts of postage can you make?

Prove that if you only use an even number of both types of stamps, the amount of postage you make must be even.
Suppose you made an even amount of postage. Prove that you used an even number of at least one of the types of stamps.
Suppose you made exactly 72 cents of postage. Prove that you used at least 6 of at least one type of stamp.

Hint.

Use a different style of proof for each part.

12.

Prove: $x=y$ if and only if $xy=\dfrac{(x+y)^2}{4}\text{.}$ Note, you will need to prove two “directions” here: the “if” and the “only if” part.

13.

Prove that $\log(7)$ is irrational.

Hint.

Note that if $\log(7) = \frac{a}{b}\text{,}$ then $7 = 10^\frac{a}{b}\text{.}$ Can any power of 7 be the same as a power of 10?

14.

Prove that there are no integer solutions to the equation $x^2 = 4y + 3\text{.}$

Hint.

What if there were? Deduce that $x$ must be odd, and continue towards a contradiction.

15.

Prove that every prime number greater than 3 is either one more or one less than a multiple of 6.

Hint.

Prove the contrapositive by cases. There will be 4 cases to consider.

16.

Your “friend” has shown you a “proof” he wrote to show that $1 = 3\text{.}$ Here is the proof:

Proof.

I claim that $1 = 3\text{.}$ Of course we can do anything to one side of an equation as long as we also do it to the other side. So subtract 2 from both sides. This gives $-1 = 1\text{.}$ Now square both sides, to get $1 = 1\text{.}$ And we all agree this is true.

What is going on here? Is your friend’s argument valid? Is the argument a proof of the claim $1=3\text{?}$ Carefully explain using what we know about logic.

Hint.

Your friend’s proof a proof, but of what? What implication follows from the given proof? Is that helpful?

17.

A standard deck of 52 cards consists of 4 suites (hearts, diamonds, spades and clubs) each containing 13 different values (Ace, 2, 3, …, 10, J, Q, K). If you draw some number of cards at random you might or might not have a pair (two cards with the same value) or three cards all of the same suit. However, if you draw enough cards, you will be guaranteed to have these. For each of the following, find the smallest number of cards you would need to draw to be guaranteed having the specified cards. Prove your answers.

Three of a kind (for example, three 7’s).
A flush of five cards (for example, five hearts).
Three cards that are either all the same suit or all different suits.

18.

Suppose you are at a party with 19 of your closest friends (so including you, there are 20 people there). Explain why there must be least two people at the party who are friends with the same number of people at the party. Assume friendship is always reciprocated.

Hint.

Consider the set of numbers of friends that everyone has. If everyone had a different number of friends, this set must contain 20 elements. Is that possible? Why not?

19.

Your friend has given you his list of 115 best Doctor Who episodes (in order of greatness). It turns out that you have seen 60 of them. Prove that there are at least two episodes you have seen that are exactly four episodes apart on your friend’s list.

Hint.

This feels like the pigeonhole principle, although a bit more complicated. At least, you could try to replicate the style of proof used by the pigeonhole principle. How would the episodes need to be spaced out so that no two of your sixty were exactly 4 apart?

20.

Suppose you have an $n\times n$ chessboard but your dog has eaten one of the corner squares. You have dominoes that each cover exactly two squares of the board. Can you cover the squares still remaining on the board with non-overlapping dominoes? What needs to be true about $n\text{?}$ Give necessary and sufficient conditions (that is, say exactly which values of $n$ work and which do not work). Prove your answers.

$An 8 by 8 chessboard with the top-right corner square removed. Every other square is shaded darker (checkerboard pattern).$

21.

What if your $n\times n$ chessboard is missing two opposite corners? Prove that no matter what $n$ is, you will not be able to cover the remaining squares with non-overlapping dominoes.

$An 8 by 8 chessboard with the top-right and bottom-left corner squares removed. Every other square is shaded darker (checkerboard pattern).$

You have attempted of activities on this page.

Prev Top Next

\(n\)	1	2	3	4	5	6	7
\(n^2 - n + 41\)	41	43	47	53	61	71	83