Proofs by Case (2)

Write clear and complete proofs by cases for the mathematical statement.

(2) If x is a real number, then |x - 1| + |x + 5| >= 6.

Proof. Assume that x is a real number. Consider the following cases:

Case 1: Assume that x  < -5. In this case x - 1 < 0, and x + 5 < 0. So |x -1| = -(x - 1) = 1 - x, and |x + 5| = -(x + 5) = -5 - x. Then

|x - 1| + |x + 5| = 1 - x - 5 - x = -4 - 2x > -4 -2(-5) = -4 + 10 = 6.

So in this case |x - 1| + |x + 5| >= 6.

Case 2: Assume that -5 =< x < 1. In this case x - 1 < 0, and x + 5 >= 0.

So |x - 1| = -(x - 1) = 1 - x, and |x + 5| = x + 5. Then

|x - 1| + |x + 5| = 1 - x + x + 5 = 6 >= 6.

Case 3: Assume that x >= 1. In this case x - 1 < 0, and x + 5 >= 0. So

|x - 1| = x -1 and |x + 5| = x + 5. Then

|x - 1| + |x+5| = x - 1 + x + 5 = 2x + 4 >= 2(1) + 4 = 6

So in all cases |x - 1| + |x + 5| >= 6.

QED

Proofs by Case (1)

Write clear and complete proofs by case for the following statement.

(1) If x is a real number, then |x + 3| - x > 2.

Proof. Assume that x is a real number.

- Case 1: Assume that x >= -3, so that x + 3 >= 0. In this case |x + 3| = x + 3. So we have

              |x + 3| - x = x + 3 - x = 3 > 2.

- Case 2: Now assume that x < - 3, so that x + 3 < 0. In this case |x + 3| = -(x + 3) = - 3 - x. So we have

|x + 3| - x = - 3 - x -x = - 2x - 3 > -2(-3) -3 = 6 - 3 = 3 > 2.

So in all cases |x+3| - x > 2.

QED

Direct Proofs (4)

(4) If m is odd, then m^2 + 1 is even.

Proof. Assume that m is odd. Then m = 2k + 1 for some integer k. So
       
          m^2 + 1 = (2k +1)^2 + 1
                        = 4k^2 + 4k + 1 + 1
                        = 4k^2 + 4k +2
                        = 2(2k^2 + 2k + 1)
                        = 2q

where q = 2k^2 + 2k + 1 is an integer. So m^2 + 1 is even.

QED

Basic Proofs Methods II

Two-part proof of P <=> Q
(i) Show P => Q by any method.
(ii) Show Q => P by any method.
Therefore, P => Q

Example. Let a be a prime, and b and c be positive integers. Prove that a divides the product bc if and only if a divides b or a divides c.

Proof.
(i) Suppose a is a prime and a divides bc. By the Fundamenta Theorem of Arithmetic, b and c may be written uniquely as products of primes: b = p1p2p3...pkq1q2q3...qr. Since a is a prime and a divides bc, a is one of the prime factors of bc. Thus, either a = pi for some i or a = qj for some j. If a = pi, then a divides b. If a = qj, then a divides c. Therefore, either a divides b or a divides c.
(ii) Suppose a divides b or a divides c.If a divides b, then a divides bc. If a divides c, then again a divides bc. In either case, a divides bc.

QED

Number Theory-Divisibility (1)

Proper divisor. We say that a is a proper divisor of b if a | b and a < b.

For example, 3 is a proper divisor of 6, but 6 is not a proper divisor of 6. Note that for any b, all divisors of b are proper except for b itself.

Nontrivial divisor. We say that a is a nontrivial divisor of b if a | b and 1 < a < b.

For example, the nontrivial divisors of 6 are 2 and 3. Note that 1 is a proper divisor of every large integer, but 1 has no trivial divisors. The following theorem states some properties of divisibility.

Theorem 2.1
Properties of Divisibility
D1: 1 | a and a | a for all a.
D2: If a | b, then a =< b
D3: If a | b and b | a, then a = b.
D4: If a | b and b | c, then a | c.
D5: For all c, a | b if and only if ac | bc.
D6: If a | b and c | d, then ac | bd
D7: If a | b and a | c, then a | (bx + cy) for all x, y

Proof of D2: If a | b, then by proper division, b = ka for some k >= 1, so ka >=a, that is b >=a.
QED

