Lecture 2

Lec 2: Logic and proofs
MATH 147 Section 2, Fall Term 2022
I (We will first finish the material from Lecture 1)

I Logical statements
I Negation
I Direct and indirect proofs
I Quantifiers
I General comments about writing proofs
I (Some of this material may be covered on Monday)
Key references: Thomson, Bruckner & Bruckner text book Appendix

What is a statement?
A statement is a sentence that is either true or false (but not both). You don’t necessarily need to know
whether it is true or false.
Some examples of statements:
1. The University of Waterloo has a Faculty of Mathematics.
2. Toronto is the capital of Canada.
3. Newton made many contributions to mathematics and physics.
4. If Newton is alive, then he is teaching me MATH 147.
5. This is a statement.
6. This statement is true.
These are not statements:
1. Good afternoon.
2. The capital of Canada.
3. Is this really a math class?
4. This statement is false.

Some mathematical examples
These are mathematical statements:
1. 5 ≤ 20.
2. 5 > 20.
3. Either 5 ≤ 20 or 5 > 20.

√
4. 482 + 196 − 35 = 2070.
5. If all prime numbers are odd, then 2 is odd.
These are not mathematical statements:
6. x ≤ 20.
7. a2 + b 2 = c 2 .
8. Either x < π or x > π.
9. If n is an odd number.
6–8 are not statements because we haven’t specified the variables. They can be considered statements if we
have already introduced the variables (even if we don’t know their values).
Compound statements
To focus on logical structure, we can use symbols to represent statements. For example, let x be a (fixed) real
number. Let p be the statement “x < 20” and q be the statement “x < 10”.
We can form new statements, such as:
1. (Either) p or q. (p ∨ q.)
2. p and q. (p ∧ q.)
3. q if p. More commonly written as: If p, then q. (p ⇒ q. Equivalently: q ⇐ p.)
4. q only if p. (q ⇒ p. Equivalently: p ⇐ q.)
5. q if and only if p. (p ⇔ q. Equivalently: q ⇔ p.)

Negations
Negating a statement refers to constructing the opposite of a given statement.
Examples:
1. The negation of “Toronto is the capital of Canada” is “Toronto is not the capital of Canada.”
2. The negation of “5 ≤ 20” is “5 > 20.”
Symbolically, we write the negation of p as ¬p (read as: not p).

Direct and indirect proofs
Suppose you want to prove that the statement p is true.
In a direct proof, you use the information you are given and agreed upon rules (e.g., rules of arithmetic) to
arrive at the conclusion p.
In an indirect proof, or proof by contradiction, you assume that p is false and show that this leads to a
statement that contradicts something you know (or assumed) to be true.
Example 1
Show that there are infinitely many odd numbers.
Assume for contradiction that there are finitely many odd numbers, n1 , n2 , ..., nN , where N ∈ N. Let
Zodd = {n1 , n2 , ..., nN } be the set of all odd numbers.
Let M = max Zodd and define K = M + 2. By construction, K is greater than everything in Zodd , so K ∈
/ Zodd .
But M is an odd number, so K is also an odd number (use the definition of odd to prove this), i.e., K ∈ Zodd .
This is a contradiction, hence, there must in fact be infinitely many odd numbers.
Contraposition
We will often want to prove statements of the form p ⇒ q (implications). For example: Let n be an integer.
Show that if n2 is even, then n is even.
The direct proof approach is to assume p is true and show that q must be true.
The indirect approach is to show that p ; q is false. In other words, if p is true and q is false, then we have a
contradiction.
Another way to express this is that if q is false, then p must be false: ¬q ⇒ ¬p.
This last statement is called the contrapositive of the statement p ⇒ q.
In our example above, the contrapositive is: If n is not even, then n2 is not even.
More about implications
Note that logical implication does not necessarily mean causality.
Examples: Groundhog Day, false-implies-anything.
More definitions:
The converse of p ⇒ q is q ⇒ p.
The inverse of p ⇒ q is ¬p ⇒ ¬q.
Question
What are the relationships among the truth values of a statement, its contrapositive, its converse, and its
inverse? E.g., if one is true, does another have to be true?
Quantifiers
We use quantifiers when a statement p(x) concerns a variable x that takes values from a specified set.
Two types of quantifiers: “for all” (∀) allowed values and “there exists” (∃) some allowed value.
We can use symbols to write out mathematical statements in a compact form but it is preferable to write it out
with English words to improve readability.
Here are two examples with equivalent ways of expressing the same statements:
1. For all n ∈ N we have 1/n ≤ 1.

