2.3 THEOREMS OF THE PROPOSITIONAL CALCULUS n iditional). Furthermore, precisely three of the conditional statement forms
in Theorem 2 can be strengthened to biconditionals, that is, remain true if
the arrow is replaced by a double arrow. Can you determine which ones?
(See Exercise 3.)
MATHEMATICAL SIGNIFICANCE OF TAUTOLOGIES
INVOLVING THE CONDITIONALThe significance of implication statements for mathematical theorem-
proving was discussed before Theorem 2, in connection with modus ponens.
Let us see, however, how this reasoning applies to actual problems from
mathematics, with specific reference to tautologies from Theorem 2.
Suppose, for example, we wish to prove that if a function f is differen-
tiable at a, then lirn,,, f(x) exists. Suppose, furthermore, that we have at
our disposal the well-known theorem of elementary calculus, "iff is dif-
ferentiable at a, then f is continuous at a," as well as the definition "f is
continuous at a if and only if lirn,,, f(x) exists @ equals f(a)." Since f
is differentiable at a implies f is continuous at a by the known theorem
(denote by p -, q), and since f is continuous at a implies lirn,,, f(x) exists
(denote by q -+ r), we may draw the desired conclusion (which has the form
p -+ r) by (b) of Theorem 2.
As a second example, consider the famous proof that 4 is irrational
(a detailed discussion of this proof is given in Article 6.2). The proof pro-
ceeds by assuming that a is rational (denote by -p) and deducing from
this a logical contradiction of the form q A -q. Part (g) of Theorem 2 in-
dicates that whenever we can deduce a contradiction from the negation of
a statement the statement itself must be true.
Finally, consider (j) of Theorem 2. Suppose we wish to derive a con-
clusion r from hypotheses p and q. Suppose we are able to derive r from
hypothesis p alone, that is, write a proof that makes no use of hypothesis
q. By (j), if we can do this, our desired theorem is thereby also proved
(see Exercise 7).
The approach suggested in the previous paragraph is a logically valid
method of proof, but it calls for a word of warning. Perhaps we are able to
prove a theorem without using all the hypotheses given. If we can, then by
(j), we have improved upon the result we were asked to derive; that is, we
have proved a stronger statement than the one requested. But ordinarily,
theorems posed to students at the junior-senior level require all the hy-
potheses given and cannot be proved (i.e., aren't true) if a hypothesis is
omitted. Failure to use one of the hypotheses in a proof is often a telltale
sign that the proof is in error. Always check your proofs to see that you
have used all the hypotheses; if you haven't, investigate further! One addi-
tional related note: Many unsolved problems in research mathematics today
involve "strengthening" known theorems, that is, removing some hypothesis