Class Notes
(811,485)

Canada
(494,756)

University of Toronto Scarborough
(30,852)

Computer Science
(300)

CSCA67H3
(56)

Anna Bretscher
(30)

Lecture

# Formal proofs

by
OneClass8101

Unlock Document

Computer Science

CSCA67H3

Anna Bretscher

Winter

Description

Proofs
Q. What is a proof?
A proof is a convincing argument that a statement is true.
Q. What makes up a proof?
• a set of basic statements that we agree are true for a spec-
iﬁed domain. E.g., if D = R then we have the basic rules
about arithmetic and inequalities.
• A series of logical steps that build on previously proven
statements.
We are concerned with the content of a proof and the structure
of the proof.
Example.
Claim 1. Let x be any natural number.
2
If x ≥ 2 then (x + 2) ≥ 16.
Proof Idea. Why do we believe this claim?
• if x ≥ 2 then x + 2 ≥ 2 + 2 = 4 by arithmetic
• squaring both sides, gives (x + 2) ≥ 16
30
www.notesolution.com 2
Claim 2. “There exists an integer x such that x +6x+9 = 0.”
Proof Idea. Why do we believe this claim?
• we can factor x +6x+9 = 0 to get (x+3)(x+3) = 0
2
• So, we know that if we let x = −3, then x + 6x + 9 = 0.
Claim 3. “There does not exist a largest natural number.”
Proof Idea. Why do we believe this claim?
• Pick any arbitrary natural number x.
• We know by basic arithmetic, that x+1 is a natural number
and larger than x.
31
www.notesolution.com Formal Proof Structure
Let’s formalize each of the previous claims.
2
Claim 1. Let xbe any natural number. If x ≥ 2 then (x + 2) ≥
16.
Q. How can we re-write Claim 1 in logical notation?
∀x ∈ N ,x ≥ 2 → (x + 2) 2 ≥ 16.
Q. How can we prove a statement for all natural numbers?
Let x be any arbitrary number.
Q. How can we formally talk about “if, then”?
We suppose that x ≥ 2 and then show that (x + 2) ≥ 16 is
true.
32
www.notesolution.com Proof
∀x ∈ N ,x ≥ 2 → (x + 2) ≥ 16
Let x be an arbitrary numberNin
Suppose x ≥ 2 .
Then, by arithmetic x + 2 ≥ 2 + 2 = 4.
And, by squaring both sides, gives (x + 2) ≥ 16
2
Therefore, x ≥ 2 → (x + 2) ≥ 16.
Since x is an arbitrary natural number, N,x ≥ 2 → (x +
2
2) ≥ 16.
33
www.notesolution.com 2
Claim 2. “There exists an intxsuch thax + 6x + 9 = 0.”
Q. In logic?
∃x ∈ Z,x + 6x + 9 = 0
Q. How can we formally prove a statement with there exists?
Pick a value for the variable.
Proof.
Letx = −3.
2 2
Then, x + 6x + 9 = (−3) + 6(−3) + 9 = 0
Thus, x + 6x + 9 = 0
2
Since x ∈Z , ∃x ∈Z,x + 6x + 9 = 0.
34
www.notesolution.com Claim 3. “There does not exist a largest natural number.”
Q. In logic?
∀x ∈ N,∃y ∈ N,x < y
Notice that we have two quantiﬁers.
Q. Does the order of the quantiﬁers matter?
yes! ∃y ∈ N ,∀x ∈ N ,x < y says that there exists a largest
number.
Proof.
Let x be an arbitrary natural number.
Let y = x + 1. Then y N .
Then, x < x + 1 = y.
Therefore, x < y.
Since y ∈N , ∃y N ,x < y
Since x is an arbitrary natural numberN,∃y ∈ N,x < y.
35
www.notesolution.com Review of Proof Structure
Universal Quantiﬁer. ∀x ∈ D,p(x) → q(x)
Let x ∈ D.
Suppose p(x)
.
.
q(x)
Therefore, p(x) → q(x)
Since x is an arbitrary element in D, ∀x ∈ D,p(x) → q(x).
Existential Quantiﬁer. ∃x ∈ D,p(x)
Let x = a speciﬁc value.
Then x ∈ D. prove this!
Proof of.p(speciﬁc value).
.
Thus, p(x).
Since x ∈ D,∃x ∈ D,p(x).
36
www.notesolution.com More Challenging Proofs.
√
Claim 4. 2 is an irrational number.
Proof Idea. Why do we believe this claim?
• Use the Fundamental Theorem of Arithmetic.
Any integer N can be represented as a product of primes.
Such a representation is unique up to the order of prime
factors.
• We will derive a contradiction.
√
• Assume that 2 is rational.
√ p
• Therefore, 2 = .q
2
• Squaring both sides: 2 = p2so 2q = p 2
q
• How many prime factors does p2 have? q2? p has twice
as many factors as p, so an even number and similarly for
q .
• What is the contradiction? We have the same number being
represented by an even number of factors and by an odd
number of factors contradicting the Fundamental Theorem
of Arithmetic.
37
www.notesolution.com Claim 4, Formalized
√
Claim 4. 2 is an irrational number.
Q. What does it mean for a number x to be rational?
There exist integers p,q such that x =
q
Q. How can we express “ 2 is an irrational number” using this
deﬁnition?
√
(⋆) ∀p ∈ Z,∀q ∈ Z, 2 ▯= .
q
Q. We only know how to prove universally quantiﬁed statements
of the form p → q. How can we convert (⋆) into this form?
√
(⋆⋆) ∀p ∈ Z,∀q ∈ Z,T → 2 ▯=p
q
Q. What is the contrapositive of (⋆⋆)?
√ p
∀p ∈ Z,∀q ∈ Z, 2 = q→ F
So we can prove the contrapositive instead of (⋆⋆)!
38
www.notesolution.com √
RTP. ∀p ∈ Z,∀q ∈ Z,T → 2 ▯=p
q
Proof by Contradiction.
Let p ∈Z .
Let q ∈ Z
√ √
Suppose 2 = p, ie.,2 is rational.
q
2
Then, 2 = 2
q
So, 2q = p 2
2
Thus, the number o2 prime factors of 2q is odd and
the number of prime factors of p is even.
This contradicts the Fun. Thm. of Arithmetic.
Therefore, F.
√
Therefore 2 = p→ F
q
√
By contrapositive, T → 2 ▯= p
q
√ p
Since q is an arbitrary integer, Z,T → 2 ▯= q
√ p
Since p is an arbitrary integer,Z∀,∀q ∈Z ,T → 2 ▯= q
39
www.notesolution.com Claim 5. The product of three consecutive natural numbers is an
even number.
Proof Idea.
Q. How can we express three consecutive numbers mathemati-
cally?
Let x ∈ N, then x,x + 1,x + 2.
Q. Why do we believe that this is true?
there will be at least one even number.
• Case 1. x is even. Then even(odd)(even) is even. Why? if x
is even then there exists k such that 2k = x and therefore,
2k(2k + 1)(2k + 2) = 2(number) = even.
• Case 2. x is odd. Then odd(even)(odd) is even. Why? if x is
odd then there exists k such that 2k+1 = x and therefore,
(2k + 1)(2k + 2)(2k + 3) = 2(k + 1)(number) =
2(number) = even.
40
www.notesolution.com Claim 5 – Formalized.
Claim 5. The product of three consecutive natural numbers is an
even number.
Q. In logic?
∀x ∈ N,∃k ∈ N,x(x + 1)(x + 2)

More
Less
Related notes for CSCA67H3