COMPSCI 225 Tutorial 6

Note on relations: Given a set A and a relation R(⊆ A2 ) then the following notations all mean that x ∈ A
is in relation with y ∈ A and can all be found in literature: (x, y) ∈ R, xRy, x ∼ y

1. Define the relation R on the integers as follows: given any x, y ∈ Z, we say that xRy holds if and
only if x ≡ 1 mod y. Prove whether R is an equivalence relation or not.

To show R is an equivalence relation, we need to show it’s reflexive, symmetric and

transitive. If any one of the three properties doesn’t hold then it’s not an equivalence
relation. We can quickly verify that R is not reflexive as for example 5 ∈ Z, but we don’t
have 5R5 as 5 ≡ 1 mod 5 does not hold.

2. Prove that the relation ≡ mod 7 on the set Z is symmetric.

Suppose we have two integers x and y and x ≡ y mod 7. It means that x − y = 7k

for some integer k. Therefore, y − x = −7k which is also a multiple of 7 and so
y ≡ x mod 7.

3. Define a relation R on the integers Z as follows: for any a, b ∈ Z, we say that aRb if and only if there
is some c ≥ 2 ∈ Z such that a ≡ b mod c. For example, 2R8 because we can find an integer c such
that 2 ≡ 8 mod c; namely, we have c = 6. Prove whether R an equivalence relation or not.

This is not an equivalence relation as it is not transitive. We have got 2 ∼ 8 (as 2 ≡

8 mod 3) and we have 8 ∼ 3 (as 8 ≡ 3 mod 5). However there is no c ≥ 2 such that we
get 2 ≡ 3 mod c which means 2 ̸∼ 3.

4. Given the set A = (Z\{0})2 and the relation R = {((a, b), (c, d)) | ad − bc = 0)}. This means
(a, b) ∼ (c, d) iff ad − bc = 0. Show that R is an equivalence relation and for (3, 5) ∈ A state the
equivalence class [(3, 5)].

We need to show the three properties reflexivity, symmetry or transitivity hold true for
R:
Reflexivity:
For any element in A, i.e. any (x, y) ∈ A we get: (x, y) ∼ (x, y) as xy − yx = 0.
Symmetry:
We assume (x, y) ∼ (u, v), this means ((x, y), (u, v)) ∈ R and therefore we have xv −
yu = 0. Rearranging this equation gives us xv = yu and rearranging this some more
gives us uy − vx = 0 which means ((u, v), (x, y)) ∈ R.
Transitivity:
Let (x, y) ∼ (u, v) and (u, v) ∼ (s, t) be given. This means we have

xv − yu = 0 ⇔ xv = yu
ut − vs = 0 ⇔ ut = vs

We need to show that (x, y) ∼ (s, t), i.e. that xt − ys = 0 holds. Taking the first
equation and multiplying by t gives us xvt = yut and plugging in the second equation
into this gives us xvt = y(ut) = y(vs). Now dividing this equation by v (v ̸= 0) gives
us xt = ys which is equivalent to what we needed to show and therefore (x, y) ∼ (s, t).

We need to determine [(3, 5)]. This means we need to find all (x, y) such that (3, 5) ∼
(x, y) which holds iff 3y − 5x = 0 which is equivalent to 3y = 5x and as y ̸= 0 we have
3 x
5 = y . This gives us [(3, 5)] = {(3k, 5k) | k ∈ Z, k ̸= 0}.

1
5. Given the set A = {a, b, c, d, e, f }. Give a relation R ⊆ A2 such that R is an equivalence relation and
[a] ̸= [b], [b] = [c], [c] ̸= [f ] and [d] = [e] = [f ]. For this relation R give an example of x, y, z ∈ A
such that {[x], [y], [z]} constitutes a partition of A.

The idea here is to that R splits A into three different equivalence classes [a] = {a},
[b] = [c] = {b, c} and [d] = [e] = [f ] = {d, e, f }. Such a relation would be R =
{(a, a), (b, b), (c, c), (d, d), (e, e), (f, f ), (b, c), (c, b), (d, e), (e, d), (e, f ), (f, e), (d, f ), (f, d)}.
Drawing the directed graph (V, E) with V = A and E = R makes this a lot easier
to comprehend. Now we can choose for x, y and z any of the representatives of the
respective equivalence classes, i.e. x = a, y = b or y = c and z = d or z = e or z = f .

6. Given the set A = {a, b, c}. Give an example of a relation R ⊆ A2 for each of the four cases:
symmetric (but not antisymmetric), antisymmetric (but not symmetric), both and neither. Can a
relation be an equivalence relation and a partial ordering at the same time?

Again, drawing the directed graph (V, E) with V = A and E = R makes this a lot easier
to comprehend these concepts. We don’t care about reflexivity or transitivity here. We
have four scenarios:
Symmetric / antisymmetric:
For example R = {} would do. We could also add self-loops, i.e. we could on top
achieve reflexivity.
Symmetric / not antisymmetric:
An example is R = {(a, b), (b, a)}. Again adding self-loops would not change anything
and note that by adding additional tuples we could again loose symmetry, however we
would never be able to restore anti-symmetry (once it is lost).
Not symmetric / antisymmetric:
The relation R = {(a, b)} is not symmetric as we would also need (b, a) ∈ R for it to
be symmetric, however it is antisymmetric. Again adding self-loops would not change
anything as well as adding (a, c), (b, c), etc as long as we don’t add the ”inverse” tuple
of any of the ones in R.
Not symmetric / not antisymmetric:
To make R not antisymmetric we need a tuple and its ”inverse”, i.e. {(a, b), (b, a)} is
antisymmetric, however symmetric, which we don’t want. Once antisymmetry is lost we
cannot restore it so we need to add tuples to loose symmetry which we achieve by adding
a tuple, but not its ”inverse”. Such an example would be R = {(a, b), (b, a), (a, c)}
which is not symmetric and not antisymmetric.

