[Math] Reflexive, symmetric and transitive closure of the following graph

Question

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 🙂

Answer 1

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:

---

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)\}$

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

$$S_R = R_A \cup \{(d,a),(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)\}$

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.)