VGU - CS Study Program
Algebra
Exercise Sheet: Relations
1. Let Z be the set of all integers.
Describe the set Z × Z.
2. Let |A| = m and |B| = n.
How many relations exist from A to B?
3. Is
x
f (x) =
x+1
invertible?
4. For which real numbers a is the function
f (x) = ax, x ∈ R
invertible? Determine the inverse function.
5. Let Rm be a relation of the integers Z defined by:
(x, y) ∈ Rm ⇔ m|(x − y)
Interpretation: (x, y) ∈ Rm if and only if x and y have the same re-
mainder when divided by m.
We denote this by:
x ≡ y mod m
i.e. x is congruent with y modulo m.
Example: We have 1 ≡ 11 mod 10, since both 1 and 11 have the re-
mainder 1 when divided by 10.
Your task: Investigate if R5 is reflexive, symmetric, antisymmetric and
transitive!
6. Is the equality relation, i.e. =, an equivalence relation?
7. Is the relation > an equivalence relation?
8. Is the relation ≥ an equivalence relation?
9. Let
A = { all positive integers divisible by 2 and not exceeding 30}.
(a) Find |A|
(b) Let
B = { all positive integers divisible by 6 and not exceeding 30}.
C = { all positive integers divisible by 8 and not exceeding 30}.
Find B ∪ C, B ∩ C, and binary string representations for B, C,
B ∪ C, B ∩ C, B̄.
10. Let Mn×n be the set of matrices of size n × n. Let
R = {(A, B) : A, B ∈ Mn×n and there exists an invertible matrix P such that A = P.B.P −1 }.
Show that R is an equivalence relation.
11. Given A the set of all webpages. Let R = {(a, b) ∈ A×A : there is at least 1 common link on we
Investigate following properties of R
(a) reflexive
(b) symmetric
(c) transitive
(d) antisymmetric
(e) equivalent
(f) partial order
12. Given A = {1, 2}. Let
R = {(B, C) ∈ 2A × 2A : B ⊆ C}.
(a) Find matrix representation MR for R and |R|.
(b) Investigate reflexive (symmetric, antisymmetric, transitive) pro-
perties of R.
13. Given a set A = {a, b, c} and a relation R with matrix representation
0 1 1
MR = 1 1 0
1 0 1
(a) Find R−1 and its matrix representation
(b) Find R̄ and its matrix representation
(c) Find R2 and its matrix representation
(d) Find R ∪ S, R ◦ S and S ◦ R where
S = {(a, b), (b, b), (b, c), (c, a), (c, b), (c, c)}.
14. Given matrix representations of relations
1 1 1 0
1 1 1 1 1 1 0
MR1 = 0 1 1, MR2 = 1
.
1 1 0
1 1 1
0 0 0 1
Determine whether R1 and R2 are equivalence relations or not.
15. Let R be the relation on the set of all cities in the world such that
(a, b) in R if there is a direct non-stop airline flight from a to b. When
is (a, b) in
(a) R2
(b) R3
(c) R−1
16. Let R be the relation {(a, b) : a 6= b} on the set of integers. What is
the reflexive closure of R?
17. Let R be the relation {(a, b) : a divides b} on the set of integers. What
is the symmetric closure of R?
18. Let R be the relation on the set of all students containing the ordered
pair (a, b) if a and b are in at least one common class and a 6= b. When
(a, b) in
(a) R2
(b) R3
(c) R∗
19. Given the matrix representation of the relation R on {a, b, c, d} as
following
0 0 1 1
1 0 0 0
M = 0
1 0 0
0 0 0 0
Find the transitive closure of R using naive and Warshall’s algorithms.
20. Given the relation R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)} on {1, 2, 3, 4}.
Find
(a) Reflexive closure of R
(b) Symmetric closure of R
(c) Transitive closure of R using naive algorithm and Warshall’s al-
gorithm
(d) Reflexive transitive closure of R
(e) Equivalence closure of R.
21. Given the relation R = {(1, 2), (1, 4), (3, 3), (4, 1)} on {1, 2, 3, 4}. Find
(a) reflexive and transitive closure of R
(b) symmetric and transitive closure of R
(c) equivalence closure of R.
22. We say that two matrices A and B of size n × n are similar if there is
an invertible matrix P such that A = P −1 .B.P . Show that the similar
relation, which is defined by pairs (A, B) such that A is similar to B,
is an equivalence relation.
23. Given the relation R on the set of all bit strings such that (s, t) ∈ R if
and only if s and t contain the same number of 1s.
(a) Prove that R is an equivalence class.
(b) List all bit strings of length 4 equivalent to 01001.
(c) How many bit strings of length n with exactly 2 occurrences of
1s are there?
24. Let R be the relation on the set ordered pairs of positive integers such
that ((a, b), (c, d)) ∈ R if and only if ad = bc. Show that R is an
equivalence relation.
25. Given matrix representation for relations on A = {a, b, c} below. De-
termine if the relations are partial ordering relation or not?
1 1 1
(a) MR1 = 1 1 0
0 0 1
1 1 1
(b) MR2 = 0 1 0
0 0 1
1 0 0
(c) MR3 = 0 1 0
1 0 1
26. Let R be a partial ordering relation on A. Show that the inverse rela-
tion R−1 is a partial ordering relation on A.
27. Ordering the following strings in the lexicographic order:
0, 01, 11, 001, 010, 011, 0001, 0101.
28. Draw Hasse diagram for the following posets
(a) A = {2, 4, 5, 10, 12, 20, 25} with the divisibility relation.
(b) B = 2{a,b,c} with the containment relation.
(c) C = {0, 01, 11, 001, 010, 011, 0001, 0101} with the lexicographic
ordering relation.
