Solutions to the exercises on

Sets, Relations, and Functions

April, 2007

Exercises on slide 11
Exercise 1
Argue that A and Ā are disjoint.

Solution
By definition of the complement, Ā is the set of those element from the universal set U, which
are not in A, so if x ∈ A then x ∈
/ Ā and if x ∈ Ā then x ∈
/ A, thus there is no such x that x ∈ A
and x ∈ Ā, therefore A ∩ Ā = ∅.

Exercise 2
Let U = N. What is the complement of {x : x2 − 3x − 4 = 0}? What if U = Q?

Solution
A = {x : x2 − 3x − 4 = 0} = {x : (x − 4)(x + 1) = 0}, then Ā = {x : x2 − 3x − 4 6= 0}.
Thus for U = N, A = {4} and Ā = {0, 1, 2, 3, 5, 6, 7, ...}. And for U = Q, A = {−1, 4} and
Ā = Q \ {−1, 4}.

Exercise on slide 12
Exercise 1
What’s the power set of {a, b, c}?

Solution
P({a, b, c}) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

Exercise 2
Give an intuitive explanation of P(N).

1
Solution
P(N) is a set of all subset of N including the empty set ∅ and N itself.
P(N) = {∅, {0}, {1}, {2}, ..., {0, 1}, {0, 2}, ...{0, 1, 2}, ...{0, 1, 2, ..., n, ...}, ..., N}.

Exercises on slide 14
Exercise 1
Give a partition of the real numbers R.

Solution
An example of a partion of R can be {A, B, C}, where A = {x : x > 0}, B = {0} and
C = {x : x < 0}. It is because A, B and C are not empty sets, they are pairwise disjoint and
their union is equal to R.

Exercise 2
Does there exist a partition of ∅?

Solution
The partition of ∅ is ∅.

The empty set can be written {Ai : i ∈ I} where I = ∅. Recall the definition of a partition:
(a) Ai 6= ∅, for all i ∈ I
(b) i∈I Ai = ∅
S

(c) Ai ∩ Aj = ∅, i 6= j, for all i, j ∈ I

(a) is trivially satisfied since I = ∅ from above. Also, (b) is vacously satisfied since the union of
all sets indexed over by an empty set is empty. Finally, again since i and j range over an empty
set there are no sets Ai and Aj so (c) holds trivially.

Exercise on slide 15
Give an example where (a, b) ∈ A but (b, a) ∈
/ A.

Solution
Let A = {(x, y) : x is a father of y}. Then if Adam is a father of Bob, (Adam, Bob) ∈ A but
(Bob, Adam) ∈/ A, because Bob is a son of Adam, and so he cannot be his father.

Exercise on slide 21
Compute (R3 ◦ R2 ) ◦ R1 .

2
Solution
By the theorem on the lecture slide 21 R3 ◦ (R2 ◦ R1 ) = (R3 ◦ R2 ) ◦ R1 .
Thus (R3 ◦ R2 ) ◦ R1 = {(Adam, 30), (Bob, 63), (Chris, 52), (Dave, 30), (Eve, 63)}

Exercise on slide 22
Why is not < on N an equivalence relation? Why is not ≤?

Solution
< is not an equivalence relation on N, because it is not reflexive. It follows from the fact that
forall a ∈ N it holds that a ≮ a.
≤ is not an equivalence relation on N, because it is not symmetric. A counter example illustrating
that ≤ is not symmetric is 4 ≤ 5 but 5 6≤ 4.

Exercise on slide 27
Why is ⊆ not a total order on P(A) if A contains at least two elements?

Solution
It is because not any two elements in P(A) can be related. For example, if A = {a, b}, then
P(A) = {∅, {a}, {b}, {a, b}}. Here the two sets {a} and {b} cannot be related by ⊆.

Exercise on slide 30
Let f (x) = 2x + 3 and g(x) = 3x + 2 be functions on N. What is (g ◦ f )(x)?

Solution
(g ◦ f )(x) = 3(f (x)) + 2 = 3(2x + 3) + 2 = 6x + 11.

Exercises on slide 35
Exercise 2
Argue that for all n ∈ Z+ the relation Rn on Z+ , defined by aRn b if and only if a%n = b%n, is
an equivalence relation.

