51.
Negatefirst
(a)
(b)
The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Selected Tutorial Solutions, Week 7
We can negate both sides of the biimplication, so we just need to show:
52.
53. 54.
55.
These are simpler expressions: A 113
(a) A⊕B=AisequivalenttoB=∅.
(b) A⊕B=A\BisequivalenttoB⊆A. BlA0a
(c) A⊕B=A∪BisequivalenttoA∩B=∅. A B
(d) A⊕B=A∩BisequivalenttoA∪B=∅. A0130
AIB U BIA VxXEA xeB
A⊆B⇔A\B=∅
AB
The left-hand side is, by definition: ∀x(x ∈ A ⇒ x ∈ B). The right-hand side can be written: ¬∃y(y ∈ A∧y ̸∈ B). Pushing the negation in, we get ∀y(y ̸∈ A∨y ∈ B), or equivalently, ∀y(y ∈ A ⇒ y ∈ B).
It is easier to look at the logical expressions. The left-hand side is {x | x ∈ A ∧ x ∈ B}.
The right-hand side is
{x | x ∈ A ∧f
= {x|x∈A∧
= {x|x∈A∧(x̸∈A∨x∈B)}
= {x|x∈A∧x∈B} Kofi
(e) A ⊕ B = Ac is equivalent to B = X, assuming a universal set X.
The statement is false, as we have, for example, {42} × ∅ = ∅ × {42} = ∅, but ∅ ≠ {42}.
Assume that R is transitive. Let (x, z) be in R ◦ R. That means there is some y, such that R(x, y) and R(y, z) hold. By transitivity, R(x, z) holds, so (R ◦ R) ⊆ R.
Conversely, assume (R ◦ R) ⊆ R. Consider x, y, z such that R(x, y) and R(y, z) hold. Clearly (x, z) is in R ◦ R, and hence, by assumption, in R. But that means R is transitive.
As an example of a transitive relation for which R ◦ R = R does not hold, consider < on Z. It is transitive, but < ◦ < does not contain, say (2,3). Since (2,3) is in <, < is different from < ◦ <.
Here is the complete table:
Property
preserved under ∩?
preserved under ∪?
preserved under inverse? preserved under complement?
Reflexivity Symmetry Transitivity yes yes yes
yes yes no
yes yes yes
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).
Negation AnB
x ̸∈ A \ B}
1
¬(x ∈ A ∧ x ̸∈ B)} NBA
AB
All
56. 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).
Neg1ation
57. From f(g(y)) = y we conclude that g is injective. Namely, if B has cardinality 1 then g is
′′
trivially injective. Otherwise, consider y, y′ ∈ B, with y ̸= y . Suppose g(y) = g(y ). Then,
applying f to both, we have y = f(g(y)) = f(g(y′)) = y′, contradicting y ̸= y′. So we must have g(y) ̸= g(y′), that is, g is injective.
Similarly we can show that f is surjective. To do this, we must show that for each y ∈ B thereissomex∈Asuchthatf(x)=y. Butthatiseasy—thatxisg(y)∈A.
58. We have: h(h(h(x))) = x for all x ∈ X. First, let us show that h must be injective. If h(x) = h(y), then, applying h twice on each side, we have h(h(h(x))) = h(h(h(y))), whence
mum
For the counter-example, take X = {a,b,c} and let h map a to b, b to c, and c to a. Then h is not the identity function on X, but h ◦ h ◦ h is.
59. 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.
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.
60. 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).
61. 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.)
62. Here are some functions that satisfy the requirements. We show fi(x) in the table’s row x, column i:
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.
x = y. So h is injective. Second, let us show that h must be surjective. Consider an arbitrary element x ∈ X. We have x = h(h(h(x))), that is, h maps h(h(x)) to x. Since x was arbitrary, h is surjective.
f1 f2 f3 f4 f5 f6 f7 f8
a b c d
aabbbacb babdbaba cacdcadd daddccdc
2