/Users/billy/gits/moc-2021/tutes/week07.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Tutorial Week 7
6–10 September 2021
Content: sets, relations, properties of relations, functions
The exercises
T7.1 Let A = {1, 2}, B = {2, 3, 4} be sets, R1 = {(1, 4), (2, 3)} a relation from A to B and
R2 = {(3, 1), (2, 2)} a relation from B to A. Evaluate the following sets in list form.
(i) (A ∪B) \ (A ∩B)
(ii) A× P(B)
(iii) R1 ◦R2
(iv) (R1 ◦R2) ∩ P(A)
T7.2 Let A, B be any sets. Show the following, using the logical definitions of the relevant concepts.
(i) A 6⊆ B ⇔A \B 6= ∅. (ii) A ∩B = A \ (A \B).
T7.3 We can represent a relation R ⊆ A × A as a directed graph, where the vertices are elements
of A and there is a directed edge from x to y, iff (x, y) ∈ R. Below is a graph representing a
relation R on the set {1, 2, . . . , 8}.
1
2
3
4
5
67
8
Draw the graph representing the transitive closure of R. Is it reflexive? Is the symmetric-
transitive closure of R reflexive?
T7.4 Show that a relation R on A is transitive iff R ◦R ⊆ R. Then give an example of a transitive
relation R for which R ◦R = R fails to hold.
T7.5 Suppose we know about functions f : A → B and g : B → A that f(g(y)) = y for all y ∈ B.
What, if anything, can be deduced about f and/or g being injective and/or surjective?
T7.6 Suppose h : X → X satisfies h ◦ h ◦ h = 1X . Show that h is a bijection. Also give a simple
example of a set X and a function h : X → X such that h ◦ h ◦ h = 1X , but h is not the
identity function (hint: think paper-scissors-rock).
After you finish: work on questions from Problem Set 7