Section3Basic Proof Methods¶ permalink

It is time to prove some theorems. A theorem is a mathematical statement that is true and can be (and has been) verified as true. A proof of a theorem is a written verification that shows that the theorem is definitely and unequivocally true. A proof should be understandable and convincing to anyone who has the requisite background and knowledge.

Subsection3.1Direct Proof

To prove an implication $P \Rightarrow Q$, the most straightforward way is the direct proof. The structure of a direct proof shall look like this:

Proof

Our first proof is a well-known fact: the sum of two even numbers is even. To prove this theorem, we need to know the meaning of even.

Definition3.1

An integer $n$ is even if $n=2k$ for some integer $k$.

For the sake of completeness, we also define odd.

Definition3.2

An integer $n$ is odd if $n=2k-1$ for some integer $k$.

The use of "if" in any definition is always the same as "if and only if" and not the same as the "if" in an "if...then.." statement. For comparison, the statement \begin{equation*}\text{If an integer $n$ can be written as $n=2k$ for some integer $k$, then $n$ is even.}\end{equation*} has a different meaning from the definition of even numbers because it only gives a sufficient condition for an integer to be an even and a priori, there are might be other situations for an integer to be even. On the other hand, the definition of even says that an integer $n$ is even exactly when we can write $n=2k$ for some integer $k$. Let us see if you understand the definition of even and odd.

Task3.3

Fill in the blanks:

$4$ is even because $4 = 2(\underline{\hspace{5mm}})$. Here, $\underline{\hspace{5mm}}$ plays the role of $n$ and $\underline{\hspace{5mm}}$ plays the role of $k$ in the definition.
$5$ is odd because $5 = 2(\underline{\hspace{5mm}})-1$. Here, $\underline{\hspace{5mm}}$ plays the role of $n$ and $\underline{\hspace{5mm}}$ plays the role of $k$ in the definition.
$-4$ is even because $-4 = 2(\underline{\hspace{5mm}})$. Here, $\underline{\hspace{5mm}}$ plays the role of $n$ and $\underline{\hspace{5mm}}$ plays the role of $k$ in the definition.
$-5$ is odd because $-5 = 2(\underline{\hspace{5mm}})-1$. Here, $\underline{\hspace{5mm}}$ plays the role of $n$ and $\underline{\hspace{5mm}}$ plays the role of $k$ in the definition.
$0$ is even because $0 = 2(\underline{\hspace{5mm}})$. Here, $\underline{\hspace{5mm}}$ plays the role of $n$ and $\underline{\hspace{5mm}}$ plays the role of $k$ in the definition.

Task3.4

Prove the theorem by filling the blanks: If $n_1$ and $n_2$ are even, then $n_1+n_2$ is even.

Proof

Task3.5

If $n_1$ is odd and $n_2$ is even, then $n_1+n_2$ is odd.

Task3.6

If $n_1$ and $n_2$ are odd, then $n_1+n_2$ is even.

Task3.7

Use direct proof to show the following theorem: If $n$ is even, then $n^2$ is even.

Task3.8

Use direct proof to show the following theorem: If $n_1$ is odd and $n_2$ is even, then $n_1n_2$ is even.

The following theorem is a consequence of elementary number theory and feel free to use it whenever you think it is appropriate. We will not prove this theorem in full extent in this course.

Theorem3.9Parity Theorem

Every integer is either even or odd but not both.

Task3.10

Use direct proof to show the following theorem: If $n$ is an arbitrary integer, then $n(n+1)$ is even.

Task3.11

Use direct proof to show the following theorem: If $x+y$ is odd and $y+z$ is odd, then $x+z$ is even.

Subsection3.2Proof by Contrapositive

In the last chapter, we learned that $P \Rightarrow Q$ is equivalent to $(\sim Q) \Rightarrow (\sim P)$. So in order to show that $P \Rightarrow Q$ is true, we can just show that $(\sim Q) \Rightarrow (\sim P)$. If we were to to use direct proof to show that $(\sim Q) \Rightarrow (\sim P)$ is true, we would assume $\sim Q$ is true and use this to deduce that $\sim P$ is true. This is the basic idea of proof by contrapositive. The structure of a contrapositive proof shall look like this:

Proof

Task3.12

Prove the theorem by filling the blanks: For any integer $n$, if $5n+3$ is even, then $n$ is odd.

Proof

Task3.13

Can you prove the theorem in Task 3.12 using direct proof? Compare two proofs. Which one do you like and why?

Task3.14

Use proof by contrapositive to show the following theorem: If $n^2$ is even, then $n$ is even. Can you prove the same theorem using direct proof?

Task3.15

Use proof by contrapositive to show the following theorem: For any integer $n$, if $n^2-6n+5$ is even, then $n$ is odd. Can you prove the same theorem using direct proof?

Subsection3.3Proof by Contradiction

The basic idea of proof by contradiction is to assume that the statement we want to prove is false. Then we show that this assumption leads to nonsense. We are then lead to conclude that we were wrong to assume the statement (the one that we want to prove) was false in the first place, so the statement must be true. Let us first investigate a few examples before we look into its logical validity.

Task3.16

Prove the theorem by filling the blanks: If $x$ and $y$ are two integers, then $x^2-4y \neq 2$.

Proof

