2
$\begingroup$

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

enter image description here

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

$\endgroup$
0
0
$\begingroup$

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:

enter image description here


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

enter image description here


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

enter image description here


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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.