/Users/billy/gits/moc-2021/problem-sets/solps07.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Problem Set Solutions, Week 7
P7.1 (i) The transitive closure of {(2, 3), (5, 4), (0, 3), (2, 1), (1, 5)} is
{(2, 3), (5, 4), (0, 3), (2, 1), (1, 5), (2, 5), (2, 4), (1, 4)}
The symmetric transitive closure is {0, 1, 2, 3, 4, 5} × {0, 1, 2, 3, 4, 5}. Neither of these
are reflexive. The first doesn’t have any (x, x) pairs, so it’s actually irreflexive, and the
second doesn’t have, for example, (6, 6). Remember that this is a relation on the set Z,
so although it relates 0, 1, 2, 3, 4 and 5 to themselves, it doesn’t do this for the rest of
the integers, so it’s not reflexive.
(ii) The transitive closure and also symmetric transitive closure of
{
(x, y) ∈ Z× Z | |x− y| ≤ 2
}
is the full relation, Z× Z, which is reflexive.
P7.2 These are simpler expressions:
(a) A⊕B = A is equivalent to B = ∅.
(b) A⊕B = A \B is equivalent to B ⊆ A.
(c) A⊕B = A ∪B is equivalent to A ∩B = ∅.
(d) A⊕B = A ∩B is equivalent to A ∪B = ∅.
(e) A⊕B = Ac is equivalent to B = X, assuming a universal set X.
(f) A⊕B = ∅ is equivalent to A = B.
P7.3 Let R ⊆ A×B be a relation.
• Define χR : A×B → {0, 1} such that
χR(a, b) =
{
1, (a, b) ∈ R
0, (a, b) 6∈ R
We can determine whether a and b are related under this representation of R, by
checking if χR(a, b) = 1. Given any function f : A × B → {0, 1}, we can form the
relation
{(a, b) ∈ A×B | f(a, b) = 1}
This recovers the original relation R from χR, since
{(a, b) ∈ A×B | χR(a, b) = 1} = {(a, b) ∈ A×B | (a, b) ∈ R}
= R
• Define αR : A → P(B) such that
αR(a) = {b ∈ B | (a, b) ∈ R}
We can determine whether a and b are related under this representation of R, by
checking if b ∈ αR(a). Given any function f : A → P(B), we can form the relation
{(a, b) ∈ A×B | b ∈ f(a)}
This recovers the original relation R from αR, since
{(a, b) ∈ A×B | b ∈ αR(a)} = {(a, b) ∈ A×B | b ∈ {x ∈ B | (a, x) ∈ R}}
= {(a, b) ∈ A×B | (a, b) ∈ R}
= R
• Define βR : B → P(A) such that
βR(b) = {a ∈ A | (a, b) ∈ R}
We can determine whether a and b are related under this representation of R, by
checking if a ∈ βR(b). Given any function f : B → P(A), we can form the relation
{(a, b) ∈ A×B | a ∈ f(b)}
This recovers the original relation R from βR, since
{(a, b) ∈ A×B | a ∈ βR(b)} = {(a, b) ∈ A×B | a ∈ {x ∈ A | (x, b) ∈ R}}
= {(a, b) ∈ A×B | (a, b) ∈ R}
= R
P7.4 Here is the complete table:
Property Reflexivity Symmetry Transitivity
preserved under ∩? yes yes yes
preserved under ∪? yes yes no
preserved under inverse? yes yes yes
preserved under complement? no yes no
To see how transitivity fails to be preserved under union, consider two relations on {a, b, c},
namely R = {(a, a), (a, b), (b, b)} and S = {(c, a)}, both transitive. R ∪ S is not tran-
sitive, because in the union we have (c, a) and (a, b), but not (c, b). And R’s complement,
{(a, c), (b, a), (b, c), (c, a), (c, b), (c, c)} is not transitive either, as it contains, for example, (a, c)
and (c, a), but not (a, a).
P7.5 From the first row of the last question’s table, it follows that, if R and S are equivalence
relations, then so is their intersection. But their union may not be. As an example, take the
reflexive, symmetric, transitive closures of R and S from the previous answer, to get these
two equivalence relations:
R′ = {(a, a), (a, b), (b, a), (b, b), (c, c)} and S′ = {(a, a), (a, c), (b, b), (c, a), (c, c)}.
Their union fails to be transitive, as it contains (c, a) and (a, b) but not (c, b).
P7.6 We certainly do not have A × A = A. In fact, no member of A is a member of A × A, and
no member of A×A is a member if A. So × is not absorptive.
2
Neither is it commutative. Let A = {0} and B = {1}. Then A × B = {(0, 1)} while
B ×A = {(1, 0)}, and those singleton sets are different, because the members are.
If we also define C = {2} then A× (B ×C) = {(0, (1, 2))} while (A×B)×C = {((0, 1), 2)}.
Again, these are different. However, it is not uncommon to identify both of (0, (1, 2)) and
((0, 1), 2) with the triple (0, 1, 2) (“flattening” the nested pairings). If we agree to do that
then × is associative, and we can simply write A×B × C for the set of triples.
P7.7 If f is injective then B has at least 42 elements. If f is surjective then B has at most 42
elements. (So if f is bijective, B has exactly 42 elements.)
P7.8 The conjecture is false. For a counter-example, take A to be {0, 1} and R = {(0, 0)}. Then
R is symmetric, and also anti-symmetric, but R is not reflexive, as it does not include (1, 1).
P7.9 The statement is false, as we have, for example, {42} × ∅ = ∅ × {42} = ∅, but ∅ 6= {42}.
P7.10 The conjecture is false. Take A to be {a, b, c} and R = {(a, a), (a, b), (b, a), (b, b), (c, a), (c, c)}
The R is reflexive, but not symmetric, since (c, a) ∈ R but (a, c) 6∈ R. And R is not anti-
symmetric either, as we have (a, b) ∈ R as well as (b, a) ∈ R.
P7.11 The reflexive closure of R is the smallest reflexive relation K such that R ⊆ K. We know
that R ∪ ∆A is reflexive, since for any a ∈ A, (a, a) ∈ ∆A, so (a, a) ∈ R ∪ ∆A. We also
know that R ⊆ R ∪ ∆A, so we just need to know that it’s the smallest relation with these
properties. So suppose K is reflexive and R ⊆ K. Then since K is reflexive, we must have
∆A ⊆ K. So both R and ∆A are subsets of K, so their union is, i.e. R ∪∆A ⊆ K (you can
verify this by expanding the definition of union and subset). Hence R ∪ ∆A is in fact the
smallest such reflexive relation containing R.
P7.12 No, for example, take the transitive closure of R from T7.3. This is a transitive binary
relation on {1, 2, 3, 4, 5, 6, 7, 8}, and if you take the symmetric reflexive closure of it, you will
have (2, 1) and (1, 5) in the closure but not (2, 5), so it is not transitive.
P7.13 Here is the table, with appropriate check-marks:
< ≤ successor divides coprime irreflexive ✓ ✓ reflexive ✓ ✓ asymmetric ✓ ✓ antisymmetric ✓ ✓ ✓ ✓ symmetric ✓ transitive ✓ ✓ ✓ linear ✓ ✓ P7.14 Here are some functions that satisfy the requirements. We show fi(x) in the table’s row x, column i: f1 f2 f3 f4 f5 f6 f7 f8 a a a b b b a c b b b a b d b a b a c c a c d c a d d d d a d d c c d c Maybe you skipped this optional exercise; but you may still want to verify, for each of these eight functions, that it really does satisfy its specification. 3