At the very end of the proof in Task 3.16, we reach the conclusion that $1$ is even. By the Parity Theorem, we know that the statement $1$ is even is equivalent to $1$ is not odd. But we also know that $1$ is odd. Thus we obtained the statement $1$ is odd and $1$ is not odd, which has the form $R \land (\sim R)$ where $R$ stands for "$1$ is odd". By Task 2.41, the general structure for a proof by contradiction of looks like this.

Proof

One unsettling feature of this method is that we may not know at the beginning of the proof what the statement $R$ is going to be. In general, there is no recipe for this. You would have to find your own contradiction. In fact, different people might find different contradictions.

Task3.17

Use proof by contradiction to show the theorem: For any integer $n$, if $n^2-6n+5$ is even, then $n$ is odd. Compare your proof with the proof by contrapositive in Task 3.15, which one do you like and why?

In general when we prove a theorem of the form $P \Rightarrow Q$, we do not recommend to start by trying to use proof by contradiction. We should try to use direct proof first. If that is not possible, then try proof by contrapositive. If that is still not possible, try proof by contradiction at the end.

Task3.18

Use proof by contradiction to show that if $m-n$ is odd, then $m+n$ is odd.

Task3.19

By the Parity Theorem, we know that every integer is either odd or even but not both. Let us show the second part of this theorem by proof by contradiction, namely, show that an arbitrary integer cannot be both odd and even. (Note that this does not show the complete statement of the Parity Theorem because we have not explained why every integer must be either odd or even. In other words, why it is not possible for an integer to be not odd and not even?)

Subsection3.4Which one to choose?

In this section, you are free to choose any method you want to solve the tasks. After you solve a task using one method, ask yourself if you can solve the same task using another method(s). If so, which method would you prefer and why?

Definition3.20

Let $m$ and $n$ be two integers. We say that $m$ divides $n$, denoted by $m \; | \; n$, provided that there exists an integer $k$ such that $n=km$. In this case, we also say that $n$ is divisible by $m$ or $m$ is a factor of $n$.

Task3.21

Use the definition, show that

$4$ divides $16$.
$7$ is not divisible by $5$.
$-10$ is a factor of $30$.
$-3$ divides $3$.
Any integer is a factor of $0$.

Task3.22

For all integers $a,b,c$, if $a \; | \; b$ and $b \; | \; c$, then $a \; | \; c$.

Task3.23

For all integer $n$, if $n^2$ is not divisible by $4$, then $n$ is odd.

Task3.24

For all integer $n$, $n^2+2$ is not divisible by $4$.

Task3.25

How would you go about proving a statement of the form "If $P$, then $Q$ or $R$" given that the statements $P$, $Q$ and $R$ are meaningful? How does this relate to Task 2.35? Use your strategy to prove the following theorem: For any integers $n$ and $m$, if $2 \; | \; (nm)$, then $2 \; | \; n$ or $2 \; | \; m$.

Task3.26

If $n$ is an integer and $n^2 \; | \; n$, then $n$ is either $0$, $1$ or $-1$.

Task3.27

How would you go about proving a statement of the form "$P$ is true if and only if $Q$ is true"? How does this relate to Task 2.34? Use your strategy to prove the following theorem: For any odd integer $n$, an integer $m$ is odd if and only if the product $mn$ is odd.

Definition3.28

A real number $x$ is rational if $x = a/b$ for some integers $a$ and $b$. A real number $x$ is irrational if it is not rational, namely, $x \neq a/b$ for all possible choices of integers $a$ and $b$.

Task3.29

If $x$ and $y$ are two real numbers, if $x+y$ is irrational, then at least one of $x$ or $y$ is irrational.

Task3.30

Show that $\sqrt{2}$ is irrational. (Hint: Suppose that $\sqrt{2}$ is rational, then $\sqrt{2} = a/b$ for some integers $a$ and $b$. Think about why we can assume $a$ and $b$ are not both even. Now what contradiction can you deduce from here?)

Task3.31

Do the following implications valid? Prove it or find a counterexample.

$(\forall x, P(x) \lor Q(x)) \Rightarrow [(\forall x, P(x)) \lor (\forall x, Q(x))]$.
$[(\forall x, P(x)) \Rightarrow (\forall x, Q(x))] \Rightarrow [\forall x, (P(x) \Rightarrow Q(x))].$

Subsection3.5Some Advices

Before we move on to the next chapter, I would like to give you some advice on how to write mathematical proofs in general.

Never begin a sentence with a mathematical symbol. Instead of saying "$n$ is an even number", we can say "The number $n$ is even.".
End each sentence with a period just like writing an English article.
Try to separate mathematical symbols and expressions with words to avoid confusions. Instead of saying "Because $x^2-1=0$, $x=1$ or $x=-1$", we can say "Because $x^2-1=0$, we know that $x=1$ or $x=-1$."
Use mathematical symbols in mathematical expressions. Use English words in sentences. Instead of saying "Since two sets are $=, \dots$", we can say "Since two sets are equal, $\dots$."
Avoid using unnecessary symbols. Instead of saying "Every set $A$ is a subset of itself", we can say "Every set is a subset of itself". Unless you need to use $A$ later on, there is no need to introduce extra notations to muddy the water.
Use "we", "us" rather than "I", "you", "me". Pretend that you are having a conversation with the reader.
Be specific as much as possible. Try not to use pronounce because it can lead to confusions. For example, "Since $X \subset Y$ and $X$ contains some element, we see that it is not empty."" Is "it" $X$ or $Y$? Either one would make sense but it is not clear which one do we mean.