Solution
In order to be an equivalence relation Rn must be reflexive(i), symmetric(ii) and transitive(iii).
(i) ∀a ∈ Z+ : a%n = a%n. Therefore Rn is reflexive.
(ii) ∀a, b ∈ Z+ : a%n = b%n implies that b%n = a%n. Therefore Rn is symmetric.
(iii) ∀a, b, c ∈ Z+ : a%n = b%n and b%n = c%n implies that a%n = c%n. Therefore Rn is
transitive.

3
Exercise 3
Argue why an equivalence relation that is also a function must be the identity. The identity
I : A → A is defined by I(a) = a for all a ∈ A.

Solution
Let R be an equivalence relation on A and a function R : A → A. Then by the definition of a
function, for every a ∈ A, there is one and only one b ∈ A so that (a, b) ∈ R, which means that
aRb. As it follows from the fact that an equivalence relation is reflexive, for every a ∈ A aRa.
Hence for every a ∈ A, there is one and only one b ∈ A so that (a, b) ∈ R, and such b = a.
Thus R is the identity.

Exercise 3.2.3 on page 80 in DM for NT

Let U = {x : x is an integer and 2 ≤ x ≤ 10}. In each of the following cases, determine
whether A ⊆ B, B ⊆ A, both or neither:
(i) A = {x : x is odd } B = {x : x is a multiple of 3}
(ii) A = {x : x is even} B = {x : x2 is even}
(iii) A = {x : x is even } B = {x : x is a power of 2}
(iv) A = {x :√ 2x + 1 > 7} B = {x : x2 > 20}
(v) A = {x : √x ∈ Z} B = {x : x is a power of 2 or 3}
(vi) A = {x : x ≤ 2} B = {x : x is a perfect square}
(vii) A = {x : x2 − 3x + 2 = 0} B = {x : x + 7 is a perfect square}.

Solution
U = {2, 3, 4, 5, 6, 7, 8, 9, 10}
(i) neither, A = {3, 5, 7, 9} B = {3, 6, 9}
(ii) both, A = {2, 4, 6, 8, 10} B = {2, 4, 6, 8, 10}
(iii) B ⊆ A, A = {2, 4, 6, 8, 10} B = {2, 4, 8}
(iv) B ⊆ A, A = {4, 5, 6, 7, 8, 9, 10} B = {5, 6, 7, 8, 9, 10}
(v) A ⊆ B, A = {4, 9} B = {2, 3, 4, 8, 9}
(vi) neither, A = {2, 3, 4} B = {4, 9}
(vii) both, A = {2} B = {2}.

Exercise 3.2.8 on page 81 in DM for NT

(i) Prove that, if A ⊆ B and B ⊆ C, then A ⊆ C.
(ii) Deduce that, if A ⊆ B, B ⊆ C and C ⊆ A, then A = B = C.

Solution
(i) Let x ∈ A, then it follows from A ⊆ B that x ∈ B, then it follows from B ⊆ C that x ∈ C.
This proves that every element of A also belongs to C, so A ⊆ C.
(ii) A ⊆ B, B ⊆ C, so it follows from (i) that A ⊆ C. If A ⊆ C and C ⊆ A then by the

4
theorem on the lecture slide 8 A = C. From A = C, A ⊆ B and B ⊆ C follows that C ⊆ B
and B ⊆ C, and thus by the same theorem B = C. Therefore A = B = C.

Exercise 3.2.10 on page 81 in DM for NT

Consider the set R of all sets which are not elements of themselves. That is, R = {A : A is a set
and A ∈/ A}.
Find a set which is an element of R. Can you find a set which is not an element of R?
Explain why R is not a well defined set. (Hint: is R itself an element of R?)

Solution
Let B is a set and B ∈ R, then by definition of R B ∈ / B. An example of such set B can be
B = {1} and many others, because usually B ∈ / B, like {1} ∈
/ {1}.
Let us now find a set C which is not an element of R, so C ∈ C must hold. An example of such
set can be C = {{...{{1}}...}}, because {{...{{1}}...}} ∈ {{{...{{1}}...}}}.
R is not well defined, because assuming that R ∈ R, it follows from the definition of R that
R ∈ / R, and assuming that R ∈ / R, it follows that R ∈ R. Such definition of R leads to a
contradiction.

Exercise 3.5.4 on page 106 in DM for NT

