Book of Proof
Page 6
matics. For example, suppose you are working with a certain circle, call it
“Circle X,” and you have available the following two pieces of information.
1. Circle X has radius equal to 3.
2. If any circle has radius r, then its area is π r2 square units.
You have no trouble putting these two facts together to get:
3. Circle X has area 9 π square units.
In doing this you are using logic to combine existing information to
produce new information. Because deducing new information is central to
mathematics, logic plays a fundamental role. This chapter is intended to
give you a sufficient mastery of it.
It is important to realize that logic is a process of deducing information
correctly, not just deducing correct information. For example, suppose we
were mistaken and Circle X actually had a radius of 4, not 3. Let’s look at
our exact same argument again.
1. Circle X has radius equal to 3.
2. If any circle has radius r, then its area is π r2 square units.
3. Circle X has area 9 π square units.
The sentence “Circle X has radius equal to 3 .” is now untrue, and so is our
conclusion “Circle X has area 9 π square units.” But the logic is perfectly
correct; the information was combined correctly, even if some of it was
false. This distinction between correct logic and correct information is
significant because it is often important to follow the consequences of an
incorrect assumption. Ideally, we want both our logic and our information
to be correct, but the point is that they are different things.
34
Logic
In proving theorems, we apply logic to information that is considered
obviously true (such as “Any two points determine exactly one line.” ) or is
already known to be true (e.g., the Pythagorean theorem). If our logic is
correct, then anything we deduce from such information will also be true
(or at least as true as the “obviously true” information we began with).
2.1 Statements
The study of logic begins with statements. A statement is a sentence
or a mathematical expression that is either definitely true or definitely
false. You can think of statements as pieces of information that are either
correct or incorrect. Thus statements are pieces of information that we
might apply logic to in order to produce other pieces of information (which
are also statements).
Example 2.1
Here are some examples of statements. They are all true.
If a circle has radius r, then its area is π r2 square units.
Every even number is divisible by 2.
2 ∈ Z
p2 ∉Z
N ⊆ Z
The set {0, 1, 2} has three elements.
Some right triangles are isosceles.
Example 2.2
Here are some additional statements. They are all false.
All right triangles are isosceles.
5 = 2
p2 ∉R
Z ⊆ N
{0, 1, 2} ∩ N = ;
Example 2.3
Here we pair sentences or expressions that are not state-
ments with similar expressions that are statements.
NOT Statements:
Statements:
Add 5 to both sides.
Adding 5 to both sides of x − 5 = 37 gives x = 42.
Z
42 ∈ Z
42
42 is not a number.
What is the solution of 2x = 84?
The solution of 2x = 84 is 42.
Statements
35
Example 2.4
We will often use the letters P, Q, R and S to stand for
specific statements. When more letters are needed we can use subscripts.
Here are more statements, designated with letters. You decide which of
them are true and which are false.
P : For every integer n > 1, the number 2n − 1 is prime.
Q : Every polynomial of degree n has at most n roots.
R : The function f (x) = x2 is continuous.
S1 : Z ⊆ ;
S2 : {0, −1,−2} ∩ N = ;
Designating statements with letters (as was done above) is a very useful
shorthand. In discussing a particular statement, such as “The function
f (x) = x2 is continuous,” it is convenient to just refer to it as R to avoid
having to write or say it many times.
Statements can contain variables. Here is an example.
P : If an integer x is a multiple of 6, then x is even.
This is a sentence that is true. (All multiples of 6 are even, so no matter
which multiple of 6 the integer x happens to be, it is even.) Since the
sentence P is definitely true, it is a statement.
When a sentence or
statement P contains a variable such as x, we sometimes denote it as P(x)
to indicate that it is saying something about x. Thus the above statement
can be denoted as
P(x) : If an integer x is a multiple of 6, then x is even.
A statement or sentence involving two variables might be denoted
P(x, y), and so on.
It is quite possible for a sentence containing variables to not be a
statement. Consider the following example.
Q(x) : The integer x is even.
Is this a statement? Whether it is true or false depends on just which
integer x is. It is true if x = 4 and false if x = 7, etc. But without any
stipulations on the value of x it is impossible to say whether Q(x) is true or
false. Since it is neither definitely true nor definitely false, Q(x) cannot be
a statement. A sentence such as this, whose truth depends on the value
of one or more variables, is called an open sentence. The variables in
an open sentence (or statement) can represent any type of entity, not just
numbers. Here is an open sentence where the variables are functions:
36
Logic
R( f , g) : The function f is the derivative of the function g.
This open sentence is true if f (x) = 2x and g(x) = x2. It is false if f (x) = x3
and g(x) = x2, etc. We point out that a sentence such as R( f , g) (that
involves variables) can be denoted either as R( f , g) or just R. We use the
expression R( f , g) when we want to emphasize that the sentence involves
variables.
We will have more to say about open sentences later, but for now let’s
return to statements.
Statements are everywhere in mathematics. Any result or theorem
that has been proved true is a statement. The quadratic formula and the
Pythagorean theorem are both statements:
p
−b ± b2 − 4ac
P : The solutions of the equation ax2 + bx + c = 0 are x =
.
2a
Q :
If a right triangle has legs of lengths a and b and hypotenuse of
length c, then a2 + b2 = c2.
Here is a very famous statement, so famous, in fact, that it has a name.
It is called Fermat’s last theorem after Pierre Fermat, a seventeenth-
century French mathematician who scribbled it in the margin of a notebook.
R : For all numbers a, b, c, n ∈ N with n > 2, it is the case that an+bn 6= cn.
Fermat believed this statement was true. He noted that he could prove
it was true, except his notebook’s margin was too narrow to contain his
proof. It
is doubtful that he really had a correct proof in mind, for after his
death generations of brilliant mathematicians tried unsuccessfully to prove
that his statement was true (or false). Finally, in 1993, Andrew Wiles of
Princeton University announced that he had devised a proof. Wiles had
worked on the problem for over seven years, and his proof runs through
hundreds of pages. The moral of this story is that some true statements
are not obviously true.
Here is another statement famous enough to be named. It was first
posed in the eighteenth century by the German mathematician Christian
Goldbach, and thus is called the Goldbach conjecture:
S : Every even integer greater than 2 is a sum of two prime numbers.
You must agree that S is either true or false. It appears to be true, because
when you examine even numbers that are bigger than 2, they seem to
be sums of two primes: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7,
Statements
37
100 = 17 + 83 and so on. But that’s not to say there isn’t some large even
number that’s not the sum of two primes. If such a number exists, then S
is false. The thing is, in the over 260 years since Goldbach first posed this
problem, no one has been able to determine whether it’s true or false. But
since it is clearly either true or false, S is a statement.
This book is about the methods that can be used to prove that S (or
any other statement) is true or false. To prove that a statement is true,
we start with obvious statements (or other statements that have been
proven true) and use logic to deduce more and more complex statements
until finally we obtain a statement such as S. Of course some statements
are more difficult to prove than others, and S appears to be notoriously
difficult; we will concentrate on statements that are easier to prove.
But the point is this: In proving that statements are true, we use logic
to help us understand statements and to combine pieces of information
to produce new pieces of information. In the next several sections we
explore some standard ways that statements can be combined to form new
statements, or broken down into simpler statements.
Exercises for Section 2.1
Decide whether or not the following are statements. In the case of a statement,
say if it is true or false, if possible.
1. Every real number is an even integer.
2. Every even integer is a real number.
3. If x and y are real numbers and 5x = 5y, then x = y.
4. Sets Z and N.
5. Sets Z and N are infinite.
6. Some sets are finite.
7. The derivative of any polynomial of degree 5 is a polynomial of degree 6.
8. N ∉ P(N).
9. cos(x) = −1
10. (R × N) ∩ (N × R) = N × N
11. The integer x is a multiple of 7.
12. If the integer x is a multiple of 7, then it is divisible by 7.
13. Either x is a multiple of 7, or it is not.
14. Call me Ishmael.
15. In the beginning, God created the heaven and the earth.
38
Logic
2.2 And, Or, Not
The word “and” can be used to combine two statements to form a new
statement. Consider for example the following sentence.
R1 : The number 2 is even and the number 3 is odd.
We recognize this as a true statement, based on our common-sense under-
standing of the meaning of the word “and.” Notice that R1 is made up of
two simpler statements:
P : The number 2 is even.
Q : The number 3 is odd.
These are joined together by the word “and” to form the more complex
statement R1. The statement R1 asserts that P and Q are both true. Since
both P and Q are in fact true, the statement R1 is also true.
Had one or both of P and Q been false, then R1 would be false. For
instance, each of the following statements is false.
R2 : The number 1 is even and the number 3 is odd.
R3 : The number 2 is even and the number 4 is odd.
R4 : The number 3 is even and the number 2 is odd.
From these examples we see that any two statements P and Q can
be combined to form a new statement “P and Q.” In the spirit of using
letters to denote statements, we now introduce the special symbol ∧ to
stand for the word “and.” Thus if P and Q are statements, P ∧ Q stands
for the statement “P and Q.” The statement P ∧ Q is true if both P and Q
are true; otherwise it is false. This is summarized in the following table,
called a truth table.
P
Q
P ∧ Q
T
T
T
T
F
F
F
T
F
F
F
F
In this table, T stands for “True,” and F stands for “False.” (T and F are
called truth values.) Each line lists one of the four possible combinations
or truth values for P and Q, and the column headed by P ∧Q tells whether
the statement P ∧ Q is true or false in each case.
And, Or, Not
39
Statements can also be combined using the word “or.” Consider the
following four statements.
S1 : The number 2 is even or the number 3 is odd.
S2 : The number 1 is even or the number 3 is odd.
S3 : The number 2 is even or the number 4 is odd.
S4 : The number 3 is even or the number 2 is odd.
In mathematics, the assertion “P or Q” is always understood to mean that
one or both of P and Q is true. Thus statements S1, S2, S3 are all true,
while S4 is false. The symbol ∨ is used to stand for the word “or.” So if P
and Q are statements, P ∨ Q represents the statement “P or Q.” Here is
the truth table.
P
Q
P ∨ Q
T
T
T
T
F
T
F
T
T
F
F
F
It is important to be aware that the meaning of “or” expressed in the
above table differs from the way it is often used in everyday conversation.
For example, suppose a university official makes the following threat:
You pay your tuition or you will be withdrawn from school.
You understand that this means that either you pay your tuition or you
will be withdrawn from school, but not both. In mathematics we never use
the word “or” in such a sense. For us “or” means exactly what is stated
in the table for ∨. Thus P ∨ Q being true means one or both of P and Q
is true. If we ever need to express the fact that exactly one of P and Q is
true, we use one of the following constructions:
P or Q, but not both.
Either P or Q.
Exactly one of P or Q.
If the university official were a mathematician, he might have qualified
his statement in one of the following ways.
Pay your tuition or you will be withdrawn from school, but not both.
Either you pay your tuition or you will be withdrawn from school.
40
Logic
&nb
sp; To conclude this section, we mention another way of obtaining new
statements from old ones. Given any statement P, we can form the new
statement “It is not true that P.” For example, consider the following
statement.
The number 2 is even.
This statement is true. Now change it by inserting the words “It is not
true that” at the beginning:
It is not true that the number 2 is even.
This new statement is false.
For another example, starting with the false statement “2 ∈ ;,” we get
the true statement “It is not true that 2 ∈ ;.”
We use the symbol ∼ to stand for the words “It’s not true that,” so
∼ P means “It’s not true that P.” We often read ∼ P simply as “not P.”
Unlike ∧ and ∨, which combine two statements, the symbol ∼ just alters
a single statement. Thus its truth table has just two lines, one for each
possible truth value of P.
P
∼ P
T
F
F
T
The statement ∼ P is called the negation of P. The negation of a
specific statement can be expressed in numerous ways. Consider
P : The number 2 is even.
Here are several ways of expressing its negation.
∼ P : It’s not true that the number 2 is even.
∼ P : It is false that the number 2 is even.
∼ P : The number 2 is not even.
In this section we’ve learned how to combine or modify statements with
the operations ∧, ∨ and ∼. Of course we can also apply these operations
to open sentences or a mixture of open sentences and statements. For
example, (x is an even integer) ∧ (3 is an odd integer) is an open sentence
that is a combination of an open sentence and a statement.
Conditional Statements
41
Exercises for Section 2.2
Express each statement or open sentence in one of the forms P ∧ Q, P ∨ Q, or ∼ P.
Be sure to also state exactly what statements P and Q stand for.
1. The number 8 is both even and a power of 2.
2. The matrix A is not invertible.
3. x 6= y
4. x < y
5. y ≥ x
6. There is a quiz scheduled for Wednesday or Friday.
7. The number x equals zero, but the number y does not.
8. At least one of the numbers x and y equals 0.
9. x ∈ A − B
10. x ∈ A ∪ B
11. A ∈ ©X ∈ P(N) : |X | < ∞ª
12. Happy families are all alike, but each unhappy family is unhappy in its own
way. (Leo Tolstoy, Anna Karenina)
13. Human beings want to be good, but not too good, and not all the time.