/Users/billy/gits/moc-2021/problem-sets/ps07.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 7
6–10 September 2021
Content: sets, relations, properties of relations, functions
P7.1 Compute the transitive closure and symmetric-transitive closure of the following relations on
Z. For each closure, determine if it is reflexive.
(i) {(2, 3), (5, 4), (0, 3), (2, 1), (1, 5)}
(ii)
{
(x, y) ∈ Z× Z | |x− y| ≤ 2
}
P7.2 Recall that the symmetric difference of sets A and B is the set A⊕B = (A\B)∪ (B \A). For
each of the following set equations, give an equivalent equation that does not use ⊕. However,
do not simply replace ⊕ by its definition; instead try to find the simplest equivalent equation.
(a) A⊕B = A
(b) A⊕B = A \B
(c) A⊕B = A ∪B
(d) A⊕B = A ∩B
(e) A⊕B = Ac
(f) A⊕B = ∅
P7.3 There are multiple ways of representing a relation R from A to B.
• A subset R ⊆ A×B (this is how we define it)
• A function χR : A×B → {0, 1}
• A function αR : A → P(B)
• A function βR : B → P(A)
Explain how we determine whether a ∈ A and b ∈ B are related under each representation
of R. Then show that we can convert between these representations, starting with a subset
R ⊆ A×B, and converting to and from each of the other three representations.
P7.4 Relations are sets. To say that R(x, y) ∧ S(x, y) holds is the same as saying that (x, y) is in
the relation R and also in the relation S, that is, (x, y) ∈ R ∩ S.
Suppose R and S are reflexive relations on a set A. Then ∆A ⊆ R and ∆A ⊆ S, so ∆A ⊆ R∩S.
That is, R ∩ S is also reflexive. We say that intersection preserves reflexivity. It is easy to
see that union also preserves reflexivity. Similarly, if R is reflexive then so is R−1, but the
complement A2 \R is clearly not. The following table lists these results. Complete the table,
indicating which operations on relations preserve symmetry and transitivity.
Property Reflexivity Symmetry Transitivity
preserved under ∩? yes
preserved under ∪? yes
preserved under inverse? yes
preserved under complement? no
P7.5 Continuing from the previous question, now assume that R and S are equivalence relations.
From your table’s first two rows, determine whether R∩S necessarily is an equivalence relation,
and whether R ∪ S is.
P7.6 The Cartesian product of two sets A and B is defined A×B = {(a, b) | a ∈ A∧ b ∈ B}. That
is, a pair whose first component comes from A and whose second component comes from B is
an element of A×B (and no other pairs are). Recall that ∩ and ∪ are absorptive, commutative
and associative. Does × have any of those properties?
P7.7 Suppose A is a set of cardinality 42, that is, A has 42 elements. What, if anything, can we
say about B’s cardinality if we know that some function f : A → B is injective? What, if
anything, can we say about B’s cardinality if we know that some function f : A → B is
surjective?
P7.8 Consider this conjecture: If a binary relation R on some set A is both symmetric and anti-
symmetric then R is reflexive. Prove or disprove the conjecture.
P7.9 Consider this statement: For all sets S and T , S × T = T × S iff S = T .
If the statement is true, prove it. Otherwise provide a counter-example.
P7.10 Consider this conjecture: If a binary relation R on some set A is reflexive then R is either
symmetric or anti-symmetric, or both. Prove or disprove the conjecture.
P7.11 Let R be a relation on A. Show that R ∪∆A is the reflexive closure of R.
P7.12 Let R be a transitive binary relation on A. Does it follow from the transitivity of R that its
symmetric reflexive closure R ∪R−1 ∪∆A is also transitive?
P7.13 Consider the relations on the natural numbers listed in the following table, and tick off their
properties. The successor relation is the relation given by {(n,m) | n+1 = m}. The coprime
relation C on N is given by C(n,m) iff GCD(n,m) = 1, that is, the only common factor of n
and m is 1.
< ≤ successor divides coprime irreflexive reflexive asymmetric antisymmetric symmetric transitive linear P7.14 (Optional.) Let ≤ be a partial order on a set X. We say that a function h : X → X is: • idempotent iff ∀x ∈ X (h(h(x)) = h(x)) • monotone iff ∀x, y ∈ X (x ≤ y ⇒ h(x) ≤ h(y)) • increasing iff ∀x ∈ X (x ≤ h(x)) Note that an idempotent function does all of its work “in one go”; repeated application will not change its result. A monotone function is one that respects order; if its input grows, its output must grow too (or stay the same). A function which is idempotent and monotone is a closure operator. If it is also increasing, we call it an upper closure operator. Closure operators are important and appear in many different contexts. We have met several—let R be the set of all binary relations. Then the functions refl , symm, and trans, in R → R, producing a relation’s reflexive, symmetric, and transitive closure, respectively, are all upper closure operators. Soon we will meet an “ǫ- closure” function that is part of the algorithm for turning a non-deterministic automaton into an equivalent deterministic automaton—yet another upper closure operator. Consider D = {a, b, c, d} and the partial order ≤ on D, defined by x ≤ y iff x = a ∨ x = y ∨ y = d Below is the so-called Hasse diagram for D. A Hasse diagram provides a helpful way of depicting a partially ordered set. The nodes are the elements of the set, and the order is given by the edges: x ≤ y if and only if there is a path from x to y travelling upwards only, along edges (and the path can have length 0). a b c d Define eight functions f1, . . . , f8 : D → D, exhibiting all possible combinations of the three properties. That is, find some (a) f1 which is idempotent, monotone, and increasing; (b) f2 which is idempotent and monotone, but not increasing; (c) f3 which is idempotent and increasing, but not monotone; (d) f4 which is monotone and increasing, but not idempotent; (e) f5 which is idempotent, but neither monotone nor increasing; (f) f6 which is monotone, but neither idempotent nor increasing; (g) f7 which is increasing, but neither idempotent nor monotone; (h) f8 which is neither idempotent, monotone, nor increasing.