Which of the following are partitions of R, the set of real numbers? Explain your answers.
(i) {In : n ∈ Z}, where In = {x ∈ R : n ≤ x ≤ n + 1}.
(ii) {Jn : n ∈ Z}, where Jn = {x ∈ R : n ≤ x < n + 1}.
(iii) {Kn : n ∈ Z}, where Kn = {x ∈ R : n < x < n + 1}.

Solution
(i) {In : n ∈ Z} is not a partition of R, because In ∩ In+1 6= ∅, and it follows from the fact that
∃x = n + 1 : x ∈ In and x ∈ In+1 .

(ii) {Jn : n ∈ Z} is a partition of R, because ∀n ∈ Z Jn 6= ∅, Jn = R and Ji ∩ Jj = ∅ if

S
n∈Z
i 6= j for all i, j ∈ Z

(iii) {Kn : n ∈ Z} is not a partition of R, because Kn 6= R, and it follows from the fact
S
n∈Z
that ∀i ∈ Z : i ∈ R and i ∈
/ Kn ∀n ∈ Z.

Exercise 5 on page 140 in DM with Combinatorics

Which of the following functions, whose domain and codomain are the real line, are one-to-one,
which are onto, and which have inverses:
(a) f (x) = |x|
(b) f (x) = x2 + 4
(c) f (x) = x3 + 6

5
(d) f (x) = x + |x|
(e) f (x) = x(x − 2)(x + 2)

Solution
(a) f (x) = |x|.
This function is not one-to-one, because ∃x1 and ∃x2 : f (x1 ) = f (x2 ) and x1 6= x2 , for example
x1 = 3 and x2 = −3.
This function is not onto, because there exists such y, that for every x : f (x) 6= y, for example,
y < 0, where f (x) ≥ 0 for every x.
This function can have inverse f −1 (y) only on y ∈ [0, +∞), because f (x) ≥ 0 for all x ∈
(−∞, +∞), moreover f −1 (y) = ±y, that is not a function.

(b) f (x) = x2 + 4
This function is not one-to-one, because ∃x1 and ∃x2 : f (x1 ) = f (x2 ) and x1 6= x2 , for example
x1 = 3 and x2 = −3.
This function is not onto, because there exists such y, that for every x : f (x) 6= y, for example,
y < 4, where f (x) ≥ 4 for every x.
This function can have inverse f −1√ (y) only on y ∈ [4, +∞), because f (x) ≥ 4 for all x ∈
−1
(−∞, +∞), moreover f (y) = ± y − 4, that is not a function.

(c) f (x) = x3 + 6
This function is one-to-one, because ∀x1 and ∀x2 : f (x1 ) = f (x2 ) implies that x1 = x2 , as it
follows from x31 + 6 = x32 + 6 that x1 = x2 .
This function is onto, because for every y, there exists x : f (x) = y. √
This function have inverse f −1 (y) on y ∈ (−∞, +∞), and f −1 (y) = 3 y − 6, that is a function.

(d) f (x) = x + |x|

This function is not one-to-one, because ∃x1 and ∃x2 : f (x1 ) = f (x2 ) and x1 6= x2 , for example
x1 = −3 and x2 = −4.
This function is not onto, because there exists such y, that for every x : f (x) 6= y, for example,
y < 0, where f (x) ≥ 0 for every x.
This function can have inverse f −1 (y) only on y ∈ [0, +∞), because f (x) ≥ 0 for all x ∈
(−∞, +∞), moreover for y > 0 the inverse is defined as f −1 (y) = y2 , and for y = 0 f −1 (y) = a,
where a can be any real number that ≤ 0, so such inverse is not a function.

(e) f (x) = x(x − 2)(x + 2)

This function is not one-to-one, because ∃x1 and ∃x2 : f (x1 ) = f (x2 ) and x1 6= x2 , for example
x1 = 0 and x2 = 2.
This function is onto, because for every y, there exists x : f (x) = y.
This function have inverse f −1 (y) on y ∈ (−∞, +∞), and f −1 (0) = 0, 2 or −2, that is not a
function.

6
Exercise 5 on page 160 in DM with Combinatorics
Show that the set A = {−10, −9, −8, −7, −6, −5, −4, −3, −2, −1, 0, 1, 2, 3, ...} is countably
infinite.

Solution
This set A is countably infinite, because there exists a bijection f : A → Z+ , where f (a) =
a + 11 for a ∈ A.