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

78 views4 pages
11 Feb 2019
School
Department
Course
Professor

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
PQ(read “if P, then Q”). For example,
Let nZ. If 5n9is 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 definition(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 pqis 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⇒∼ Pfirst, and then prove this new statement as a valid argument:
Q
other explicit premise(s) (such as the definition(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 PQis true, one may argue, instead, that its negation is false. Since we have equivalences
(pq) (pq)(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 Qfirst, and then use both
of them in a valid argument as follows:
P
Q
other explicit premise(s) (such as the definition(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 pqis not a conditional anymore, and the
implication that P⇒∼ Qis true or false does not mean that the implication PQis false or true accordingly!
Example 1. Let nZ. Prove the statement
If 5n9is odd, then nis even
using three different methods of proof.
Proof.Method 1:Direct Proof
Suppose that 5n9 is odd.
By the definition of odd integers, 5n9 = 2k+ 1 for some kZ.
It follows that n= 2k+ 1 4n+ 9 = 2(k2n+ 5).
This shows that nis even by the definition of even integers because k2n+ 5 Z.
Method 2:Proving its contrapositive
We shall prove its contrapositive:
If nis odd, then 5n9is even.
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class