## 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