School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 7
16–18 September 2020
The exercises
51. Let A, B, and C be sets. Show: (a) A̸⊆B⇔A\B̸=∅.
(b) A∩B=A\(A\B).
Hint: Use the formal (logical) definitions of the concepts involved.
52. 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
53. 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.
54. 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.
55. 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.
SupposeRandSarereflexiverelationsonasetA. Then∆A ⊆Rand∆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.
56. 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.
57. Supposeweknowaboutfunctionsf:A→Bandg:B→Athatf(g(y))=yforally∈B. What, if anything, can be deduced about f and/or g being injective and/or surjective?
58. 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).
Property
Reflexivity Symmetry Transitivity
preserved under ∩?
preserved under ∪?
preserved under inverse? preserved under complement?
yes yes yes no
59. (Drill.) 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?
60. (Drill.) 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.
61. (Drill.) 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?
62. (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).
b
a
d
c
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.