0
$\begingroup$

Can anyone tell me why the first set is an equivalence relation, and not the second? As far as I can see, both are reflexive, symmetric and transitive, but my books says only the second one is an equivalence relation. The set is {1,2,3,4}

{(1,4),(4,1),(2,2),(4,4)}
{(1,1),(2,2),(2,3),(3,2),(3,3),(4,4)}

$\endgroup$
1
$\begingroup$

Since the underlying set is $\{1,2,3,4\}$, the first relation is not reflexive: it’s missing the pairs $\langle 1,1\rangle$ and $\langle 3,3\rangle$. It’s also not transitive, since it has $\langle 1,4\rangle$ and $\langle 4,1\rangle$ but not $\langle 1,1\rangle$.

$\endgroup$
  • $\begingroup$ I see, but is it required for an equivalence relation to include all the given elements in the set? $\endgroup$ – user103548 Nov 4 '13 at 10:31
  • $\begingroup$ @user103548: A relation on $A$ is reflexive if and only if it includes $\langle a,a\rangle$ for every $a\in A$. $\endgroup$ – Brian M. Scott Nov 4 '13 at 10:32
0
$\begingroup$

The first is not an equivalence relation because it is not reflexive. It is missing $(1,1),(3,3)$. The lack of $(1,1)$ also implies that it is not transitive, because we have both $(1,4),(4,1)$. The second set, however, is an equivalence relation.

For reference, here's a definition:

A relation $R$ on a set $X$ is a subset of $X \times X$.

An equivalence relation on $X$ is a relation $R$ on $X$ such that:

  • Reflexivity: For all $a \in X, (a,a) \in R$
  • Symmetry: For all $a,b \in X$, if $(a,b) \in R$, then $(b,a) \in R$.
  • Transitivity: For all $a,b,c\in X$, if $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$.
$\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.