2. METHODS OF PROOF 692. Methods of Proof2.1. Types of Proofs. Suppose we wish to prove an implication p → q. Hereare some strategies we have available to try.• Trivial Proof: If we know q is true then p → q is true regardless of thetruth value of p.• Vacuous Proof: If p is a conjunction of other hypotheses and we know oneor more of these hypotheses is false, then p is false and so p → q is vacuouslytrue regardless of the truth value of q.• Direct Proof: Assume p, and then use the rules of inference, axioms, defi-nitions, and logical equivalences to prove q.• Indirect Proof or Proof by Contradiction: Assume p and ¬q and derivea contradiction r ∧ ¬r.• Proof by Contrapositive: (Special case of Proof by Contradiction.)Give a direct proof of ¬q → ¬p. Assume ¬q and then use the rules ofinference, axioms, definitions, and logical equivalences to prove ¬p.(Can bethought of as a proof by contradiction in which you assume p and ¬q andarrive at the contradiction p ∧ ¬p.)• Proof by Cases: If the hypothesis p can be separated into cases p1∨ p2∨··· ∨ pk, prove each of the propositions,p1→ q, p2→ q, . . . , pk→ q, separately.(You may use different methods of proof for different cases.)DiscussionWe are now getting to the heart of this course: methods you can use to writeproofs. Let’s investigate the strategies given above in some detail.2.2. Trivial Proof/Vacuous Proof.Example 2.2.1. Prove the statement: If there are 100 students enrolled in thiscourse this semester, then 62= 36.Proof. The assertion is trivially true, since the conclusion is true, independentof the hypothesis (which, may or may not be true depending on the enrollment). Example 2.2.2. Prove the statement. If 6 is a prime number, then 62= 30.2. METHODS OF PROOF 70Proof. The hypothesis is false, therefore the statement is vacuously true (eventhough the conclusion is also false). DiscussionThe first two methods of proof, the “Trivial Proof” and the “Vacuous Proof” arecertainly the easiest when they work. Notice that the form of the “Trivial Proof”,q → (p → q), is, in fact, a tautology. This follows from disjunction introduction,since p → q is equivalent to ¬p ∨ q. Likewise, the “Vacuous Proof” is based on thetautology ¬p → (p → q).Exercise 2.2.1. Fill in the reasons for the following proof of the tautology ¬p →(p → q).[¬p → (p → q)] ⇔ [p ∨(¬p ∨ q)]⇔ [(p ∨ ¬p) ∨q]⇔ T ∨ q⇔ TExercise 2.2.2. Let A = {1, 2, 3} and R = {(2, 3), (2, 1)}(⊆ A × A). Prove: ifa, b, c ∈ A are such that (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R.Since it is a rare occasion when we are able to get by with one of these two methodsof proof, we turn to some we are more likely to need. In most of the following examplesthe underlying “theorem” may be a fact that is well known to you. The purpose inpresenting them, however, is not to surprise you with new mathematical facts, butto get you thinking about the correct way to set up and carry out a mathematicalargument, and you should read them carefully with this in mind.2.3. Direct Proof.Example 2.3.1. Prove the statement: For all integers m and n, if m and n areodd integers, then m + n is an even integer.Proof. Assume m and n are arbitrary odd integers. Then m and n can bewritten in the formm = 2a + 1 and n = 2b + 1,2. METHODS OF PROOF 71where a and b are also integers. Thenm + n = (2a + 1) + (2b + 1) (substitution)= 2a + 2b + 2 (associative and commutativelaws of addition)= 2(a + b + 1) (distributive law)Since m+n is twice another integer, namely, a+b+1, m+n is an even integer. DiscussionThe first strategy you should try when attempting to prove any assertion is to givea direct proof. That is, assume the hypotheses that are given and try to argue directlythat the conclusion follows. This is often the best approach when the hypothesescan be translated into algebraic expressions (equations or inequalities) that can bemanipulated to give other algebraic expressions, which are useful in verifying theconclusion.Example 2.3.1 shows a simple direct proof of a very familiar result. We are usingthe familiar definitions of what it means for an integer to be even or odd: An integern is even if n = 2k for some integer k; an integer n is odd if n = 2k + 1 for someinteger k. Study the form of this proof. There are two hypotheses, “m is an oddinteger,” and “n is an odd integer”; and the conclusion is the statement “m + n isan even integer.” This “theorem” is a quantified statement (“for all integers m andn”, or “for all odd integers m and n”). In the proof we assumed the hypotheses heldfor arbitrarily integers m and n, and then we wrote down equations that follow fromthe definition of what it means for these integers to be odd. Although this looks likea pretty obvious thing to do, at least when you see someone else do it, this step, inwhich you bring your knowledge to the problem, may seem like a big one to take, andyou may find yourself stalling out at this point.One possible reason this may happen is that you may be trying to do too muchat once. The cure for this is to be patient: take small steps, using the appropriatedefinitions and previously proven facts, and see where they lead. When we wrote downm = 2a + 1 and n = 2b + 1, we did a number of fairly sophisticated things. First, weused our knowledge (definitions) of what it means for an integer to be odd. Second,in order for this information to be useful, we needed to translate this knowledge into amathematical expression, or expressions in this case, that are subject to manipulation.And third, in setting up these expressions, we needed to use appropriate mathematicalnotation, so that we did not introduce any subtle or hidden relationships into thepicture that are unwarranted by the hypotheses.2. METHODS OF PROOF 72A common mistake of this type might arise as follows:“Well, m is an odd integer, so I can write m = 2k + 1, where k isan integer. Since n is also an odd integer, I can write n = 2k + 1,where k is an integer.”Do you see the mistake? By allowing the same letter k to represent what might bedifferent integers, we have inadvertently added another assumption, namely, that m =n! Of course, we didn’t mean to do this, but, unfortunately, our intentions haven’tbeen carried out, and so our proof breaks down at this point. In order to maintainthe “arbitrariness” of m and n, we must allow, at the least, that they be