Discrete Mathematics, Equivalence Relations
Give the specific reason why the following set $R$ does not define an equivalence relation on the set $\{1,2,3,4\}$.
R$=\{(1,1)(2,2),(3,3),(4,4),(2,3)(3,2),(2,4),(4,2)\}$.
ReflexivityFor any a ϵ S, $aRa$.
SymmetryFor any a,b ϵ S, $aRb \iff bRa$.
TransitivityFor any a,b,c ϵ S, if $aRb$ and $bRc$, then $aRc$.
I am unsure how one would just simply compare numbers. Would I say for $(1,1)$ think of it saying $1R1$? I mean $1$ does $= 1$. But soon as we get to $2,3$ it wont work because $2=2$. I know I am missing something here. I am wondering how I could figure this out without being given an equation like $x/y$ element of $S$, then I could say $xy=yx$, we have $x/yRx/y$ so its reflexive and so on.
$\endgroup$ 42 Answers
$\begingroup$You should interpret the fact that $(1,1)\in R$ as meaning $1R1,$ or in other words that $1$ is related to $1$ under the relation. Likewise $(2,3)\in R$ means that $2R3$ so that $2$ is related to $3.$ This does not conflict with the fact that $2\ne 3$ since the relation $R$ is not equality. However if $R$ is an equivalence relation the reflexivity property implies that $1R1, 2R2,$ etc. So if they're equal then they must be related, however the converse doesn't hold: if they aren't equal they can still be related.
The symmetry condition says that if $x$ if related to $y$ then $y$ is related to $x.$ So, as an example, if $(2,3)\in R$ then we must have $(3,2)\in R.$ This holds in your example so this example is consistent with $R$ obeying symmetry. If you had $(2,3)\in R$ but $(3,2)$ wasn't in $R,$ then you would have a counterexample to symmetry and would be able to say that $R$ violates symmetry and is not an equivalence relation. However looking at your $R$ you see that we have $(2,4)\in R$ and $(4,2)\in$ which is again consistent with symmetry, and we can't find any counterexamples. So $R$ is a symmetric relation.
So that leaves transitivity which says that if jake is friends with sally and sally is friends with linda then jake is friends with linda. If you look at $R$ you will see that $3$ is friends with $2$ and $2$ is friends with $4$ but $3$ is not friends with $4.$ This is a violation of transitivity. So $R$ is not an equivalence relation.
Note: You seem to be confusing equality with being related under $R$ so I'll add something down here that I probably should have emphasized more up there: Equality is an equivalence relation but not all equivalence relations are equality. You can think of $R$ as something that behaves sort of like an equals sign, but it's more general than that. If $S=\{1,2,3,4\}$ as above you could write the relation of equality on $S$ as $$E = \{(1,1),(2,2),(3,3),(4,4)\}.$$ And then you would have $aEb$ exactly if and only if $a=b.$ Other equivalence relations will have more pairs in them since reflexiveness guarantees that all four of those have to appear. For instance the set of all possible pairs is is an equivalence relation (if a not-that-interesting one) in which any two numbers in $S$ are related.
$\endgroup$ 1 $\begingroup$Short guide:
Yes $(i,j)$ means $iRj$, it doesn't mean $i = j$.
I see $(3,2)$ and I see $(2,4)$, if it is transitive, what element should appear in the set as well?
$\endgroup$ 1