7. Take any set X, and let Y = P(X), the power set of X. Prove that Y is a poset under the “subset”
relation ⊆, in which we say that A ⊆ B holds if and only if A is a subset of B.

Recall that by definition A ⊆ B holds if and only if every element of A is also an element
of B. Using this definition, we simply check the three properties that characterise a poset
to see that P(X), ⊆ is indeed a poset:

2
 • Reflexivity: Take any A ∈ P(X). We want to show that A ⊆ A. By definition,
this happens if and only if every element a ∈ A is . . . an element of A, which is
trvially true. Success!
• Antisymmetry: Take any two distinct elements A, B ∈ P(X). We want to show
that if A ⊆ B, then B ̸⊆ A. To see why: notice that by definition, if A ⊆ B
then every element of A is an element of B. Therefore, if A ̸= B, the only way
this could have happened is if there is some element of B that’s not in A. But this
means that by defintion B ̸⊆ A, as desired.
• Transitivity: Take any three distinct elements A, B, C ∈ P(X). We want to show
that if A ⊆ B and B ⊆ C, then A ⊆ C. To do this, take any a ∈ A. Because
A ⊆ B, this means that a ∈ B; because B ⊆ C, this means that a ∈ C. Therefore
we’ve shown that for any a ∈ A that a ∈ C; i.e. A ⊆ C, as desired.

8. Let S be the power set of {1, 2, 3} and let R be the relation defined as follows: xRy if and only if
x = y or |x| < |y|.

(a) Establish that R is a partial order.

(b) Draw the Hasse diagram for the poset (S, R).

(a) To show R is an partial order, we need to show it’s reflexive, antisymmetric and
transitive. Let’s do them one by one.
1. R is reflexive since by definition xRy if x = y and so xRx for ∀x ∈ 2S .
2. Suppose xRy and yRx for some x, y. We obviously cannot have |x| < |y|
and |y| < |x| at the same time so it has to be the case that x = y. And so R is
antisymmetric.
3. Suppose xRy and yRz. By definition of R, we have four cases. Case 1)
|x| < |y| and |y| < |z|; Case 2) |x| < |y| and y = z; Case 3) x = y and |y| < |z|;
Case 4) x = y and y = z. In all four cases, we can get to the conclusion that
|x| < |z| or x = z fairly easily and so xRz which means R is transitive.

(b) The Hasse diagram:

{1, 2, 3}

{1, 2} {1, 3} {2, 3}

{1} {2} {3}

3
 9. Draw a Hasse diagram for the “is a factor of” relation | on the set {0, 1, 2, 3, 4}.

We proceed using the method described in class. Our unique maximal/greatest element
is 0, because every number is a factor of 0 (because 0 = 0 · n for every n!) Beneath 0,
we draw 4 and 3, as these are both maximal once 0 is removed (as no other remaining
elements have 4 or 3 as factors.) Beneath those we draw 2, as with 0, 4 and 3 down 2 is
not a factor of any remaining elements; finally we finish by putting 1 at the bottom, as
it’s the last thing left.

4 3

10. Given the set of binary string S = {0, 1, 10, 101, 111, 001, 0010, 00111} and for x, y ∈ S the relation
⪯ defined as x ⪯ y iff x is a prefix of y. Then (S, ⪯) constitutes a poset. Draw the Hasse diagram,
list all minimal, maximal, least and greatest elements or state that they don’t exist if this is the case.
List all elements that are comparable to 001 and all elements that are not comparable to 001. Give an
example of S ′ ⊆ S such that (S ′ , ⪯) is a totally ordered set.

From the diagram we can see that the maximal elements are 0010, 00111 and 101 as
each of these are not prefix of any other string. However, there is no greatest element as
no we don’t have any string such that all others are prefix of this string.
We can see that 0 and 1 are minimal elements as for each of them there is no other string
which is prefix of either of them. Also, there is no least element as there exists no string
that is prefix of all other strings in S.

Sidenote: Note that adding the empty string λ to S would make this the only minimal
element which would also be the least element. On the other hand there is no string x
that could be added to S to make this the only maximal and hence the greatest element
as no such x exists with 0010, 00111 and 101 being prefix of x at the same time.
From the diagram we can see that the elements 0010, 00111 and 0 are comparable with
001 as either 001 is prefix of them or they are prefix of 001. On the other hand 1, 10, 111
and 101 are incomparable with 001.
An example of S ′ such that (S ′ , ⪯) is a totally ordered set would be S ′ = {1, 10, 101}
as each two elements in S ′ are comparable.

4
 
11. Suppose that A = {1, 2, 3} and S = P(A) \ {1, 2, 3} . Draw a Hasse diagram of the poset (S, ⊆).
How many maximal elements are there in this poset?

By definition, P(A) is all of the subsets of A; therefore, S is all of the subsets of A

except for the subset {1, 2, 3}.
Under the relation ⊆, this poset has the following Hasse diagram:

{1,2} {1,3} {2,3}

{1} {2} {3}

In particular, it has three maximal elements, as none of the three subsets

{1, 2}, {1, 3}, {2, 3} are subsets of any other elements of S.