Mathematical Proof/Methods of Proof
There are many different ways to prove things in mathematics. This chapter will introduce some of those methods.
Introduction
editIn this chapter, for every method of proof introduced, we will discuss it in this manner:
- Explaining why the method works, by considering its underlying logic.
- Introducing how to use the method.
- Giving examples of using the method (and possibly also some previous method introduced) to prove some results.
Before introducing the first proof method, let us go through the meanings of some frequently used terms in mathematics books (some are already used in previous chapters actually), which are used more frequently starting from this chapter.
- Definition: an explanation of meaning of a term.
- Theorem: an important and interesting true mathematical statement.
- Proposition: a (relatively) less important theorem.
- Lemma: a true mathematical statement that is useful in establishing the truth of other true statements, and is less important than a theorem.
- Corollary: a true mathematical statement that can be deduced from a theorem (or proposition) simply.
- Proof: an explanation of why a statement is true.
- Axiom: a true mathematical statement whose truth is accepted without proof.
- Conjecture: a statement that is believed to be true, but is not proven to be true.
Direct proof
editMany mathematical theorems can be expressed in the form of ", in which and are open statements about elements in a set [1]. This expression means "If then " is true for every . However, in practice, we rarely include the phrase "is true", and usually just write the theorem in the form of "For every , if , then ." Sometimes, we write instead "Let . If , then .", which has the same meaning.
In some situations, the statement is not stated in such a form directly, but can be expressed in such a form. For example, the statement "The square of an even integer is even." can be expressed as "For every , is even is even.", or "For every , if is even, then is even.", or "Let . If is even, then is even.", etc.
Now, we will introduce the first proof method to prove statements in such a form, which is known as direct proof. As suggested by its name, this method is quite "direct", and is probably the simplest method among all methods discussed in this chapter.
Consider the statement "". We would like to prove that it is true. Suppose is false for some . Then, the conditional must be true for this by definition, regardless of the truth value of . Hence, in the proof, we do not need to consider those for which the hypothesis is false.
Because of this, to give a direct proof of "", we first assume is true (So, we are considering every for which is true.), and then proceed to show that is true for every such (or else the conditional will be false).
This shows that is true for those for which is true, and this is enough to prove is true for every (for which may or may not be true), since we have mentioned that the conditional must be true for those for which is false.
Example. Prove that for every , if is odd, then is even.
Proof. Assume is odd. Then, by definition we have for some . Thus, where (this follows from the definition of integers). This means can be written as for some , and hence is even.
In the previous proof, we have used the definitions of odd and even integers:
- an integer is even if for some integer .
- an integer is odd if for some integer .
We can write the proof more concisely using logical notations, as follows:
Proof.
Both styles of proofs are acceptable, but for beginners, it is recommended to use the first type. Also, the first type can let the readers understand the proof easier.
Remark.
- The property of an integer of whether it is even or odd is called parity.
- When we use "" in the proof, it is implicitly assumed it follows the same meaning as in the given statement, i.e., is an integer. We can also let to be an integer explicitly in the proof to be more clear.
- In some other places, the first line "Assume ..." is simply omitted for convenience, but the assumptions are still used in the proof.
Exercise. Consider the statement "For every , if is odd and is even, then is even.". A student provides the following proof to the statement:
Proof. Assume is odd and is even. That is, and for some . It follows that , and thus is even.
Is the proof correct? If not, point out the mistake, and write a correct proof.
The proof is incorrect. The mistake is that one should not use the same for both and , since using the same implies that , which is not necessarily the case from the assumptions. The following proof is a correct one:
Proof. Assume is odd and is even. That is, and for some . It follows that , and thus is even.
Exercise. Prove that for every , if is even, then is odd.
Proof. Assume is even. Then, for some . Thus, Since , is odd.
Exercise. Prove every of the following statements.
(a) The sum of two arbitrary even integers is even.
(b) The sum of two arbitrary odd integers is even.
(c) The sum of an arbitrary even integer and an arbitrary odd integer is odd.
(d) The product of two arbitrary even integers is even.
(e) The product of two arbitrary odd integers is odd.
(f) The product of an arbitrary even integer and an arbitrary odd integer is even.
(Hint: rewrite the statements in the form of "" first.)
(a) First, rewrite the statement as "For every , if and are even, then is even."
Proof. Assume and are even. Then, and for some (notice that we should not use the same for both and , since may be different from .). Thus, , and hence is even since .
(b) First, rewrite the statement as "For every , if and are odd, then is even."
Proof. Assume and are odd. Then, and for some . Thus, , and hence is even since .
(c) First, rewrite the statement as "For every , if is odd and is even, then is odd."
Proof. Assume is odd and is even. Then, and for some . Thus, , and hence is odd since .
(d) First, rewrite the statement as "For every , if is even and is even, then is even."
Proof. Assume and are even. Then, and for some . Thus, , and hence is even since .
(e) First, rewrite the statement as "For every , if is odd and is odd, then is odd."
Proof. Assume and are odd. Then, and for some . Thus, , and hence is odd since .
(f) First, rewrite the statement as "For every , if is odd and is even, then is even."
Proof. Assume is odd and is even. Then, and for some . Thus, , and hence is even since .
Exercise. A real number is defined to be rational if there exist integers with such that . Prove every of the following statements.
(a) The sum of two arbitrary rational numbers is rational.
(b) The difference of two arbitrary rational numbers is rational.
(c) The product of two arbitrary rational numbers is rational.
(d) The quotient of an arbitrary rational number by an arbitrary nonzero rational number is rational.
(a) First, rewrite the statement as "For every , if , then .
Proof. Assume . Then, and for some with and . Thus, Since with , .
(b) First, rewrite the statement as "For every , if , then .
Proof. Assume . Then, for some with . So, is rational since and . Thus, by (a), we have .
(c) First, rewrite the statement as "For every , if , then .
Proof. Assume . Then, and for some with and . Thus, Since with , .
(d) First, rewrite the statement as "For every , if and then .
Proof. Assume and . Then, and for some with , , and . Thus, Since with , .
Example. Prove that for every , if , then .
Proof. For every , . Thus, the hypothesis is false, and hence the statement must be true.
Remark.
- Notice that we do not use direct proof here, since the false hypothesis makes the statement true. In this case, we call the proof as vacuous proof, and say that the result follows vacuously (the statement says nothing at all).
Example. Prove that for every , if , then .
Proof. Assume . Then, Since is positive and is negative by assumption, we have , and thus
Remark.
- Graphically, the function (we will discuss the concept of function in later chapter) looks like:
Exercise. Prove that for every , if , then (this statement is the converse of the statement in above example). (Hint: The following property may be useful: for every , if , then either ( and ) or ( and ).) (This statement seems to be true by inspecting the above graph, but inspecting graph is not a valid way of proving this statement.)
Proof. Assume . Then, ("" is read "which implies" in this context). It follows that we have either
- and , or
- and .
Since no real number satisfies the first one, we must have the second one, which gives .
Combining the two results in the previous example and exercise, we get an "if and only if" result:
- For every , we have if and only if .
In other words, using set language, (Both sets represent the curve (strictly) under the horizontal line in the above graph.)
Letting and be the open statement "" and "" respectively, we can express the above result symbolically: Recall that "" means "" and "". So, to give a direct proof to the statement in the form of "", a usual way is to break the proof into two parts:
- proving that (known as the "only if" part, or "" direction)
- proving that (known as the "if" part, or "" direction)
Example. Prove that for every , . (Hint: this inequality is equivalent to the inequality , obtained by multiplying both side by , which is a positive integer.)
Proof. Using the hint, it suffices to prove that for every , . But it follows from the fact that .
Exercise.
A student provides the following proof to the above statement:
Proof. Since is a positive integer, multiplying to both sides of the inequality yields . After rearranging, we get , which is always true.
Point out the mistake in the proof.
The mistake is that the student implicitly assumes , which is what we want to prove, at the beginning of the proof. Thus, this proof does not prove the result. (Notice that in the proof in the example, we do not assume . Instead, we start from the fact that .)
Example. Let . Prove that for every , if is prime, then is odd.
Proof. Assume is prime. Since the only primes in the set are 3,5,7 and 11, this means . Hence, is odd.
Exercise. Prove that for every , if is even, then is prime.
Proof. Since the set only contains odd numbers, the hypothesis is false, and therefore the result follows vacuously.
Example. (A special case of AM-GM inequality) Prove that for every , if and are positive, then
Proof. Assume and are positive. Then,
Exercise. Suggest a condition where the equality holds, i.e., .
The condition is .
Proofs related to congruence of integers
editAfter introducing the method of direct proof, let us apply this method on proving some results relating to congruence of integers. Before this, let us introduce the concept of congruence of integers. We begin by a motivation for the definition of congruence of integers.
We know that an integer is either even or odd, i.e., can be expressed as or for some integer , according to whether the remainder is 0 or 1 when is divided by 2. Thus, if two integers and have the same remainder when divided by 2 (i.e., have the same parity), then the difference can be proved to be a multiple of 2 (it can be proved that the converse is also true). Similarly, an integer can be expressed as or for some integer , according to whether remainder is 0, 1 or 2 when is divided by 3. Hence, if two integers and have the same remainder when divided by 3, then the difference can be proved to be a multiple of 3 (the converse is also true).
Hence, "two integers have the same remainder when divided by some integer " is equivalent to "their difference is a multiple of ". This leads us to the following definition.
Definition. (Congruence of integers) Let and with . Then, the integer is congruent to modulo , denoted by , if is a multiple of , i.e., for some .
Remark.
- Instead of " is a multiple of ", we can also say is divisible by , or divides , denoted by (in general, the notation means " divides " (and means " does not divide ").
Example. We have since , and since . But, since .
Exercise.
Example. (Clock arithmetic) A familiar application of the concept of congruence of integers is clock arithmetic. For instance, when we want to know adding 5 hours to 8 o'clock gives what time, we first calculate . But . So, we now think about 13 is congruent to which integer between 1 and 12. The integer is 1. Hence, the time is 1 o'clock.
In general, we can get the resulting time by performing the modulo operation, which gives the remainder when dividing the sum of the two numbers by 12 (called modulus). The notation for " modulo " is , which gives the remainder when is divided by ( and are positive integers).
Now, let us apply direct proof to prove some results related to the congruence of integers.
Theorem. For every and for every with , if and , then
- (compatibility with addition) .
- (compatibility with translation) .
- (compatibility with scaling) .
- (compatibility with multiplication) .
(For the compatibility with translation and scaling, the assumption that is not needed.)
Proof. We will only prove the compatibility with addition and multiplication. The proof of other two compatibilities is left to the following exercise.
Compatibility with addition: Assume that and . Then, and for some . Thus, Since , we have .
Compatibility with multiplication: Assume that and . Then, and for some . Thus, Since , we have .
Remark.
- We have applied the trick in the proof of compatibility with multiplication. One can also prove it without using this trick. The details are left to the following exercise.
Exercise. Prove the compatibility with multiplication in the above theorem, without using the trick used in the above proof. (Hint: You may express in terms of and in terms of first.)
Assume that and . Then, and for some . That is, and . Hence, Since , we have .
Exercise. Prove the compatibility with translation and scaling in the above theorem.
One can of course use direct proof and the definition of congruence of integers to prove them, but we will just apply the compatibility with addition and multiplication (which are proven) to prove them (they can be regarded as corollaries of the compatibility with addition and multiplication).
Proof. Assume . Since , we have . Hence, by the compatibility with addition, we have . Also, by the compatibility with multiplication, we have .
In the above result, everything is with the same "modulo ". It is then natural to ask whether there are any results for different "modulo". The answer is yes, and to discuss a result, we need the concept of relatively prime integers.
Definition. (Relatively prime integers) Two integers are relatively prime if their greatest common divisor is 1.
Remark.
- The integers are also called coprime or mutually prime.
Example.
- 2 and 3 are relatively prime.
- 4 and 12 are not relatively prime since their greatest common divisor is 4.
- 9 and 66 are not relatively prime since their greatest common divisor is 3.
Theorem. Two integers and are relatively prime if and only if there exist integers and such that .
Proof. Omitted.
Using this result, we can deduce the following result:
Theorem. For every with , if , and are relatively prime, then .
Proof. Assume , , and are relatively prime. Then, we have and for some . This means . Also, for some . Multiplying both sides by the integer , we get Putting , we get Putting this into , we get Since , we have .
Remark.
- This theorem says in particular if an integer is a multiple of , and also a multiple of , and and are relatively prime, then the integer is a multiple of .
- For example, if an inteeger is a multiple of 3 and also a multiple of 7, then the integer is a multiple of 21 since 3 and 7 are relatively prime.
Exercise. Give an example of integers such that , , and are not relatively prime, and .
Take . Then, and . However, .
Example. (Reflexivity, symmetry, and transitivity of the congruence of integers) Prove that for every with ,
- (reflexivity) for every , .
- (symmetry) for every , if , then .
- (transitivity) for every , if and , then .
(Since the congruence of integers satisfies these three properties, it is said to be an equivalence relation. We will discuss the concept of (equivalence) relation in a later chapter.)
Proof.
Reflexivity:
Since , we have .
Symmetry:
Assume . Then, for some . Thus, , and hence since .
Transitivity:
Assume and . Then, and for some . Hence, . Thus, since .
Remark.
- Notice that not all relations satisfy all these three properties. For instance, "" does not satisfy the reflexivity and transitivity, "" does not satisfy the reflexivity and symmetry.
Example. Applying the compatibility with multiplication in the above theorem, we can get the following result:
- Let be an integer, be a nonnegative integer, and with . If , then .
We can prove it (a bit informally) as follows:
Proof. Assume . First, . Second, we have . Applying this argument again, we get . Thus, we have for every nonnegative integer by applying the argument "again and again".
To prove the result formally, we need to use proof by mathematical induction, which will be discussed later.
Example.
(a) Consider the remainder of when divided by 4 (i.e., ) for . Do you observe any pattern? Hence, suggest a conjecture.
(b) Prove the conjecture.
Solution.
(a) We have Notice that the remainder is 1 for , and 3 for . It is thus natural to expect that the same pattern continue for all other larger integers. Thus, a conjecture is
- Let be a nonnegative integer. If is even, then . Also, if is odd, then .
(b) We will just prove "If is even, then .". The proof of the second part is left to the following exercise.
Proof. Assume is even. Then, for some nonnegative integer ( is a nonnegative integer). It follows that . Since , it follows that by the result in previous example. Hence, .
Exercise. Prove the second part in the above conjecture.
Proof. Assume is odd. Then, for some nonnegative integer . It follows that . From the prove above, we have . Thus, we get .
The following lemma is quite useful for proving results about congruence of integers.
Lemma. (Euclid's division lemma) For every integer and with , there exists a unique pair of integers and such that
Proof. We separate the proof into existence part and uniqueness part.
Existence part:
Case 1: .
Then, we set and . After that, the equation can be rewritten equivalently as , and also the inequality can be rewritten equivalently as . Through this, we transform this case to case 2.
Case 2: .
Subcase 1: and .
Then, we set , , and . After that, the equation can be rewritten equivalently as (this is equivalent to ). Also, the inequality can be rewritten equivalently as . Through this, we transform this case to the subcase 2.
Subcase 2: and .
Set and . Then, we have .
Subsubcase 1: . Take and . Then, we have and we are done.
Subsubcase 2: .
Set and . Then, we have with . Since there are exactly nonnegative integers less than , we need to repeat this process at most times (, so is at most the preceding integer of ) to get a such that [2] (and also a ).
So, we take and . Then, we have and we are done.
Uniqueness part:
Assume there exists another pair of integers and (in addition to the pair of integers and ) such that Since we have also we get, by subtracting the two equations,
Also, by considering the above two inequalities, we get Putting it in the above equation, we get .
Thus, we have and .
Remark.
- This lemma is the basis of Euclidean division, as known as division with remainder.
- is called the dividend, is called the divisor, is called the quotient, and is called the remainder.
- We employ the method of proof by cases in the proof, which is not a "new" way of proof strictly speaking. We just consider different cases in the proof. However, when we use this method, we need to ensure that the cases covers all possibilities for the "for every", so that we actually prove the statement.
- From this lemma, we know that every integer has remainder either 0 or 1 or 2 or ... or (from the inequality ) when divided by an integer with . In other words, for every integer , we have either or or ... or . For brevity, we can also write .
Example. Prove that for every integer , .
Proof. By Euclid's division lemma, we have . Thus, we have . But and . So, the result follows by the transitivity of the congruence of integers.
Exercise. Propose a similar result for the congruence modulo 5, and prove it.
Proposition: For every integer , .
Proof. By Euclid's division lemma, we have . Thus, we have . But and . So, the result follows.
Proofs related to sets
editThe proofs related to sets are often in the form of
- A set is a subset of another set.
- A set equals another set.
To prove that a set is a subset of another set, we use the definition of subset:
- A set is a subset of another set if for every element , if , then .
Thus, we can employ direct proof to prove that a set is a subset of another set.
For the equality of two sets, recall that:
- A set equals another set if and only if and .
Thus, to prove the equality of two sets, we often need to separate the proof into two parts: (i) proving that ; (ii) proving that .
Example. (Transitivity of "") Prove that for every set and , if and , then .
Proof. Assume and . Then, for every , and hence .
Example. (Associative law) Prove that for every set and , .
Proof. First, we prove that . For every , Thus, we have .
Now, we prove the reverse subset inclusion, i.e., . For every , Thus, we have .
Notice that the proof for reverse subset inclusion is very similar to the proof for the first part. Indeed, it is just a reverse of the proof for the first part. Hence, we can actually simplify the proof as follows:
Proof. For every , Thus, we have .
Using this proof, we can prove the set equality directly (set equals set if for every , ). (However, we should be careful about whether we really have "".) But, in many cases, the proof for reverse subset inclusion is not just simply obtained by reversing the proof for the first part, and we have to separate the proof into proofs for two subset inclusions.
We can observe that to prove different laws for the sets, we just simply use the corresponding laws in logic to prove them. Hence, the proofs for other laws, e.g., commutative law and distributive law, are similar.
Exercise. (De Morgan's law) Let and subsets of a universal set . Prove that .
Proof. For every ,
Example. Let and be subsets of a universal set . Prove that .
Proof. For every ,
Exercise. Using this result, prove that . (Hint: you may use the laws in set theory in the proof.)
Here, we just use the laws of in set theory to prove the equality of sets:
Example. Prove that for every set and , and .
Proof. For the first one, for every , (no matter is true or false, we always have the first implication.)
For the second one, for every ,
Exercise.
(a) Propose an assumption on the sets and such that we have both reverse subset inclusions, i.e., and . Prove them under this assumption.
(b) Propose an assumption on the sets and such that we have (the another reverse subset inclusion may or may not hold). Prove it under this assumption.
(c) Propose an assumption on the sets and such that we have (the another reverse subset inclusion may or may not hold). Prove it under this assumption.
(The assumptions proposed should be as weak (recall the meaning of weak in logic) as possible, so that the result can apply in more contexts.)
(a) Assumption: .
Proof. Assume . For the first one, for every , For the second one, for every ,
(One can also use the some results in set theory (e.g. , , etc.) in the proof.)
(b) Assumption: .
Proof. Assume . Then, for every ,
(c) Assumption: .
Proof. Assume . Then, for every , (We have the first implication, since if , then we have , and also since )
Exercise. Consider the statement: for every set and , . A student gives the following proof:
Proof. For every ,
Is the proof correct? If not, point out the mistake and give a correct proof.
The mistake is in this step: We have "", but do not necessarily have "", since we generally do not have , and thus we cannot show "" by contrapositive.
The following is a correct proof:
Proof. For every , On the other hand, for every ,
Example. Prove that for every set and , if and , then .
Proof. For every ,
Example. Prove that for every set and , .
Proof. For every ,
Exercise. Prove that for every set and ,
(a) .
(b) .
Proof. For every , (Notice that for the third "", we cannot change it to "" since .)
On the other hand, for every ,
Proof. For every ,
Exercise. Consider the statement:
- For every set and , if and , then .
A student provides the following proof:
Proof. Assume and . For every ,
Is the proof correct? If not, point out the mistake and give a correct proof.
The proof is correct.
Example. Prove that for every set and .
Proof. For every ,
Exercise. Prove that for every set and . (Hint: you may find the property useful.)
Proof. For every ,
Remark.
- The reverse subset inclusion does not hold. For instance, take and . Then, and . We can see that there is not reverse subset inclusion in this case.
Example. Let and be sets. Prove that if and only if .
Proof. "" direction: Assume . Then, for every set , Thus, we have .
"" direction: Assume . Then, for every , Thus, .
We can also prove the "" direction more simply:
Assume . Since for every set ,