Direct and Indirect Proofs

To prove a formula of the form " x (p(x)) is false, prove the negation of the formula, which is $ x (~ p(x)), is true. You can prove the negation is true by an example. Such example is called a counter example. In the example, you must come up with an x such that p(x) is false.

To prove a formula of the form p ® q is false, prove the negation of the formula, which is p Ù ~ q, is true. You can prove the negation is true by an example. Such example is called a counter example. In the example, p must be true and q must be false.

Caution:
You cannot prove formulas of the form " x (p(x)) or the form p ® q are true by an example. For example, if you're given the formula "every integer is greater than 9", you cannot say the formula is true because 10 is an integer greater than 9. In fact, the formula is false, because, for example, 8 is an integer and it's not greater than 9.

To prove a theorem (i.e. to prove a formula is true), you can do that either directly (one of the direct proof techniques is proof by cases), or indirectly (such as proof by contrapositive and proof by contradiction). Why indirect proofs? Because sometimes they are easier than direct proofs. For example, to prove a formula of the form p ® q is true, it might be easier to prove ~q ® ~p is true (i.e. to prove the contrapositive). Remember the contrapositive of an implication is equivalent to the implication. Thus, if proving p ® q is true is difficult, try to prove it by contrapositive. I.e. assume q is false and then prove p is false. Remember: To prove p ® q is true directly, you have to assume p is true and then prove q is true. Note that p ® q is false only if p is true and q is false. So, to prove p ® q is true, you will have to dimiss this case. Now to prove a formula is true by contradiction, assume the conclusion is false and then reach a statement/formula contradicting the hypothesis or contradicting a known fact. Now to prove a formula of the form p « q is true directly, prove p ® q is true and prove q ® p is true (remember p « q is the same as (p ® q) Ù (q ® p)). Finally, to prove something like "p, q and r are equivalent" (note we might have more than 3 formulas, e.g. p, q, r, and s), it suffices to prove: p ® q is true, q ® r is true, and r ® p is true (if this is difficult, you may rearrange p, q, and r, and then prove the first implies the second, the second implies the third, and the third implies the first). Or you may prove "p, q and r are equivalent" (note we might have more than 3 formulas, e.g. p, q, r, and s), by proving: p º q, q º r (if this is difficult, you may rearrange p, q, and r, and then prove the first is equivalent to the second and the second is equivalent to the third). Remember if p º q and q º r, then p º r.

Remark:
The following are the same:
  1. All prime numbers are odd.
  2. Every prime number is odd.
  3. There are no even prime numbers.
  4. N is prime ® N is odd.
  5. If n is a prime number, then n is odd.

Facts we will use in this section:
  1. Ö2 is irrational.
  2. N is an even integer iff there exists an integer m such that n = 2m.
  3. N is an odd integer iff there exists an integer m such that n = 2m+1 (sometimes we may write n = 2m-1 instead).

Exercises:
Prove or disprove the following (if the formula is false, write down a counterexample or write down a proof; if the formula is true, prove it):
  1. If n is a prime number, then n2 + n + 41 is prime.
  2. If the average of 5 different positive integers is 15, then one of the integers is greater than 16.
  3. If the average of 5 positive integers is 15, then one of the integers is greater than 16.
  4. If r and s are irrational numbers, then rs is irrational.
  5. N is prime ® N is odd.
  6. If n is a prime number greater than 2, then n is odd.
  7. 2x2 - 8x + 11 ³ 3 for every real number x.
  8. For every real number x, 2x2 - 8x + 11 > 0.
  9. If x is a real number greater than 5, then 2x2 - 8x + 11 > 21.
  10. 2x2 - 8x + 11 > 21 if and only if x is a real number greater than 5.
  11. There exists a real number y such that, for every real number x, 2x2 +1 > x2 y.
  12. There exists a real number y > 3 such that, for every real number x, 2x2 +1 > x2 y.
  13. There exists x1 and x2 such that x1 < x2 and x13 - x1 > x23 -x2.
  14. Let x and y be real numbers. If x + y = -xy, then either x = y = 0 or x = y = -2.
  15. Let x and y be nonnegative real numbers. If x + y = -xy, then x = y = 0.
  16. The equation x + y = -xy has no solution in Z+.
  17. If x is an irrational number, then Öx is irrational.
  18. If a is rational and b is irrational, then a+b is irrational.
  19. If a and b are real numbers such that a+b is rational, then a and b are rational.
  20. If a and b are real numbers such that |a| ¹ |b| and a+b is rational, then a and b are rational.
  21. If a and b are real numbers such that ab is rational, then both a and b are rational.
  22. If a and b are rational, then a+b and ab are rational.
  23. If a is rational and b is irrational, then a+b is irrational.
  24. If a is nonzero rational and b is irrational, then ab is irrational.
  25. If a is an odd integer, then there is an integer b such that either a = 4b+3 or a = 4b+1.
  26. If n is an odd prime, then n2+4 is prime.
  27. If n is an odd prime, then n2+4 is an odd prime.
  28. If n is prime, then n2+4 is prime.
  29. If x is real and x3 - 5x2 + 3x = 15, then x = 5.
  30. The only solution to x3 - 5x2 - 3x = -15 in þ is x = 5.
  31. The only solution to x3 - 5x2 - 3x = -15 in ý is x = 5.
  32. Let a and b be positive integers and let m = ab. Prove that either a £ Öm or b £ Öm.
  33. Let n be an even integer. Prove that n2 is even.
  34. Let n be an integer. Prove that n2 is even iff n is even.
  35. Let n be an odd integer. Prove that n2 is odd.
  36. Let n be an integer. Prove that n2 is odd iff n is odd.
  37. Let n be an integer. Prove that n2 - 3n -18 is even.
  38. Prove that there is no largest positive integer.
  39. Prove that there is no smallest negative integer.
  40. Prove that there is no smallest positive real number.

Do the following problems from the textbook:

Section 1.3: 4 (c,e,f), 8(d,c), 10 (c,d), 11(a,d,g), 14.
Section 1.4: 3(b,c,e), 4(b,e,f).