Proof D4: If a | b and b | c, then b = ka and c = jb for some k and j. Therefore c = k(ka) = (jk)a, so a | c.
QED

Proof of D7: If a |b and a | c, then b = ka and c = ja for some j, k. Therefore, bx + cy = (ka)x + (ja)y =
(kx + jy)a, so a | (bx + cy).
QED

Remarks
In order to prove that m = n, it is sometimes convenient to use D3, that is, to prove that m | n and n | m.

Number Theory-Divisibility

Definition 2.1 Divisibility
We say that a divides b, and we write a|b if b = ka for some k.
For example, 3|12, since 12 = 4 * 3, also 8|40, since 40 = 5 * 8. If a|b, we might also say "a is a divisor of b", "a is a factor of b", or " "b is a multiple of a". If a does not divide b, then we write a |/ b. For example, 3 |/ 14; also, 8 |/ 42.

Logic-Basic Proof Methods II

Proof by contraposition P => Q
Suppose ~Q.
     .
     .
     .
Therefore, ~P ( via direct proof)
Thus, ~Q => ~P.
Therefore, P => Q.

QED

Example. Let m be an integer. Prove that if m^2 is odd, then m is odd.
In this example the symbol "^" means power.

Proof. Supposed m is not odd. [Suppose ~Q.] Then m is even. Thus, m = 2k for some integer k. Then m^2 = (2k)^2 = 4k^2 = 2 (2k^2). Since m^2 is twice the integer  2k^2, m^2 is even. [Deduce ~P.] Thus, if m is even, then m^2 is even; so, by contraposition, if m^2 is odd, then m is odd.

Example. Let x and y be real numbers such that x , 2y. [The second assumption (~Q) begins our proof by contraposition.]  then 2y - x > 0 and 3x - y > 0. Therefore, (2y - x)(3x - y) = 7x - 3x^2 -2y^2 > 0. Hence, 7xy > 3x^2 + 2y^2. We have shown that if 3x > y, then 7xy > 3x^2 + 2y^2. We conclude that if 7xy <=(equal sign) 3x^2 + 2y^2, then 3x <=(equal sign) y.

QED

Example. Prove that the graphs of y = x^2 + x + 2 and y = x - 2 do not intersect.

