Page 111 - Discrete Mathematics and Its Applications

90 1 / The Foundations: Logic and Proofs
EXAMPLE 18
“Proof:" Suppose that n is not positive. Because the conditional statement “If n is positive, then
2
2
n is positive” is true, we can conclude that n is not positive.
Solution: Let P (n) and Q(n) be as in the solution of Example 16. Then our hypothesis is ¬P (n)
2
and the statement “If n is positive, then n is positive” is the statement ∀n(P (n) → Q(n)).
From the hypothesis ¬P (n) and the statement ∀n(P (n) → Q(n)) we cannot conclude ¬Q(n),
because we are not using a valid rule of inference. Instead, this is an example of the fallacy of
denying the hypothesis. A counterexample is supplied by n =−1, as in Example 16. ▲
Finally, we briefly discuss a particularly nasty type of error. Many incorrect arguments are
based on a fallacy called begging the question. This fallacy occurs when one or more steps of
a proof are based on the truth of the statement being proved. In other words, this fallacy arises
when a statement is proved using itself, or a statement equivalent to it. That is why this fallacy
is also called circular reasoning.
2
Is the following argument correct? It supposedly shows that n is an even integer whenever n is
an even integer.
2
2
Suppose that n is even. Then n = 2k for some integer k. Let n = 2l for some integer l.
This shows that n is even.
Solution: This argument is incorrect. The statement “let n = 2l for some integer l” occurs in
the proof. No argument has been given to show that n can be written as 2l for some integer l.
This is circular reasoning because this statement is equivalent to the statement being proved,
namely, “n is even.” Of course, the result itself is correct; only the method of proof is wrong. ▲
Making mistakes in proofs is part of the learning process. When you make a mistake that
someone else finds, you should carefully analyze where you went wrong and make sure that
you do not make the same mistake again. Even professional mathematicians make mistakes in
proofs. More than a few incorrect proofs of important results have fooled people for many years
before subtle errors in them were found.
Just a Beginning
We have now developed a basic arsenal of proof methods. In the next section we will introduce
other important proof methods. We will also introduce several important proof techniques in
Chapter 5, including mathematical induction, which can be used to prove results that hold for
all positive integers. In Chapter 6 we will introduce the notion of combinatorial proofs.
In this section we introduced several methods for proving theorems of the form ∀x(P(x) →
Q(x)), including direct proofs and proofs by contraposition. There are many theorems of this
type whose proofs are easy to construct by directly working through the hypotheses and def-
initions of the terms of the theorem. However, it is often difficult to prove a theorem without
resorting to a clever use of a proof by contraposition or a proof by contradiction, or some
other proof technique. In Section 1.8 we will address proof strategy. We will describe various
approaches that can be used to find proofs when straightforward approaches do not work. Con-
structing proofs is an art that can be learned only through experience, including writing proofs,
having your proofs critiqued, and reading and analyzing other proofs.