Book of Proof
Page 9
logical structure and meanings of the sentences. Sometimes it is necessary
or helpful to parse them into expressions involving logic symbols. This may
be done mentally or on scratch paper, or occasionally even explicitly within
the body of a proof. The purpose of this section is to give you sufficient
practice in translating English sentences into symbolic form so that you
can better understand their logical structure. Here are some examples:
Example 2.8
Consider the Mean Value Theorem from Calculus:
If f is continuous on the interval [a, b] and differentiable on (a, b), then
f (b)−f (a)
there is a number c ∈ (a, b) for which f 0(c) =
b−a
.
Here is a translation to symbolic form:
³
´
³
´
¡ f
f (b)−f (a)
cont. on [a, b]¢ ∧ ¡ f is diff. on (a, b)¢ ⇒ ∃ c ∈ (a, b), f 0(c) =
b−a
.
56
Logic
Example 2.9
Consider Goldbach’s conjecture, from Section 2.1:
Every even integer greater than 2 is the sum of two primes.
This can be translated in the following ways, where P is the set of prime
numbers and S = {4, 6, 8, 10, . . .} is the set of even integers greater than 2.
¡n ∈ S¢ ⇒ ¡∃ p, q ∈ P, n = p + q¢
∀ n ∈ S, ∃ p, q ∈ P, n = p + q
These translations of Goldbach’s conjecture illustrate an important
point. The first has the basic structure (n ∈ S) ⇒ Q(n) and the second has
structure ∀ n ∈ S, Q(n), yet they have exactly the same meaning. This is
significant. Every universally quantified statement can be expressed as a
conditional statement.
Fact 2.2
Suppose S is a set and Q(x) is a statement about x for each
x ∈ S. The following statements mean the same thing:
∀ x ∈ S, Q(x)
(x ∈ S) ⇒ Q(x).
This fact is significant because so many theorems have the form of
a conditional statement. (The Mean Value Theorem is an example!) In
proving a theorem we have to think carefully about what it says. Sometimes
a theorem will be expressed as a universally quantified statement but it will
be more convenient to think of it as a conditional statement. Understanding
the above fact allows us to switch between the two forms.
We close this section with some final points. In translating a state-
ment, be attentive to its intended meaning. Don’t jump into, for example,
automatically replacing every “and” with ∧ and “or” with ∨. An example:
At least one of the integers x and y is even.
Don’t be led astray by the presence of the word “and.” The meaning of
the statement is that one or both of the numbers is even, so it should be
translated with “or,” not “and”:
(x is even) ∨ ( y is even).
Finally, the logical meaning of “but” can be captured by “and.” The
sentence “The integer x is even, but the integer y is odd,” is translated as
(x is even) ∧ ( y is odd).
Negating Statements
57
Exercises for Section 2.9
Translate each of the following sentences into symbolic logic.
1. If f is a polynomial and its degree is greater than 2, then f 0 is not constant.
2. The number x is positive but the number y is not positive.
p
3. If x is prime then
x is not a rational number.
4. For every prime number p there is another prime number q with q > p.
5. For every positive number ε, there is a positive number δ for which |x − a| < δ
implies | f (x) − f (a)| < ε.
6. For every positive number ε there is a positive number M for which |f (x)−b| < ε,
whenever x > M.
7. There exists a real number a for which a + x = x for every real number x.
8. I don’t eat anything that has a face.
9. If x is a rational number and x 6= 0, then tan(x) is not a rational number.
10. If sin(x) < 0, then it is not the case that 0 ≤ x ≤ π.
11. There is a Providence that protects idiots, drunkards, children and the United
States of America. (Otto von Bismarck)
12. You can fool some of the people all of the time, and you can fool all of the people
some of the time, but you can’t fool all of the people all of the time. (Abraham
Lincoln)
13. Everything is funny as long as it is happening to somebody else. (Will Rogers)
2.10 Negating Statements
Given a statement R, the statement ∼ R is called the negation of R. If R
is a complex statement, then it is often the case that its negation ∼ R can
be written in a simpler or more useful form. The process of finding this
form is called negating R. In proving theorems it is often necessary to
negate certain statements. We now investigate how to do this.
We have already examined part of this topic. DeMorgan’s laws
∼ (P ∧ Q) = (∼ P) ∨ (∼ Q)
(2.6)
∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)
(2.7)
(from Section 2.6) can be viewed as rules that tell us how to negate the
statements P ∧ Q and P ∨ Q. Here are some examples that illustrate how
DeMorgan’s laws are used to negate statements involving “and” or “or.”
58
Logic
Example 2.10
Consider negating the following statement.
R : You can solve it by factoring or with the quadratic formula.
Now, R means (You can solve it by factoring) ∨ (You can solve it with Q.F.),
which we will denote as P ∨ Q. The negation of this is
∼ (P ∨ Q) = (∼ P) ∧ (∼ Q).
Therefore, in words, the negation of R is
∼ R : You can’t solve it by factoring and you can’t solve it with
the quadratic formula.
Maybe you can find ∼ R without invoking DeMorgan’s laws. That is good;
you have internalized DeMorgan’s laws and are using them unconsciously.
Example 2.11
We will negate the following sentence.
R : The numbers x and y are both odd.
This statement means (x is odd) ∧ ( y is odd), so its negation is
∼ ¡(x is odd) ∧ (y is odd)¢ = ∼ (x is odd) ∨ ∼ (y is odd)
= (x is even) ∨ (y is even).
Therefore the negation of R can be expressed in the following ways:
∼ R : The number x is even or the number y is even.
∼ R : At least one of x and y is even.
Now let’s move on to a slightly different kind of problem. It’s often
necessary to find the negations of quantified statements. For example,
consider ∼ (∀ x ∈ N, P(x)). Reading this in words, we have the following:
It is not the case that P(x) is true for all natural numbers x.
This means P(x) is false for at least one x. In symbols, this is ∃ x ∈ N, ∼ P(x).
Thus ∼ (∀ x ∈ N, P(x)) = ∃ x ∈ N, ∼ P(x). Similarly, you can reason out that
∼ (∃ x ∈ N, P(x)) = ∀ x ∈ N, ∼ P(x). In general:
∼ (∀ x ∈ S, P(x)) = ∃ x ∈ S, ∼ P(x),
(2.8)
∼ (∃ x ∈ S, P(x)) = ∀ x ∈ S, ∼ P(x).
(2.9)
Negating Statements
59
Example 2.12
&nb
sp; Consider negating the following statement.
R : The square of every real number is non-negative.
Symbolically, R can be expressed as ∀ x ∈ R, x2 ≥ 0, and thus its negation is
∼ (∀ x ∈ R, x2 ≥ 0) = ∃ x ∈ R, ∼ (x2 ≥ 0) = ∃ x ∈ R, x2 < 0. In words, this is
∼ R : There exists a real number whose square is negative.
Observe that R is true and ∼ R is false. You may be able to get ∼ R
immediately, without using Equation (2.8) as we did above. If so, that is
good; if not, you will probably be there soon.
If a statement has multiple quantifiers, negating it will involve several
iterations of Equations (2.8) and (2.9). Consider the following:
S : For every real number x there is a real number y for which y3 = x.
This statement asserts any real number x has a cube root y, so it’s true.
Symbolically S can be expressed as
∀ x ∈ R, ∃ y ∈ R, y3 = x.
Let’s work out the negation of this statement.
∼ (∀ x ∈ R, ∃ y ∈ R, y3 = x) = ∃ x ∈ R, ∼ (∃ y ∈ R, y3 = x)
= ∃ x ∈ R, ∀ y ∈ R, ∼ (y3 = x)
= ∃ x ∈ R, ∀ y ∈ R, y3 6= x.
Therefore the negation is the following (false) statement.
∼ S : There is a real number x for which y3 6= x for all real numbers y.
In writing proofs you will sometimes have to negate a conditional
statement P ⇒ Q. The remainder of this section describes how to do this.
To begin, look at the expression ∼ (P ⇒ Q), which literally says “ P ⇒ Q is
false.” You know from the truth table for ⇒ that the only way that P ⇒ Q
can be false is if P is true and Q is false. Therefore ∼ (P ⇒ Q) = P∧ ∼ Q.
∼ (P ⇒ Q) = P∧ ∼ Q
(2.10)
(In fact, in Exercise 12 of Section 2.6, you used a truth table to verify that
these two statements are indeed logically equivalent.)
60
Logic
Example 2.13
Negate the following statement about a particular (i.e.,
constant) number a.
R : If a is odd then a2 is odd.
Using Equation (2.10), we get the following negation.
∼ R : a is odd and a2 is not odd.
Example 2.14
This example is like the previous one, but the constant a
is replaced by a variable x. We will negate the following statement.
R : If x is odd then x2 is odd.
As discussed in Section 2.8, we interpret this as the universally quantified
statement
R : ∀x ∈ Z, (x odd) ⇒ (x2 odd).
By Equations (2.8) and (2.10), we get the following negation for R.
∼ ¡∀x ∈ Z, (x odd) ⇒ (x2 odd)¢ = ∃x ∈ Z,∼ ¡(x odd) ⇒ (x2 odd)¢
= ∃x ∈ Z, (x odd)∧ ∼ (x2 odd).
Translating back into words, we have
∼ R : There is an odd integer x whose square is not odd.
Notice that R is true and ∼ R is false.
The above Example 2.14 showed how to negate a conditional statement
P(x) ⇒ Q(x). This type of problem can sometimes be embedded in more
complex negation. See Exercise 5 below (and its solution).
Exercises for Section 2.10
Negate the following sentences.
1. The number x is positive, but the number y is not positive.
p
2. If x is prime, then
x is not a rational number.
3. For every prime number p, there is another prime number q with q > p.
4. For every positive number ε, there is a positive number δ such that |x − a| < δ
implies | f (x) − f (a)| < ε.
5. For every positive number ε, there is a positive number M for which |f (x)−b| < ε
whenever x > M.
6. There exists a real number a for which a + x = x for every real number x.
Logical Inference
61
7. I don’t eat anything that has a face.
8. If x is a rational number and x 6= 0, then tan(x) is not a rational number.
9. If sin(x) < 0, then it is not the case that 0 ≤ x ≤ π.
10. If f is a polynomial and its degree is greater than 2, then f 0 is not constant.
11. You can fool all of the people all of the time.
12. Whenever I have to choose between two evils, I choose the one I haven’t tried
yet. (Mae West)
2.11 Logical Inference
Suppose we know that a statement of form P ⇒ Q is true. This tells us
that whenever P is true, Q will also be true. By itself, P ⇒ Q being true
does not tell us that either P or Q is true (they could both be false, or P
could be false and Q true). However if in addition we happen to know
that P is true then it must be that Q is true. This is called a logical
inference: Given two true statements we can infer that a third statement
is true. In this instance true statements P ⇒ Q and P are “added together”
to get Q. This is described below with P ⇒ Q and P stacked one atop the
other with a line separating them from Q. The intended meaning is that
P ⇒ Q combined with P produces Q.
P ⇒ Q
P ⇒ Q
P ∨ Q
P
∼ Q
∼ P
Q
∼ P
Q
Two other logical inferences are listed above. In each case you should
convince yourself (based on your knowledge of the relevant truth tables)
that the truth of the statements above the line forces the statement below
the line to be true.
Following are some additional useful logical inferences.
The first
expresses the obvious fact that if P and Q are both true then the statement
P ∧ Q will be true. On the other hand, P ∧ Q being true forces P (also Q)
to be true. Finally, if P is true, then P ∨ Q must be true, no matter what
statement Q is.
P
Q
P ∧ Q
P
P
P
∧ Q
P
∨ Q
These inferences are so intuitively obvious that they scarcely need to
be mentioned. However, they represent certain patterns of reasoning that
we will frequently apply to sentences in proofs, so we should be cognizant
of the fact that we are using them.
62
Logic
2.12 An Important Note
It is important to be aware of the reasons that we study logic. There
are three very significant reasons. First, the truth tables we studied tell
us the exact meanings of the words such as “and,” “or,” “not” and so on.
For instance, whenever we use or read the “If..., then” construction in
a mathematical context, logic tells us exactly what is meant. Second,
the rules of inference provide a system in which we can produce new
information (statements) from known information. Finally, logical rules
such as DeMorgan’s laws help us correctly change certain statements into
(potentially more useful) statements with the same meaning. Thus logic
helps us understand the meanings of statements and it also produces new
meaningful statements.
Logic is the glue that holds strings of statements together and pins down
the exact meaning of certain key phrases such as the “If..., then” or “For
all” constructions. Logic is the common language that all mathematicians
&nbs
p; use, so we must have a firm grip on it in order to write and understand
mathematics.
But despite its fundamental role, logic’s place is in the background of
what we do, not the forefront. From here on, the beautiful symbols ∧, ∨,
⇒, ⇔, ∼, ∀ and ∃ are rarely written. But we are aware of their meanings
constantly. When reading or writing a sentence involving mathematics we
parse it with these symbols, either mentally or on scratch paper, so as to
understand the true and unambiguous meaning.
CHAPTER
3
Counting
t may seem peculiar that a college-level text has a chapter on counting.
I At its most basic level, counting is a process of pointing to each object
in a collection and calling off “one, two, three,... ” until the quantity of
objects is determined. How complex could that be? Actually, counting
can become quite subtle, and in this chapter we explore some of its more
sophisticated aspects. Our goal is still to answer the question “How many? ”
but we introduce mathematical techniques that bypass the actual process
of counting individual objects.
Almost every branch of mathematics uses some form of this “sophisti-
cated counting.” Many such counting problems can be modeled with the
idea of a list, so we start there.
3.1 Counting Lists
A list is an ordered sequence of objects. A list is denoted by an opening
parenthesis, followed by the objects, separated by commas, followed by a
closing parenthesis. For example (a, b, c, d, e) is a list consisting of the first
five letters of the English alphabet, in order. The objects a, b, c, d, e are
called the entries of the list; the first entry is a, the second is b, and so
on. If the entries are rearranged we get a different list, so, for instance,
(a, b, c, d, e) 6= (b, a, c, d, e).
A list is somewhat like a set, but instead of being a mere collection of
objects, the entries of a list have a definite order. Note that for sets we
have
©a, b, c, d, eª = ©b, a, c, d, eª,
but—as noted above—the analogous equality for lists does not hold.
Unlike sets, lists are allowed to have repeated entries. For example
(5, 3, 5, 4, 3, 3) is a perfectly acceptable list, as is (S,O, S). The number of
entries in a list is called its length. Thus (5, 3, 5, 4, 3, 3) has length six, and
(S, O, S) has length three.
64
Counting
Occasionally we may get sloppy and write lists without parentheses
and commas; for instance, we may express (S, O, S) as SOS if there is no