Exam 2 Material
Math symbols: ≠ , ∤ ,⋲ , ∉, ℤ
∞ (Infinity)
∑ (Summation)
Chapter 4. More on Direct Proof and Proof by Contrapositive
4.1.Proofs Involving Divisibility of Integers
For integers a and b with a ≠ 0 , we say that a divides b if there exists an integer c such that b=ac. W denote this by a|b
Example 1
Ex. n is an integer <=> 2|n
If a|b, then we also say that b is a multiple of a and that a is a divisor of b.
If a does not divide b, we denote this by a|b. by a ∤ b
Example 2
Example prove: Let a,b and c be integers with a≠0 and b≠0. If a divides b and b divides c, then a divides c.
Proof.
Since a divides b and b divides c, b=ax and c=by for some x,y, b=ax and c=by for some x,y ⋲ ℤ . So cd=axby=abxy. Since x,y ⋲ ℤ , ab divides cd.
Example 3:
Prove: Let a,b,c,x,y ⋲ ℤ where a ≠ 0. If a divides b and a divides c, then a divides bx+cy.
Proof: Assume that a divides both b and c. Then b=an and c=am for some n, m ⋲ ℤ. By substituting these expressions into bx + cy, we have bx + cy = (an)x + (am)y = a(nx + my), which shows that a divides bx + cy. This completes the proof, demonstrating that if a divides both b and c, then a must also divide the linear combination bx + cy.
Explanation of Implication and Its Contrapositive
Implication Statement: A statement of the form “∀x ∈ S,P(x) =⇒ Q(x),” means "For all x in the set S, if P(x) is true, then Q(x) is also true."Here, ( P(x) ) is known as the premise or hypothesis, and ( Q(x) ) is known as the conclusion.
Contrapositive: The contrapositive of the statement “∀x ∈ S,∼Q(x) =⇒ ∼P(x).”. This means, "For all x in S, if Q(x) is not true, then P(x) is also not true."It is important to note that the quantifier (( \forall )) remains unchanged or unnegated in the contrapositive statement.
Proof by Contrapositive Method:
State the Original Implication: Start with the original statement ∀x ∈ S,P(x) =⇒ Q(x),
Write the Contrapositive: Convert the implication into its contrapositive form, “∀x ∈ S,∼Q(x) =⇒ ∼P(x).”
Prove the Contrapositive: To prove that the implication( P(x) ⇒ Q(x) ) holds, demonstrate that if ( Q(x) ) is false, then ( P(x) ) must also be false for all elements x in S.
Duplicating Proves and Restatements of Theorem 3.12
Statement: If x is even, then x² is even.
Proof by Direct Proof: For any integer x, if x is an even integer, we can express it as x = 2k for some integer k. Therefore,
[ x² = (2k)² = 4k² = 2(2k²) ]
Since 2k² is an integer, x² is even.
Converse Statement: If x² is odd, then x is odd.
Proof by Contrapositive: To show the contrapositive, we restate: If x is even, then x² is even.
Assume x is an even integer, so we express it as x = 2k for some integer k. Then:
[ x² = (2k)² = 4k² = 2(2k²) ]
Hence, x² is even, verifying the contrapositive. This establishes that if x² is odd, then x must be odd.
Relation to Theorem 3.12
Theorem 3.12 states:
If x is even, then x² is even.
If x² is even, then x is even.
The contrapositive of these implications are:
If x² is odd, then x is odd.
If x is odd, then x² is odd.
Thus, the statements in this section restate Theorem 3.12 in terms of contrapositives and do not require separate proof.
Alternative Restatement of Theorem 3.12
One possible restatement of the theorem is:
"The square of every even integer is even."
Proof by Contrapositive
Overview
When proving a result or theorem expressed in the form:
Let x ∈ S. If P(x), then Q(x), or
For all x ∈ S, if P(x), then Q(x), it is essential to establish the truth of the implication P(x) ⇒ Q(x) for all x ∈ S.
Contrapositive Approach
If it can be shown that (∼Q(x)) ⇒ (∼P(x)) holds true for all x ∈ S, then P(x) ⇒ Q(x) is also true for all x ∈ S. A proof by contrapositive essentially takes the form:
Let x ∈ S. If ∼Q(x), then ∼P(x), or
For all x ∈ S, if ∼Q(x), then ∼P(x).
Thus, to provide a proof by contrapositive of the result:
Assume ∼Q(x) is true for an arbitrary element x ∈ S and demonstrate that ∼P(x) is true for that element.
Application of Proof by Contrapositive
Some results are better suited for proof by contrapositive.
Example: Result 3.10
Statement: Let x ∈ ℤ. If 5x−7 is even, then x is odd.
Proof: Assume that x is even. Then x can be expressed as x = 2a for some integer a. Therefore:5x − 7 = 5(2a) − 7 = 10a − 7 = 10a − 8 + 1 = 2(5a − 4) + 1.Since 5a − 4 ∈ ℤ, it follows that 5x − 7 is odd.Thus, establishing that if 5x − 7 is even, then x must be odd.
To prove the statement 'For any real number m, if 3m + 5 is odd, then m is even,' we can use proof by contrapositive.
Contrapositive: If m is odd, then 3m + 5 is even.
Proof by Contrapositive:
Assume m is odd. Therefore, we can express m as m = 2k + 1 for some integer k.
Substituting this into the expression:
3m + 5 = 3(2k + 1) + 5 = 6k + 3 + 5 = 6k + 8.
We can factor out 2 from the expression:
6k + 8 = 2(3k + 4).
Since 3k + 4 is an integer, it follows that 2(3k + 4) is even.
Thus, if m is odd, then 3m + 5 is even, establishing that the original statement holds.
To prove the statement 'For any real number m, if 3m + 5 is odd, then m is even,' we can use proof by contrapositive.
Contrapositive: If m is odd, then 3m + 5 is even.
Proof by Contrapositive:
Assume m is odd. Therefore, we can express m as m = 2k + 1 for some integer k.
Substituting this into the expression:
3m + 5 = 3(2k + 1) + 5 = 6k + 3 + 5 = 6k + 8.
We can factor out 2 from the expression:
6k + 8 = 2(3k + 4).
Since 3k + 4 is an integer, it follows that 2(3k + 4) is even.
Thus, if m is odd, then 3m + 5 is even, establishing that the original statement holds.
Corollary: For any integer n, n is odd if and only if n² is odd.
Proof:
(Forward direction): Assume n is odd. Then n can be expressed as n = 2k + 1 for some integer k. Therefore:
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.
Since 2k² + 2k is an integer, n² is odd.
(Reverse direction): Assume n² is odd. Then n² can be expressed as n² = 2m + 1 for some integer m. If n were even (n = 2p for some integer p), then n² = (2p)² = 4p², which is even. Thus, n must be odd for n² to be odd.