# Reflexive, symmetric and transitive closure of the following graph

First of all, I have to understand which relation this graph represents:

Since there are 4 different elements, suppose there's the set $A = \{ a, b, c, d\}$

The relation drawn above, I think, can be described as follows on $A^2$:

$R_A = \{ (a, b), (b, a), (a, d), (b, d)\}$

I have first a more formal question: what would be the set build for this relation?

Now, since I am a newbie, I will just try to give the reflexive, symmetric and transite closure for the relation or to discuss the problems that I have:

1. Reflexive closure:

I think it could be describe just adding the identity pairs:

$R_R = \{ (a, b), (b, a), (a, d), (b, d), (a, a), (b, b), (c, c), (d, d)\}$

2. Symmetric closure:

Here, I know I have to include all the "reversed" pairs of the presents ones, so my solution would be:

$S_R = \{ (a, b), (b, a), (a, d), (d, a), (b, d), (d, b)\}$

3. Transitive closure:

I think I have to include $(a, a)$ because we have $(a, b)$ and $(b, a)$. I have to include $(a, d)$, because we also have $(b, d)$. I also have to include $(b, d)$, because I have both $(b, a)$ and $(a, d)$. So the final closure would be:

$T_R = \{ (a, b), (b, a), (a, d), (b, d), (a, a), (b, b)\}$

If you could try to correct me, if I am wrong, it would be great :)

The relation drawn above, I think, can be described as follows on $$A^2$$: $$R_A = \{ (a, b), (b, a), (a, d), (b, d)\}$$

On the premise that an element points to an element it is related to, this diagram is correct, yes.

I have first a more formal question: what would be the set build for this relation?

Do you mean expressing $$R_A$$ in setbuilder notation? If so, I'm not sure if there's a proper means of doing so that doesn't feel somewhat "off," at least to me. The definition that comes to mind is

$$R_A = \{ (x,y) \in A \times A \mid xRy \}$$

If anyone has a better idea I'd love to hear it, because this mostly just seems to be the definition of a relation (in terms of a set of ordered pairs).

1. Reflexive closure: I think it could be describe just adding the identity pairs: $$R_R = \{ (a, b), (b, a), (a, d), (b, d), (a, a), (b, b), (c, c), (d, d)\}$$

Indeed, that's the idea: the "closure" of a property for a relation is the relation given, plus those you need to get that property to hold. This ambiguity for you is why I might express the closure as, instead

$$R_R = R_A \cup \{(a,a),(b,b),(c,c),(d,d)\}$$

since it makes it clearer which elements you added to $$R_A$$.

Graphically, imagine making this closure as drawing lines so that each element points to itself:

1. Symmetric closure: Here, I know I have to include all the "reversed" pairs of the presents ones, so my solution would be: $$S_R = \{ (a, b), (b, a), (a, d), (d, a), (b, d), (d, b)\}$$

Precisely. Imagine this graphically as "closing" each loop already present. Thus,

$$S_R = R_A \cup \{(d,a),(d,b)\}$$

1. Transitive closure: I think I have to include $$(a, a)$$ because we have $$(a, b)$$ and $$(b, a)$$. I have to include $$(a, d)$$, because we also have $$(b, d)$$. I also have to include $$(b, d)$$, because I have both $$(b, a)$$ and $$(a, d)$$. So the final closure would be: $$T_R = \{ (a, b), (b, a), (a, d), (b, d), (a, a), (b, b)\}$$

Yup. For this, graphically, you need to envision it like so: if you can follow two consecutive lines from one element to another and then to a third, you also need a line going directly from the first to the third. The only such chains you can make are

• $$a \to b \to a$$
• $$b \to a \to b$$
• $$b \to a \to d$$
• $$a \to b \to d$$

and the latter two are already in the graph. So you just have

$$T_R = R_A \cup \{(a,a),(b,b)\}$$

So in summary, what you did seems fine.

(Though you did post this years ago so I imagine you don't really need this confirmation and help now, but if nothing else this might help others in the future and also gets this off the unanswered list.)