| Chapter 0: Logic and Proofs |
|---|
x P(x) => Q(x).
A Theorem will be a major landmark in the mathematical theory, a Proposition a lesser result, while a Lemma will usually be a result that is needed to prove a Theorem or Proposition, but is not very interesting on its own.
A Corollary is a result that follows almost immediately from a Theorem.
An Example is not usually a general result, but often a particular case of a Theorem or Proposition.
An Algorithm is an explicit procedure for solving a problem in a finite number of steps.
There are many methods for proving Theorems, Propositions, and Lemmas, but there is no procedure that will apply to all proofs. It is extremely difficult to get a computer to write a good proof. Proof writing is an art that requires much practice. There is a delicate balance between writing down too many details, and leaving out logical steps that cannot easily be filled by the reader. However there are some standard strategies for attacking proofs, and we now introduce the most important of these. These methods of proof are not only important in mathematics, but also in computer science where, for example, they are used in software specification for verifying programs.
Many mathematical theorems can be expressed symbolically in the form P => Q. The statement P is called the assumption or hypothesis of the theorem and the statement Q is the conclusion. The assumption will consist of one or more statements, normally involving some variables. The theorem says that if the assumption is true, then the conclusion is true.
Proposition. If a > b and c < 0 then ac < bc.
Proof. If a > b then a-b > 0. The positive number a - b times the negative number c is negative so
( a - b ) c < 0. Hence ac - bc < 0 and ac < bc.
Proposition. Let x be a real number. Then x2 + x < 0 if and only if -1 < x < 0.
Proof. We first prove x2 + x < 0 => -1 < x < 0.
We have
x ( x + 1 ) < 0. If the product of two numbers is negative then one number is positive and the other is negative. There are two cases to consider.Case (i). If x > 0 and x+1 < 0 then x > 0 and x < - 1. This case is impossible.
Case (ii). If x < 0 and x+1 > 0 then x < 0 and x > - 1. Hence -1 < x < 0.
We now prove -1 < x < 0 => x2 + x < 0.
If -1 < x< 0 then x + 1 > 0. Since x < 0 and the product of a positive number and a negative number is negative, it follows that x ( x + 1 ) < 0. That is, x2 + x< 0.
Proof.
| P | Q | P => Q | NOT Q | NOT P | NOT Q => NOT P |
|---|---|---|---|---|---|
| T T F F | T F T F | T F T T | F T F T | F F T T | T F T T |
Proposition. Let n be an integer. If n3 is odd then n is odd.
Proof. Suppose that n is not odd; that is, suppose n is even. Then n3 will also be even; that is n3 is not odd. Hence we have shown
NOT (n is odd) => NOT ( n3 is odd ). The contrapositive isn3 is odd => n is odd which is what we had to prove.
For example, suppose we wanted to prove the statement Q. If we can show that NOT Q leads to a contradiction, then NOT Q must be false; that is, Q must be true.
Proposition. There is no real solution to x2 - 6 x + 10 = 0.
Proof. This result can be stated symbolically as
NOT ( where the universe of discourse is the set of real numbers.x x2 - 6 x + 10 = 0 )
Assume that the result is false; that is, assume that there is a real number x with x2 - 6 x + 10 = 0. Then, by completing the square, we can write this as
( x - 3 )2 + 1 = 0. However ( x - 3 )20, so the left side of this equation is greater than or equal to 1. This gives a contradiction. Hence the original statement is true.
Alternatively, suppose we wanted to prove the statement P => Q. If we assume P and NOT Q, and show that this leads to a contradiction, then P AND NOT Q is false. Hence NOT(P AND NOT Q) is true. This is equivalent to (NOT P) OR Q being true and, by Example 0.1.6, this is equivalent to P => Q being true.
Proposition. If x is a real number such that x3 + 7 x2 < 9 then show that x < 1.1.
Proof. Suppose that x is a real number such that x3 + 7 x2 < 9, but x < 1.1 is not true; that is x
x3 + 7 x2 However this gives a contradiction to the assumption that x3 + 7 x2 < 9. Hence the original result is true.
This example could also be proved by using the contrapositive law.
Other good examples of proof by contradiction are Proposition 1.5.2, Euclid's Theorem 1.5.3, and Theorem 4.2.1.
Proposition. Let m and n be integers. If m3 + n3 is odd then m is odd or n is odd.
Proof. Suppose that m3 + n3 is odd, and that m is not odd. Therefore m is even and so m3 will also be even. Hence m3 + n3 - m3 = n3 will be odd. By the result in subsection 0.3.4 it follows that n is odd, and we have shown
( m3 + n3 is odd ) AND NOT ( m is odd ) => ( n is odd ). This is equivalent to the statement that was to be proved, namely( m3 + n3 is odd ) => (m is odd ) OR ( n is odd ).
Another good example of this type of proof is in Theorem 1.5.4.