∀n ∈ N : 1/n ≤ 1.
∀n ∈ N, 1/n ≤ 1.
2. There exists x ∈ R such that 1/x > 1.

∃x ∈ R 3 1/x > 1.
∃x ∈ R, 1/x > 1.
It may be necessary to construct statements with nested quantifiers. Pay attention to the order!
For all a ∈ A, there exists b ∈ B such that for all c ∈ C , the statement p(a, b, c) is true.
∀a ∈ A : ∃b ∈ B 3 ∀c ∈ C : p(x, y , z).
∀a ∈ A, ∃b ∈ B, ∀c ∈ C , p(x, y , z).
Negating statements with quantifiers
When negating statements with quantifiers, replace the quantifier with the other kind and negate the following
part.
negate
∀x, p(x) −−−−→ ∃x, ¬p(x)
negate
∃x, p(x) −−−−→ ∀x, ¬p(x)
Try negating these examples:
1. 5 > 2.
2. ∀x ∈ R, x 2 ≥ 0.
3. ∀x, ∃y , ∀z : x 2 + y 2 > z.
Notice that to prove that [∀x, p(x)] is false, you just need one counterexample, i.e., just find one allowed value
of x for which p(x) is false.
To prove that [∃x, p(x)] is false, you need to show that p(x) is false for every possible choice of x.
General comments about writing proofs
I Writing proofs is a skill that takes time and practice to develop!
I Read proofs and pay attention to the structure and style.
I You want to explain logical arguments. Explicitly use words like “therefore”, “thus”, “since” to justify a
sentence from previous points.
I Make it clear what are assumptions (hypotheses) and what are deduced.
I Write in complete sentences with appropriate punctuation.
I A list of equations is not a proof.
Additional references:
https://math.berkeley.edu/~hutching/teach/proofs.pdf
https://web.cs.ucdavis.edu/~amenta/w10/writingman.pdf
http://www.math.toronto.edu/writing/MathStyleGuide.pdf

Lecture 2

Uploaded by

Copyright:

Available Formats

Lecture 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 2

Uploaded by

Copyright:

Available Formats

Lec 2: Logic and proofs

MATH 147 Section 2, Fall Term 2022

I (We will first finish the material from Lecture 1)

Key references: Thomson, Bruckner & Bruckner text book Appendix

Some examples of statements:

1. The University of Waterloo has a Faculty of Mathematics.

2. Toronto is the capital of Canada.

3. Newton made many contributions to mathematics and physics.

4. If Newton is alive, then he is teaching me MATH 147.

6. This statement is true.

These are not statements:

2. The capital of Canada.

3. Is this really a math class?

4. This statement is false.

These are mathematical statements:

3. Either 5 ≤ 20 or 5 > 20.

5. If all prime numbers are odd, then 2 is odd.

These are not mathematical statements:

8. Either x < π or x > π.

We can form new statements, such as:

3. q if p. More commonly written as: If p, then q. (p ⇒ q. Equivalently: q ⇐ p.)

4. q only if p. (q ⇒ p. Equivalently: p ⇐ q.)

5. q if and only if p. (p ⇔ q. Equivalently: q ⇔ p.)

Negating a statement refers to constructing the opposite of a given statement.

2. The negation of “5 ≤ 20” is “5 > 20.”

Symbolically, we write the negation of p as ¬p (read as: not p).

Suppose you want to prove that the statement p is true.

This last statement is called the contrapositive of the statement p ⇒ q.

Note that logical implication does not necessarily mean causality.

Examples: Groundhog Day, false-implies-anything.

The inverse of p ⇒ q is ¬p ⇒ ¬q.

1. For all n ∈ N we have 1/n ≤ 1.

2. There exists x ∈ R such that 1/x > 1.

I Writing proofs is a skill that takes time and practice to develop!

I Read proofs and pay attention to the structure and style.

I Write in complete sentences with appropriate punctuation.

I A list of equations is not a proof.

You might also like