Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X= \{1,2,3,4\}$, and $R = \{(1,2),(3,4)\}$. Show the minimum equivalence relation on $X$ that extends $R$. How many elements does the quotient set $X/R$ have ? Can somebody give hints to solve it ?

share|improve this question
    
Hint: learn what it means for something to be an equivalence relation. –  Gerry Myerson Jun 11 '13 at 9:17

2 Answers 2

HINT: By definition an equivalence relation is reflexive, so if $E$ is the minimum equivalence relation on $X$ extending $R$, then $E$ must contain the pairs $\langle 1,1\rangle,\langle 2,2\rangle,\langle 3,3\rangle$, and $\langle 4,4\rangle$. It is also symmetric, so since it contains $\langle 1,2\rangle$, it must contain the pair $\langle 2,1\rangle$ as well. What other pair must it contain in order to be symmetric? Let $S$ be the relation that you get when you make all of these additions to $R$.

Finally, $E$ must be transitive. That is, if $x,y,z\in X$, $\langle x,y\rangle\in E$, and $\langle y,z\rangle\in E$, then $\langle x,z\rangle$ must be in $E$. Do you need to add anything to $S$ to make it transitive, or does it already have this property?

It isn’t the quotient $X/R$ that you want: it’s $X/E$. This is just the set of equivalence classes of the equivalence relation $E$. If you understand what an equivalence class is, you should have no trouble determining how many there are, but here’s a start: what elements of $X$ are related to $1$ by $E$? The set of all of those is one of the equivalence classes.

share|improve this answer

Since $R$ is already transitive, it suffices to take the reflexive and symmetric closure of $R$. To make $R$ reflexive, union it with the identity relation: $$ \{(a,a) \mid a \in X\} $$

To make $R$ symmetric, union it with its opposite ordered pairs: $$ \{(a,b) \mid (b,a) \in R \} $$

Can you take it from here? Spoiler below:

This yields the new equivalence relation: $$R^* = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\}$$ which partitions $X$ into the following $2$ equivalence classes: $$\{1,2\} \qquad\text{and}\qquad \{3,4\}$$ Thus, the quotient set $X/R^*$ has $2$ elements.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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