Page 103 - Discrete Mathematics and Its Applications

82 1 / The Foundations: Logic and Proofs

theorems needs to include a universal quantifier, the standard convention in mathematics is to
omit it. For example, the statement
2
2
“If x> y, where x and y are positive real numbers, then x >y .”
really means
2
2
“For all positive real numbers x and y,if x> y, then x >y .”
Furthermore, when theorems of this type are proved, the first step of the proof usually involves
selecting a general element of the domain. Subsequent steps show that this element has the
property in question. Finally, universal generalization implies that the theorem holds for all
members of the domain.

Methods of Proving Theorems

Proving mathematical theorems can be difficult. To construct proofs we need all available am-
munition, including a powerful battery of different proof methods. These methods provide the
overall approach and strategy of proofs. Understanding these methods is a key component of
learning how to read and construct mathematical proofs. One we have chosen a proof method,
we use axioms, definitions of terms, previously proved results, and rules of inference to com-
plete the proof. Note that in this book we will always assume the axioms for real numbers
found in Appendix 1. We will also assume the usual axioms whenever we prove a result about
geometry. When you construct your own proofs, be careful not to use anything but these axioms,
definitions, and previously proved results as facts!
To prove a theorem of the form ∀x(P (x) → Q(x)), our goal is to show that P(c) → Q(c)
is true, where c is an arbitrary element of the domain, and then apply universal generalization.
In this proof, we need to show that a conditional statement is true. Because of this, we now focus
on methods that show that conditional statements are true. Recall that p → q is true unless p is
true but q is false. Note that to prove the statement p → q, we need only show that q is true if p
is true. The following discussion will give the most common techniques for proving conditional
statements. Later we will discuss methods for proving other types of statements. In this section,
and in Section 1.8, we will develop a large arsenal of proof techniques that can be used to prove
a wide variety of theorems.
When you read proofs, you will often find the words “obviously” or “clearly.” These words
indicate that steps have been omitted that the author expects the reader to be able to fill in.
Unfortunately, this assumption is often not warranted and readers are not at all sure how to fill in
the gaps. We will assiduously try to avoid using these words and try not to omit too many steps.
However, if we included all steps in proofs, our proofs would often be excruciatingly long.

Direct Proofs

A direct proof of a conditional statement p → q is constructed when the first step is the
assumption that p is true; subsequent steps are constructed using rules of inference, with the
final step showing that q must also be true. A direct proof shows that a conditional statement
p → q is true by showing that if p is true, then q must also be true, so that the combination
p true and q false never occurs. In a direct proof, we assume that p is true and use axioms,
definitions, and previously proven theorems, together with rules of inference, to show that q
must also be true.You will find that direct proofs of many results are quite straightforward, with a
fairly obvious sequence of steps leading from the hypothesis to the conclusion. However, direct
proofs sometimes require particular insights and can be quite tricky. The first direct proofs we
present here are quite straightforward; later in the text you will see some that are less obvious.
We will provide examples of several different direct proofs. Before we give the first example,
we need to define some terminology.