# MA121 Lecture Notes - Lecture 3: Contraposition, List Of Theorems, Mathematical Induction

78 views4 pages

For unlimited access to Class Notes, a Class+ subscription is required.

Review Summary for the Tutorial and Written Quizzes of Lab 3

Part I.Methods of Proof for Implications

The most commonly seen expressions in mathematical theorems are implication statements in the logial form

P⇒Q(read “if P, then Q”). For example,

Let n∈Z. If 5n−9is odd, then nis even.

Implication statements may be proved using one of the following methods.

1.Direct proof

This method of proof is a valid argument consisting of explicit or implicit premises and the conclusion Q. The

statement Pmust appear as a premise.

P

other explicit premise(s) (such as the deﬁnition(s) involved)

other implicit premise(s) (such as known theorem(s) that can be applied)

∴Q

A typical, fatal mistake in using this method is to actually apply (or just simply assume) the conclusion Qas a

premise in the proof.

2.Proving its contrapositive

Because the conditional p→qis equivalent to its contrapositive ∼q→∼ p, we can prove the statement ∼Q⇒∼ P

instead and then claim the original statment is also true. In practice, it is recommended that you write an explicit

expression of ∼Q⇒∼ Pﬁrst, and then prove this new statement as a valid argument:

∼Q

other explicit premise(s) (such as the deﬁnition(s) involved)

other implicit premise(s) (such as known theorem(s) that can be applied)

∴∼P

A typical, fatal mistake in using this method is to add P,∼Por Qas a premise in proving the new statement.

3.Indirect proof by contradiction

In order to show that P→Qis true, one may argue, instead, that its negation is false. Since we have equivalences

∼(p→q)⇔ ∼ (∼p∨q)⇔(p∧ ∼ q), the argument now is that the assumption P∧ ∼ Qleads to a contradiction

statement or an absurd claim. This is equivalent to say that the original statement is true. In practice, it is

recommended that you write an explicit expression of Pand an explicit expression of ∼Qﬁrst, and then use both

of them in a valid argument as follows:

P

∼Q

other explicit premise(s) (such as the deﬁnition(s) involved)

other implicit premise(s) (such as known theorem(s) that can be applied)

∴F(a contradiction statement or an absurd claim)

A typical, fatal mistake in using this method is to write an expression of P→∼ Qand then prove or disprove

this new claim. Remember that the negation of the conditional p→qis not a conditional anymore, and the

implication that P⇒∼ Qis true or false does not mean that the implication P⇒Qis false or true accordingly!

Example 1. Let n∈Z. Prove the statement

If 5n−9is odd, then nis even

using three diﬀerent methods of proof.

Proof.Method 1:Direct Proof

Suppose that 5n−9 is odd.

By the deﬁnition of odd integers, 5n−9 = 2k+ 1 for some k∈Z.

It follows that n= 2k+ 1 −4n+ 9 = 2(k−2n+ 5).

This shows that nis even by the deﬁnition of even integers because k−2n+ 5 ∈Z.

Method 2:Proving its contrapositive

We shall prove its contrapositive:

If nis odd, then 5n−9is even.