Description
1 Exercises
1. (6 marks) Sipser, Ex. 0.3: Let A be the set {x, y, z} and B be the set {x, y}.
(a) (1 mark) Is A a subset of B?
(b) (1 mark) Is B a subset of A?
(c) (1 mark) What is A ∪ B?
(d) (1 mark) What is A ∩ B?
(e) (1 mark) What is A × B?
(f) (1 mark) What is the power set of B?
2. (2 marks) Sipser, Ex. 0.4: If A has a elements and B has b elements, how many elements are in A×B? Explain
your answer.
3. (2 marks) Sipser, Ex. 0.5: If C is a set with c elements, how many elements are in the power set of C? Explain
your answer.
4. (7 marks) Sipser, Ex. 0.6: Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function
f : X 7→ Y and the binary function g : X × Y 7→ Y are described in the following tables.
n f(n)
1 6
2 7
3 6
4 7
5 6
g 6 7 8 9 10
1 10 10 10 10 10
2 7 8 9 10 6
3 7 7 8 8 9
4 9 8 7 6 10
5 6 6 6 6 6
(a) (1 mark) What is the value of f(2)?
(b) (2 marks) What are the domain and co-domain of f?
(c) (1 mark) What is the value of g(2, 10)?
(d) (2 marks) What are the domain and co-domain of g?
(e) (1 mark) What is the value of g(4, f(4))?
5. (3 marks) Sipser, Ex. 0.7: For each part, give a relation that satisfies the condition.
1
(a) (1 mark) Reflexive and symmetric but not transitive.
(b) (1 mark) Reflexive and transitive but not symmetric.
(c) (1 mark) Symmetric and transitive but not reflexive.
2 Problems
1. (2 marks) Sipser, Prob. 0.12 (0.11 in 2nd edition): Find the error in the following proof that all horses are the
same color.
CLAIM: In any set of h horses, all horses are the same color.
PROOF: By induction on h.
Base Case: For h = 1. In any set containing just one horse, all horses clearly are the same color.
Induction Step: For k ≥ 1 assume that the claim is true for h = k and prove that it is true for h = k + 1. Take
any set H of k + 1 horses. We show that all the horses in this set are the same color. Remove one horse from
this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H1 are the same
color.
Now replace the removed horse and remove a different one to obtain the set H2. By the same argument, all
the horses in H2 are the same color. Therefore all horses in H must be the same color, and the proof is complete.
2. (4 marks) Prove using induction that
Xn
m=0
m =
n(n + 1)
2
.
2