Prueba

Morphology of Proof An introduction to rigorous proof techniques
Craig Silverstein September 26, 1998

1 Methodology of Proof | an example
get from the assumptions | the A part | to the conclusions | the B part. To prove a theorem, you combine the assumptions with de nitions and other theorems and show that the conclusion is always true. The hard part is guring out what de nitions and othertheorems to use. De nitions and theorems let you convert statements to other statements by stringing these de nitions and theorems together you can convert the statements of A into the statements of B. This constitutes a proof. For instance: Theorem 1 Let x be a number greater than or equal to 4. Then 2x x2. This theorem converts the statement \a number x is greater than or equal to 4" to \for thisnumber, 2x x2 . We can use it in the proof of another theorem, like so: Theorem 2 Let x be the sum of four squares, a2 + b2 + c2 + d2 where a, b, c, and d are positive. Then 2x x2 . If we can prove that x is of necessity greater than or equal to 4 (by noting, for instance, that a, b, c, and d are at least 1, and thus their sum is thus at least 4), then we can convert the assumption of our theoremfrom \x is the sum of four positive squares" to \x is at least 4." Then we can use the rst proof to convert the statement \x is at least 4" to \2x x2 ." This completes our proof. Often, we use de nitions to expand out mathematical shorthand before we can start applying proofs. For instance, if an assumption is \x is prime," we might need to convert it to \x has exactly two positive divisors"before continuing with the proof. If you are at a loss for how to start Here is a theorem that can be proved using these techniques. Theorem 3 Let S be a nite subset of some in nite set U . Let T be the complement of S . Prove T is in nite. Intuitively, this is saying that if you have an in nite supply of something, and you take a nite amount of it away, you are left with an in nite amount. This lastsentence may seem obvious, but it is not a proof. To obtain a rigorous proof, we must get from the assumptions to the conclusion through theorems and de nitions. We identify the assumptions: \S is a nite subset of an in nite set. It has a complement T ." A good start is to expand the de nitions in the assuption. 1
Deep down, all theorems are of the form if A then B. They may be expressed in someother way, such as all A are B or let A be true. Then B is true, but the goal in each case is to

a proof, convert all the terms in the assumptions to their de nitions.

\for all."

De nition 1 A set S is nite if there exists a number N such that the number of elements in S (denoted jSj) is less than N . If no such N exists, then S is in nite. Note that you give me the set S before I try togure out the number N . Thus, if any number N exists that is bigger than jSj, I will be sure to nd it, since I know what S is. This ordering concern (\ rst we have S , then we nd N ") is important with statements such as \there exists" or

De nition 2 If S and T are both subsets of some set U , T is the complement of S (under U ) if S T = U and S \ T is .
Now we use our de nitions to convertour assumptions:

Original statement S is nite
U is in nite

New statement
jSj < N

There is a number N such that

There is no number M such that jUj < M T is the complement of S S T = U and S \ T is We're still stuck, so we have to apply one of the proof methods which will be discussed in the next sections, which let you work backwards from the conclusion | the B part | to help prove thetheorem. In particular, we need the common proof technique of proof by contradiction: We assume that the result is false, and show that as a result, the assumptions must be false as well. But the assumptions are never false (by assumption!) so the theorem must be true. In this case, we assume the result is false, that is that T is in fact nite. Then, applying a de nition, there is a number P...