Proof. Suppose that the graphs of y = x^2 + x + 2 and y = x - 2 do intersect at some point (a,b0. [Suppose ~P.] Since (a,b) is a point on both graphs, b= a^2 + a +2 and b = a -2. Therefore, a-2 = a^2 +a +2, so a^2 = -4. Thus, a^2 < 0. But a is a real number, so a >=0. This is impossible..[ The statement a^2 < 0 ^(and) a^2 >= 0 is a contradiction.] Therefore, the graphs do not intersect.

QED

Proof of P by Contradiction
Suppose ~P.
     .
     .
     .
Therefore, Q.
Hence, Q ^ ~Q, a contradiction.
Thus, P.

QED

Example.
Prove that square root(2), or sqrt(2) is an irrational number.

Proof. Suppose that sqrt(2) is a irrational number. [Assume ~P.] Then sqrt(20 = s/t, where s and t are integers. Thus, 2 = s^2/t^2, and 2t^2 = s^2. Since s^2 and t^2 are squares, s^2 contains an even number of 2's as prime factors [This is our Q statement.], and t^2 contains an even number of 2's. But then 2t^2 contains an odd number of 2's as factors. Since 2t^2 = s^2, s^2 has an odd number of 2's. [This statement ~Q.] This is a contradiction, because s^2 cannot have  both an even and an odd number of 2's as factors. We conclude that sqrt(2) is irrational.

QED

Logic-Basic Proof methods I

A few of the basic tautologies we shall refer to are

P v ~ P    Excluded middle
(P => Q) <=> (~Q => ~P)   Contrapositive
P v (Q v R) <=> (P v Q) v R   Associative
P ^ (Q ^ R <=> (P ^ Q) ^ R    Associative
P ^ (Q v R) <=> (P ^ Q) v (P ^ R)   Distributive
P v (Q ^ R) <=> (P v Q) ^ (P v R)   Distributive
(P <=> Q) <=> (P => Q) ^ (Q => P)   Biconditional
~(P => Q) <=> P ^ ~Q   Denial of implication
~(P ^ Q)<=> ~P v ~Q    De morgan's law
~(P v Q) <=> ~P ^ ~Q   De morgan's law
P <=> (~P => (Q ^ ~ Q))  Contradiction
[(P => Q) ^ (Q => R)] => (P => R)   Transitivity
[P ^ (P => Q) => Q    Modus Poenus

Direct Proof of P => Q

Assume P.
     .
     .
     .
Therefore, Q.
Thus P => Q

QED

Example. Suppose a, b, and c are integers. Prove that if a divides b and b divides c, then a divides c.

Proof. [For a direct proof, we assume the antecedent, which is "a divides b and b divides c." Our goal is to derive the consequent, "a divides c," as our last step.] Suppose a, b, and c are integers, and that a divides b and b divides c. [We now rewrite these assumptions by using the definition of "divides," so that we have some equation to work with.] Then b = ak for some integer k, and c = bj for some integer j. [To show that a divides c, we have to write c as a multiple of a.] Therefore, c = bj = (ak)j = a(kj), so a divides b and b divides c, a divides c.

QED

Direct Proofs (3)

Write clear and complete direct proofs for each of the following mathematical statements.

If m is even and n is odd, then mn + 3n is odd.

Proof. Assume that m is even and n is odd. So m = 2k and n = 2j + 1 for some integers k and j. Then
           mn + 3n = (2k)(2j + 1) + 3(2j + 1)
                         = 4kj + 2k + 6j + 3
                         = 4kj + 2k + 6j + 2 + 1
                         = 2(2kj + k + 3j + 1) + 1
                         = 2q + 1

where q = 2kj + k + 3j + 1 is an integer. So mn + 3n is odd.

QED

Direct Proofs (2)

Write clear and complete direct proofs for the following mathematical statement.
(2) If x | a and y | b, then a = xm and b = yn for some integers m and n. Then

                                       ab = (xm)(yn)
                                           = xy(mn)
                                           = (xy)q

where q = mn is an integer. Thus xy | ab as desired.

QED

Truth Tables (5)

(5) He will fail the biochemistry exam unless he studies all week.

P := He fails the biochemistry exam.
Q := He studies all week.

So our statement is P unless Q which is equivalent to (~Q) => P or

If he does not study all week, then he will fail the biochemistry exam. or
If he passes the biochemistry exam, then he studied all week.

Truth Tables (4)

(4) I will buy a new car only if I win the lottery.

P := I will buy a new car.
Q := I will win the lottery.

So our statement is P only if Q which is equivalent to P => Q or

If I buy a new car, then I won the lottery. or
If I don't win the lottery, then I won't buy a new car.

Truth tables (3)

Rewrite each of the following sentences in symbolic propositional form. Then write each sentence in conditional (If...then...) form.

(3) She is not tall or she does not have brown eyes.

P := She is tall.
Q := She has brown eyes.

So our statement is (~P) v (~Q) which is equivalent to (~(~Q)) => (~P) or
Q => (~P) or

If she has brown eyes, then she is not tall. or
If she is tall, then she does not have brown eyes.

Truth tables-(2)

Rewrite each of the following sentences in symbolic propositional form. Then write each sentence in conditional (if...then...) form.
(2) The food is cold or the food is bad.

P := The food is cold.
Q := The food is bad.

So our statement is P v Q which is equivalent to P v(~(~Q)) or
(~Q) => P or

If the food is not bad, then the food is cold. or
If the food is not cold, then the food is bad.

Truth Tables-(1)

Example 1: Rewrite each of the following sentences in symbolic propositional form. Then write each sentence in conditional (If...then...) form.

(1) It will rain or it will not hail.
P := It will rain.
Q := It will hail.
So our statement is P v (~Q) which is equivalent to Q => P or
If it hails, then it will rain. or
If it does not rain, then it will not hail.

Direct Proofs

Write clear and complete direct proofs for each of the following mathematical statements.
(1) If x | a and x | b, then x | (a^2 - b^2).
Proof. Assume that x | a and x | b, then   we know that a = xm, and b = xn for some integers m and n. Now
a^2 - b^2 = (xm)^2 - (xm)^2
               = x^2m^2 - x^2n^2
               = x(xm^2 - xn^2)
               = xq
where q = (xm^2 - xn^2) is an integer. Therefore x| (a^2 - b^2).

QED