Discrete structures

Question

Consider the following relation R on the set A = {1, 2, 3, 4}:

R = {(1, 2), (2, 3), (3, 1), (4, 1)}

Find the transitive closure of this relation.

Answer 1

Let me rewrite the relation R like this:

1 R 2, 2 R 3, 3 R 1, 4 R 1

Denote the transitive closure by R*.

In general, for two numbers a and b,

a R* b iff there is sequence of numbers a₁, ..., a_n such that

a = a₁, b = a_n, and for all 1 <= i < n, a_i R a_i+1

Looking at the given relation R, you can see, for example

1 R 2 R 3 R 1

Therefore the three numbers 1, 2, 3 are all mutually related by R*.

In addition,

4 R 1 R 2 R 3 R 1

Therefore 4 is also related to each of 1, 2, 3.

But 4 itself never appears on the right hand side,

so nothing is related to 4.

Thus

R* = {(1, 1), (1, 2), (1, 3),

(2, 1), (2, 2), (2, 3),

(3, 1), (3, 2), (3, 3),

(4, 1), (4, 2), (4, 3)}