Proofs Class Problems
Proofs Class Problems
1. Assume that A⊆B. Show that if x∉B, then x∉A.
1. Assume that A⊆B. Show that if x∉B, then x∉A.
Proof by contrapositive that is, we want to prove x∈A implies x∈B
Proof by contrapositive that is, we want to prove x∈A implies x∈B
1
.x∈A (Contrapositive assumption)
2
.A⊆B (Problem Assumption)
3
.x∈Ax∈B (definition of set containment)
4
.x∈B (Inference from 3 and 1)
2. Show by induction that 1 + 3 + ... + (2n +1) = 2(n+1) for all n∈.
2. Show by induction that 1 + 3 + ... + (2n +1) = for all n∈.
2
(n+1)
We will proceed by induction on n:
We will proceed by induction on n:
Let P(x) = 1 + 3 + ... + (2x +1) =
2
(x+1)
1
.0 = 0
2
.0+1 = 0+1
3
.2*0 +1 =
2
(0+1)
4
.P(0)
At this point we need to prove P(k)->P(k+1). We do this by direct proof method.
5
.P(k)
6
.1 + 3 + ... + (2k +1) = .
2
(k+1)
7
.1 + 3 + ... + (2k +1) + (2(k+1) +1) = + (2(k+1) +1)
2
(k+1)
8
.1 + ...+ (2(k+1) +1) = +(2k+2+1)
(+2k+1)
2
k
9
.1 + ...+ (2(k+1) +1) = +4k+4
2
k
10
.1 + ...+ (2(k+1) +1) =
2
(k+2)
11
.1 + ...+ (2(k+1) +1) = ((k+1)
2
+1)
12
.P(k+1)
13
.P(k)P(k+1)
14
.∀nP(n) (by Induction)
15
.1 + 3 + ... + (2n +1) = for all n∈
2
(n+1)
3. Let a∈. Consider the following statement: ∀e∃d ∀x(|x-a|<d |f(x)-f(a)|<e) What would be the approach to start proving the statement?
3. Let a∈. Consider the following statement: ∀e∃d ∀x(|x-a|<d |f(x)-f(a)|<e) What would be the approach to start proving the statement?
We would have to start by using an arbitrary number e.
1
.Let e∈.
We then proceed by constructing a number d (potentially)depending on e
2
.Let d = function(e).
we then take an arbitrary number x
3
.let x∈
4. Prove the following using propositional logic axioms:
4. Prove the following using propositional logic axioms:
1
.p(qp)
1
.1
.p→(¬q∨p)
1
.2
.p(qp)
2
.pp
2
.1
.p→(¬(pp)∨p)
2
.2
.p→((pp)p)
2
.3
.{p →((p → p) → p)} → {(p → (p → p))→ (p →p)}
2
.4
.(p → (p → p))→ (p →p)
2
.5
.p→(¬p∨p)
2
.6
.p → (p → p)
2
.7
.p →p
5. Symbolize the following using First order Logic.
5. Symbolize the following using First order Logic.
1
.No dog has gone to heaven.
Let H(x) = “x has gone to heaven”
¬ ∃ xH (x)
¬ ∃ xH (x)
2
.Not all integers are odd.
Let O (x) = “x is odd”
¬ ∀ x O (x)
¬ ∀ x O (x)
3
.There are no numbers greater than 7.
¬ ∃ x x > 7
6. Negate the following statements. Arrive at a statement in which all quantifiers are at the start of it.
6. Negate the following statements. Arrive at a statement in which all quantifiers are at the start of it.
1
.∀x∃y x<y
1
.1
.¬∀x∃y x<y
1
.2
.∃x¬∃y x<y
1
.3
.∃x∀y¬( x<y)
2
.∃x∀y y≤x
2
.1
.∀x∃y¬( y≤x)
3
.∀x ∃y∀z (z > x z ≥ y)
3
.1
.∃x ∀y∃z ¬ (z > x z ≥ y)
7. Prove the following statements:
7. Prove the following statements:
1
.A ⊆ A⋃B
Proving the statement above is equivalent to proving that ∀x ( x∈A x∈A⋃B).
We proceed by direct proof
We proceed by direct proof
1
.1
.Let x∈A.
1
.2
.then x∈A or x∈B
1
.3
.x∈A⋃B
Since x was arbitrary, this shows ∀x ( x∈A x∈A⋃B) which means that A ⊆ A⋃B.
2
.A⋂B ⊆ A
We note that by definition the above is equivalent to proving ∀x ( x∈A⋂B x∈A)
We prove the statement by direct proof
We prove the statement by direct proof
2
.1
.Let x∈A⋂B
2
.2
.x∈A and x∈B
2
.3
.x∈A
Since x was arbitrary we have ∀x ( x∈A⋂B x∈A) which means that A⋂B ⊆ A.