1
$\begingroup$

$R$ is relation on $A = \{1,2,3,4\}$

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

I need to find $S$, the smallest relation that contains $R$ that is

  1. symmetric and transitive
  2. $S$ is equivalence relation on $A$ so that $S$ has exactly two equivalence class

My answers are

  1. $S = \{(1,2),(1,4),(4,1),(3,3),(2,1),(2,4),(1,1),(4,4)\}$

  2. $S = \{(1,2),(2,1),(2,3),(3,4),(4,1),(1,4),(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(3,1),(4,2)\}$

but there are more than exactly two equivalence classes. How can I change that?

$\endgroup$
8
  • 1
    $\begingroup$ It is bad form to put phrases like "is my answer correct?", or "Please help me," or "Can't figure this out," etc. in a title. Can you see why? $\endgroup$ – David G. Stork Apr 13 '20 at 21:31
  • $\begingroup$ Your answer 1. is not transitive... For example, you have $(1,2) \in S$ and $(2,1) \in S$, but do not have $(1,1) \in S$. $\endgroup$ – Anton Vrdoljak Apr 13 '20 at 21:31
  • $\begingroup$ @AntonVrdoljak is it ok now ? or (4,4) ∈ S too ? $\endgroup$ – Dana Apr 13 '20 at 21:35
  • $\begingroup$ To @Dana : True, $(4, 4) \in S$ too (for answer 1.). $\endgroup$ – Anton Vrdoljak Apr 13 '20 at 21:47
  • 1
    $\begingroup$ @Shaun changed the title , is that better ? $\endgroup$ – Dana Apr 14 '20 at 7:05
1
$\begingroup$

Observe that, if we represent your initial relation $R$ as a directed graph (where $x$ points to $y$ iff $(x,y) \in R$), then we have this graph:

enter image description here

In graphs like these, certain properties can be intuitively and visually observed:

  • Reflexivity appears if every node points to itself.
  • Symmetry happens if, whenever $x$ points to $y$ (and thus a path exists), then $y$ points to $x$ (and thus a path to "backtrack" exists). Basically, there are no "stray," one-way edges - only closed loops.
  • Transitivity is visible when, if there exists paths $x$ to $y$ and $y$ to $z$, then there is a path $x$ to $z$. For distinct nodes, then this means that, whenever two sides of a triangle are filled in, the last one is too, though the direction depends on the direction of the other sides in question.
  • Your equivalence classes are all of the nodes in each of the disjoint graphs you have. (Two graphs are disjoint if, basically, one is entirely separate from another, totally isolated.)

For your first part, you want the symmetric and transitive closure. We can work each part in turn. To get symmetry, we need to close a loop with $2 \to 1$. We then need to use transitivity: $4 \to 1 \to 2$ requires $4 \to 2$; similarly, $2 \to 1 \to 4$ requires $2 \to 4$. The relation $\{(3,3)\}$ itself is transitive and symmetric, so there's nothing to change there. We thus get the following graph at this stage:

enter image description here

However, since $1 \to 2 \to 1$, $2 \to 4 \to 2$, and $4 \to 2 \to 4$, we need arrows from each of $1,2,4$ pointing to themselves as well by symmetry. Thus, the final result is

enter image description here

This relation is given by our original relation, plus the arrows we added. Thus, the $S$ you seek is

\begin{align*} S &= R \cup \{(2,1),(4,2),(2,4),(1,1),(2,2),(4,4)\} \\ &= \Big\{\underbrace{(1,2),(1,4),(4,1),(3,3)}_{\in R},(2,1),(2,4),(1,1),(4,4), \color{red}{(4,2),(2,2)}\Big\} \end{align*}

In red are those you forgot.


To turn $R$ into an equivalence relation in the most minimal fashion possible, we can turn it into the reflexive/transitive/symmetric closure of itself. However, notice that the relation previously is, in fact, also reflexive. Thus, the relation given by that is also an equivalence relation.

The nodes of the disjoint graphs are $1,2,4$ and $3$, and thus each group is an equivalence class. That is,

$$A/S = \Big\{ \{1,2,4\},\{3\} \Big\}$$

is your quotient set - your set of equivalence classes.


...granted, this question is a bit old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.

$\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.