3.2 Proofs 证明

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 3.2 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

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

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

1. 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 & =(2k+1)(2m+1)\\ & =4km+2k+2m+1\\ & =2(2km+k+m)+1. \end{align*} Therefore $ab$ is odd.
2. 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 & =(2k)b\\ & =2(kb). \end{align*} Thus $ab$ is even.
3. 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 & =(2k+1)(2j+1)\\ 2n & =4kj+2k+2j+1\\ n & = 2kj+k+j+\frac{1}{2}. \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.
4. Let $ab$ be an even number, say $ab=2n\text{,}$ and $a$ be an odd number, say $a=2k+1\text{.}$ \begin{align*} ab & =(2k+1)b\\ 2n & =2kb+b\\ 2n-2kb& =b\\ 2(n-kb)& =b. \end{align*} Therefore $b$ must be even.

1. 设 $a$ 与 $b$ 均为奇数。即存在整数 $k$ 与 $m$ 使得 $a=2k+1$ 且 $b=2m+1\text{。}$ 于是 \begin{align*} ab & =(2k+1)(2m+1)\\ & =4km+2k+2m+1\\ & =2(2km+k+m)+1. \end{align*} 因此 $ab$ 为奇数。
2. 假设 $a$ 或 $b$ 为偶数——不妨设是 $a$（$b$ 为偶数的情形完全类似）。即存在整数 $k$ 使得 $a=2k\text{。}$ 于是 \begin{align*} ab & =(2k)b\\ & =2(kb). \end{align*} 故 $ab$ 为偶数。
3. 假设 $ab$ 为偶数，但 $a$ 与 $b$ 均为奇数。即存在整数 $n\text{、}$ $k\text{、}$ $j$ 使得 $ab = 2n\text{，}$ $a=2k+1$ 且 $b=2j+1\text{。}$ 于是 \begin{align*} 2n & =(2k+1)(2j+1)\\ 2n & =4kj+2k+2j+1\\ n & = 2kj+k+j+\frac{1}{2}. \end{align*} 但 $2kj+k+j$ 是整数，这意味着整数 $n$ 等于一个非整数，矛盾。
4. 设 $ab$ 为偶数，例如 $ab=2n\text{，}$且 $a$ 为奇数，例如 $a=2k+1\text{。}$ \begin{align*} ab & =(2k+1)b\\ 2n & =2kb+b\\ 2n-2kb& =b\\ 2(n-kb)& =b. \end{align*} 因此 $b$ 必为偶数。

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 3.2.1 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. \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.

1. Suppose there are only finitely many primes. [this is a premise. Note the use of "suppose."]
2. There must be a largest prime, call it $p\text{.}$ [follows from line 1, by the definition of "finitely many."]
3. 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.]
4. $N$ is larger than $p\text{.}$ [by the definition of $p!$]
5. $N$ is not divisible by any number less than or equal to $p\text{.}$ [by definition, $p!$ is divisible by each number less than or equal to $p\text{,}$ so $p! + 1$ is not.]
6. 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.]
7. Therefore $p$ is not the largest prime. [by line 6, $N$ is divisible by a prime larger than $p\text{.}$]
8. This is a contradiction. [from line 2 and line 7: the largest prime is $p$ and there is a prime larger than $p\text{.}$]
9. Therefore there are infinitely many primes. [from line 1 and line 8: our only premise lead to a contradiction, so the premise is false.]

1. 假设素数只有有限多个。[这是一条前提。注意这里用了「假设」。]
2. 必存在一个最大的素数，记为 $p\text{。}$ [由第 1 行及「有限多个」的定义推出。]
3. 令 $N = p! + 1\text{。}$ [基本只是记号，但这正是证明中富有灵感的部分；盯住 $p! + 1$ 是关键洞见。]
4. $N$ 大于 $p\text{。}$ [由 $p!$ 的定义。]
5. $N$ 不能被任何小于或等于 $p$ 的数整除。[根据定义，$p!$ 能被每个小于或等于 $p$ 的数整除，故 $p! + 1$ 不能。]
6. $N$ 的素因数分解中含有大于 $p$ 的素数。[因为 $N$ 能被其素因数分解中的每一个素数整除，且由第 5 行。]
7. 因此 $p$ 并非最大的素数。[由第 6 行，$N$ 能被一个大于 $p$ 的素数整除。]
8. 这是一个矛盾。[综合第 2 行与第 7 行：最大的素数是 $p$，同时又存在一个大于 $p$ 的素数。]
9. 因此素数有无穷多个。[由第 1 行与第 8 行：我们唯一的前提导致了矛盾，故该前提为假。]

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. Additionally, it is equally important to understand the overall structure of the proof. This is where using tools from logic is helpful. Luckily there are a relatively small number of standard proof styles that keep showing up again and again. Being familiar with these can help understand proof, as well as give ideas of how to write your own.

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. Direct proofs are especially useful when proving implications. The general format to prove $P \imp Q$ is this:

Assume $P\text{.}$ Explain, explain, …, explain. Therefore $Q\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 3.2.1

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

Solution

The format of the proof with 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 will basically just explain what it means for $n$ to be even, and then see what that means for $n^2\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 3.2.2

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$ (so $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{.}$ ∎

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 a couple examples:

Example 3.2.3

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 above using a direct proof. From trying a few examples, this statement definitely appears this is 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. 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 3.2.4

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.

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+1)\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 3.2.5

Consider the 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.

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). ∎