Direct Proofs

In a direct proof of the statement we employ the transitive nature of implication. That is to say that if and then it follows that . To start off the proof we assume that p is a true statement. From this we deduce an implied statement . From we deduce an implied statement and so on until we obtain an implication . Using the transitive property of implication we then deduce the validity of the theorem statement. The idea is very simple but the problem is what are these implied statements ? These are results in their own right and may be obtained from other theorems, corollaries or lemmas. In other words, they are known true statements. Alternatively, they may be obtained from definitions. Undoubtedly, then, we have to know some of the implications of the statement . In other words, what does a given piece of information tell us. The bad news is that a given statement might make us think of several consequences and only a few of those facts might be used in the proof. The worst case is that a given statement means absolutely nothing. So the difficulty in a direct proof is finding these connections between certain facts. For example, suppose we know that x is a prime number. What does that tell us? Here are some possible connections.

• Only positive divisors are 1 and itself
• If x is not two then it is an odd integer
• If x is odd then it is of the form 4k+1 or 4k-1 for some integer k.

Essentially we need to build in our memory a list of facts and implications. This comes down to knowing as much information as possible. One might compare a direct proof to crossing a river using stepping stones. Standing on the river bank is knowing the statement p. Getting across the river is deducing the statement q. The stepping stones are the intermediate statements each of which is a consequence of the other. From each stone, you may have a choice of several stones to reach next and you have to decide which one is best for you. The worst scenario is to have no stones on which to step!

The skill of knowing which implications to use gets better with practice and experience. However, one cannot over emphasize the fact that it is necessary to have knowledge of other results.

There is one particular warning we should give here. In knowing the answer to a problem we were unable to solve by ourselves, we sometimes work backwards to see how we could have derived that answer. This often gives us more insight into the problem. In a direct proof of a conditional statement we do know the answer (namely q). This time, assuming the answer and working backwards does not work and certainly is not a proof. In first attempts at proofs, students often assume q and derive a true statement such as ``1 = 1'' and conclude that q is true. This is incorrect from many points of view. First of all, their ``proof'' may never use the statement p. What they have proved is . Secondly, the statement ``1=1'' is true (in fact a tautology) and so is true whenever q is true but is also true if q is false. Thirdly, at best the student has proved the converse statement which is not equivalent to the original. Think about the statement ``If x is odd then 2x is even'' and why 2x being even does not imply that x is odd.