An Introduction To Mathematical Proofs Notes For Math 3034: Jimmy T. Arnold
An Introduction To Mathematical Proofs Notes For Math 3034: Jimmy T. Arnold
An Introduction To Mathematical Proofs Notes For Math 3034: Jimmy T. Arnold
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
Jimmy T. Arnold
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
1
TABLE OF CONTENTS
1.1. Statements
1.2. Statement Forms, Logical Equivalence, and Negations
1.3. Quantifiers
1.4: Definitions
2
NOTATION
Symbol Set
R The set of all real numbers
R+ The set of all positive real numbers
R# The set of all nonzero real numbers
Q The set of all rational numbers
Q+ The set of all positive rational numbers
Q# The set of all nonzero rational numbers
Z The set of all integers
Z+ The set of all positive integers
Z# The set of all nonzero integers
Mm×n (S) The set of all m × n matrices with entries from the set S.
3
CHAPTER 1: THE STRUCTURE OF MATHEMATICAL STATEMENTS
Definition 1: A statement (or proposition) is an assertion that is true or false but not
both.
Solution:
4
We now introduce “connectives” that can be used to combine two or more given
statements to obtain a new statement. Let P and Q be statements.
P Q P ∨Q
T T T
disjunction P or Q P ∨Q T F T
F T T
F F F
Comments
(a) Other terms that mean “and” are but and also.
(b) The mathematical “or” is always used in the “inclusive” sense; that is, if both P and
Q are true then P ∨ Q is also true.
In common English usage, “or” is sometimes used in an “exclusive” sense; that is, one or
the other, but not both, is true. A statement such as “You may have coke or pepsi,” is
likely meant in the exclusive sense.
Exercise 2: With statements P and Q as defined below, write each of the statements in
(a) – (f) symbolically and state whether the statement is true or false.
√
P : 4 is an even integer. Q: 3 < 17
√
(a) 4 is an even integer and 3 < 17.
√
(b) 4 is an even integer and 3 ≥ 17.
√
(c) 4 is an odd integer and 3 ≥ 17.
√
(d) 4 is an even integer or 3 < 17.
√
(e) 4 is an odd integer or 3 < 17.
√
(f) 4 is an odd integer or 3 ≥ 17.
5
Exercise 3: Write the statement “19 is neither even nor divisible by 3” in symbolic
form using the notation:
P : 19 is even Q: 19 is divisible by 3
Implication
Comments
(a) Note that the implication P → Q is true whenever P is false. For example the
statement “If 4 is an odd integer then 18 is prime,” is a true statement.
(b) Following are some of the various English expressions that translate to P → Q.
• If P then Q.
• P implies Q.
• P only if Q.
• Q when P .
• Q is necessary for P .
• P is sufficient for Q.
One way to remember these is to remember that in an implication, certain key words
always refer to the hypothesis and others to the conclusion. The following table
summarizes some of these.
Terms for P and Q in the implication P → Q
P Q
hypothesis conclusion
if only if
sufficient necessary
6
Exercise 4: In each of the following you are given statements P and Q and an
implication involving P and Q. In each problem determine if the given statement is P → Q
or Q → P . Also determine if the given statement is true or false.
√
(a) 5 = 7 whenever 3 = 2 .
√
P: 5 = 7 Q: 3 = 2.
Equivalence
7
The Converse and Contrapositive
Exercise 6: For each statement in (a) – (d) write both the converse and contrapositive of
the given statement. In each case, determine whether the given statement is true or false,
state whether the converse is true or false, and state whether the contrapositive is true or
false.
√
(a) If 3 < 17 then 4 is not a prime integer.
√
(b) If 3 ≥ 17 then 4 is not a prime integer.
√
(c) If 3 < 17 then 4 is a prime integer.
√
(d) If 3 ≥ 17 then 4 is is a prime integer.
8
1.1 EXERCISES
1.1.2. In each of (a) – (i) determine the value(s) of a and/or b for which the statement is
true.
1.1.3. Identify the hypothesis and conclusion in each of the following implications.
9
1.1.5. Suppose the following statements are all true:
• Either Joe will pass Math 3034 or he will get a job flipping hamburgers.
Determine whether or not Joe will get a job flipping hamburgers. Explain your reasoning.
1.1.6. Knights always tell the truth but knaves never tell the truth. In a group of three
individuals (who we will label as #1, #2, and #3) each is either a knight or a knave. Each
makes a statement:
#1: “We are all three knaves.”
#2: “Two of us are knaves and one of us is a knight.“
#3: “I am a knight and the other two are knaves.”
Which are knights and which are knaves? Explain your reasoning.
1.1.7. The prom is Saturday night and the following facts are known:
• Either Mike is not taking Jen or Jason is going with Debbie.
• If Jason goes with Debbie and Bill stays home then Sue will go with Robbie.
• Bill is staying home but Sue will not go with Robbie.
Is Mike taking Jen to the prom? Justify your answer.
10
Section 1.2. STATEMENT FORMS, LOGICAL EQUIVALENCE, AND
NEGATIONS
Logical Equivalence
Definition 1: Two statement forms are logically equivalent provided they have the
same truth values for all possible truth values of the component variables.
Notation: If R and S are statement forms, we will write R ⇐⇒ S to mean that R and S
are logically equivalent.
One method for determining whether two statement forms are logically equivalent is to
construct a truth table that compares their truth values for all possible truth values of
the component variables. The proofs of the following theorems will illustrate.
Theorem 1: An implication and its contrapositive are logically equivalent; that is, for
components P and Q,
(P → Q) ⇐⇒ (∼ Q → ∼ P ).
Proof:
P Q ∼P ∼ Q P → Q ∼ Q →∼ P
T T F F T T
T F F T F F
F T T F T T
F F T T T T
Theorem 2: An implication and its converse are not logically equivalent; that is, for
components P and Q,
(P → Q) ⇐⇒ (Q → P ).
11
Proof:
P Q P →Q Q→P
T T T T
T F F T
F T T F
F F T T
Note that in the second and third rows the implication and its converse have different truth
values.
(P → Q) ⇐⇒ (∼ P ∨ Q).
Proof:
P Q ∼P P →Q ∼P ∨Q
T T F T T
T F F F F
F T T T T
F F T T T
12
there are no double negatives. The following theorem provides the basic rules for writing
useful negations.
Proof of (b):
P Q ∼P ∼ Q P ∧ Q ∼ (P ∧ Q) ∼ P ∨ ∼ Q
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T
Proof of (d): Using Theorem 3, and parts (a) and (c) of Theorem 4, note that
∼ (P → Q) ⇐⇒ ∼ (∼ P ∨ Q) ⇐⇒ (∼ (∼ P )∧ ∼ Q) ⇐⇒ (P ∧ ∼ Q).
Example 1: Give a useful and logically equivalent formulation for the statement form
∼ [P → (∼ Q → R)].
Solution:
Exercise 1: Give a useful and logically equivalent form of each of the following.
a. ∼ [(P ∧ ∼ Q) → R]
b. ∼ [P → (Q∨ ∼ R)]
c. ∼ [P ∧ (Q → R)]
13
Exercise 2: In each of (a) – (d):
(i) Write the statement in symbolic form. (This requires assigning labels to the
components.)
More Equivalencies
Terminology: A statement form T that is true for all truth values of its components is
called a tautology. A statement form C that is false for all truth values of its components
is called a contradicition.
14
6. Universal Bound Laws (a) P ∨ T ⇐⇒ T
(b) P ∧ C ⇐⇒ C
Proof of 3(a): We will prove 3(a) with a truth table. Note that there are three
components in the statement form and for each component there are two possible truth
values – true or false. Thus, the total number of possibilities (that is, the number of lines
in the truth table) is 23 = 8.
P Q R Q∨R P ∧ (Q ∨ R) P ∧ Q P ∧ R (P ∧ Q) ∨ (P ∧ R)
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T F F F F
F T F T F F F F
F F T T F F F F
F F F F F F F F
Note that columns 5 and 8 of the table have the same truth values, thus proving 3(a).
Example 3: Use the basic equivalences of Theorems 3 and 5 to prove that the statement
forms P → (Q ∨ R) and (P ∧ ∼ Q) → R are logically equivalent.
Proof: P → (Q ∨ R) ⇐⇒ ∼ P ∨ (Q ∨ R) ⇐⇒ (∼ P ∨ Q) ∨ R ⇐⇒ ∼ (∼ P ∨ Q) →
R ⇐⇒ (P ∧ ∼ Q) → R.
Comment: We will later find the equivalence given in Example 3 to be quite useful. To
prove a statement of the form P → (Q ∨ R) involves assuming P and trying to conclude
the awkward form (Q ∨ R). If we substitute the equivalent form, (P ∧ ∼ Q) → R, we begin
with two hypotheses, P and ∼ Q, and need only to prove the single conclusion R.
15
SECTION 1.2: EXERCISES
1.2.2. Use truth tables to determine whether or not each of the following pairs of
statement forms are logically equivalent.
(a) ∼ (P → Q) and ∼ P → ∼ Q.
(b) (P → Q) → R and (P → R) → Q.
(i) Use the assigned variables and the symbols ∼, ∧, and ∨ to write the statement in
symbolic form;
(ii) Write a useful (simplified) negation of the statement in symbolic form; and
1.2.4. Give the converse, the contrapositive, and the negation (in useful form) of each of
the following statement forms.
(a) (P ∨ Q) → R
(b) (P ∧ Q) → R
(c) P → (∼ Q ∧ R)
(d) (P → Q) → R
(e) P → (Q → R)
16
1.2.6. Use a truth table to prove Theorem 5, part 3(b).
1.2.7. Use the Theorems of Section 1.2 to prove the following equivalencies.
(a) [(P ∨ Q) → R] ⇐⇒ [(P → R) ∧ (Q → R)]
(b) [P → (Q → R)] ⇐⇒ [(P ∧ Q) → R]
(c) [(P → Q) → R] ⇐⇒ [(∼ P → R) ∧ (Q → R)]
1.2.8. The famous detective, Hercule Poirot, has arrived at the following facts.
• The statement, “if Col. Mustard did not commit the murder then neither Miss
Scarlet nor Mr. Green committed the murder” is false.
• Either Miss Scarlet did not commit the murder or the weapon was a candlestick.
• If the weapon was a candlestick then Col. Mustard committed the murder.
17
Section 1.3: QUANTIFIERS
Let P (x) denote an open statement. Associated with the variable x is a universal set (or
domain) Ux such that for each a ∈ Ux , P (a) is a statement; that is, P (a) is either true or
false.
The truth set of P (x) is the set of values in Ux for which P (x) becomes a true statement.
Solution: Let Q(x, y) denote the open statement 2x + y 2 = 6. Note that the universal
sets for x and y are given to be the set R of real numbers. Thus, the given statement has
18
symbolic form (∃x, y ∈ R) Q(x, y). Since Q(3, 0) is a true statement, the given statement is
also true.
19
Exercise 2: In each of the following open statements, the universal sets are
Ux = Uy = R, where R denotes set of all real numbers.
(i) write the statement as an English sentence that communicates the universal set for
each variable; and
Theorem 1 (Rules for Negations): Let P (x) denote an open statement. Then
(a) ∼ [(∃x ∈ Ux ) P (x)] ⇐⇒ (∀x ∈ Ux ) ∼ P (x).
(b) ∼ [(∀x ∈ Ux ) P (x)] ⇐⇒ (∃x ∈ Ux ) ∼ P (x).
20
Example 4: Give a useful logically equivalent form for the negation of:
Exercise 3: Give a useful, logically equivalent form for the negation of each of the
following:
(a) (∀ x) [(∃ y) P (x, y) ∧ (∀ z) (∃ w) Q(x, z, w)]
(b) (∀ x) [(∃ y) P (x, y) → (∀ z) Q(x, z) ∧ (∃ w) ∼ R(x, w, z) ]
(a) For every real number y there is a positive real number x such that y = ln x.
(b) For every positive real number y there exist real numbers x and z such that
y = x2 − 1 and y = ez .
21
Example 6: Consider the statement:
For all real numbers x, if x2 − 5x + 6 = 0 then either x = 2 or x = 3.
(i) Assign a universal set to each variable, label each component statement with a
symbol, and write the given statement symbolically;
(i) Assign a universal set to each variable, label each component statement with a
symbol, and write the given statement symbolically;
(a) For integers m and n, if m + n is even, then both m and n are even.
(b) For√every positive integer n, if n is not prime then there exists a prime integer p such
that p ≤ n and p is a factor of n.
22
SECTION 1.3: EXERCISES
1.3.1. In each of (a) – (c), give a useful negation of the statement form.
(a) (∀x ∈ Ux ) [(∃y ∈ Uy ) P (x, y) ∨ (∀z ∈ Uz ) Q(x, z)].
(b) (∃x ∈ Ux ) (∀y ∈ Uy ) P (x, y) → (∀z ∈ Uz ) Q(x, z) ∨ (∃w ∈ Uw ) R(x, w) .
(c) (∃x ∈ Ux ) (∀y ∈ Uy ) P (x, y) → (∀z ∈ Uz ) (∃w ∈ Uw ) Q(x, z, w)∧ ∼ R(x, z, w) .
(i) Label all the components (e.g. P(x): x > 0; Q(x): x2 = 1.) then give a symbolic
representation of the statement using the given universal set.
(ii) Give the symbolic form of a useful negation of the statement.
(iii) Give a useful written negation of the statement.
1.3.4. Statement: For every pair of real numbers a and b, either a < b or b < a.
Ua = Ub = R, the set of all real numbers.
1.3.5. Statement: For all real numbers a and b there exists a real number c such that
a + c = 2 and b + c = 3.
Ua = Ub = Uc = R, the set of all real numbers.
1.3.6. In each of (a) and (b), give the contrapositive of the given statement form.
(a) (∃x ∈ Ux ) (∀y ∈ Uy ) P (x, y) → (∀z ∈ Uz ) Q(x, z) ∨ (∃w ∈ Uw ) R(x, w) .
(b) (∃x ∈ Ux ) (∀y ∈ Uy ) P (x, y) → (∀z ∈ Uz ) (∃w ∈ Uw ) Q(x, z, w)∧ ∼ R(x, z, w) .
(a) For all real numbers x and y, if x < y then there exists a rational number r such that
x < r < y.
(b) For every real number x, if 0 < x < 1 then there exists a positive real number such
that < x < 1 − .
23
Section 1.4: DEFINITIONS
We will not have occasion to negate an entire definition. Associated with every definition
“x is a term,” however, is the corresponding definition of “x is not a term”. This definition
has the general form
24
Example 3:
Definition: A function f is bounded on the real numbers provided there exists a
positive real number M such that for every real number x, |f (x)| < M .
For the definition above:
(a) Write the definition in symbolic form.
(b) Give the symbolic form of the definition of: f is not bounded on the real numbers.
(c) Write out a useful definition of: f is not bounded on the real numbers.
Solution: (a) Uf is the set of all functions defined on the set of real numbers.
UM = R+ , the set of positive real numbers.
Ux = R, the set of all real numbers.
N (f ): f is bounded on the real numbers.
P (f, M, x): |f (x)| < M .
Symbolic Form: (∀f ) [ N (f ) ↔ (∃M ∈ R+ ) (∀x ∈ R) P (f, M, x)].
(b) (∀f ) [ ∼ N (f ) ↔ (∀M ∈ R+ ) (∃x ∈ R) ∼ P (f, M, x)].
(c) A function f is not bounded on the real numbers provided for every positive real
number M there exists a real number x such that |f (x)| ≥ M .
Exercise 1:
Definition: A real number u is a least upper bound for a set A of real numbers
provided a ≤ u for every a ∈ A and for every positive real number there exists b ∈ A such
that u − < b.
(a) For the definition above use the assignment of symbols below to write the definition
in symbolic form.
Uu = R, where R is the set of all real numbers.
UA is the set of all subsets of R.
U = R+ , the set of positive real numbers.
Ua = Ub = A.
N (u, A): u is a least upper bound for a set A of real numbers
P (a, u): a ≤ u.
Q(b, , u): u − < b.
(b) Give the symbolic form of the definition of: u is not a least upper bound for a set A
of real numbers.
(c) Write out a useful definition of: u is not a least upper bound for a set A of real
numbers.
25
Some Definitions
We conclude this section with some definitions that will be useful in our later proofs.
Definition 1: An integer n is even provided there exists an integer k such that n = 2k.
Definition 3: The integer b divides the integer a provided there exists an integer c such
a = bc.
Definition 4: An integer p is prime provided p > 1 and the only positive divisors of p
are 1 and p.
Comment: Note that there is a hidden (i.e., unnamed) variable in this definition;
specifically, no symbol is given for a positive divisor of p.
An alternate form of the definiton of prime is:
An integer p is prime provided p > 1 and for every positive integer d, if d divides p then
either d = 1 or d = p.
26
SECTION 1.4: EXERCISES
27
(a) Write the given definition in symbolic form using the following assignments:
Uf : all functions that map the reals into the reals.
Ua = UL = Ux : all real numbers.
U = Uδ : all positive real numbers
N (f, a, L): limx→a f (x) = L
P (x, a, δ): |x − a| < δ
Q(f, x, L, ): |f (x) − L| <
(b) Give the symbolic form of the definition of: limx→a f (x) = L.
(c) Write out a useful definition of: limx→a f (x) = L.
28