Easy# Equivalence Relation on a Set: Definition and Examples

ABSALG-EYVXD9

A relation $R$ between two non-empty sets $S$ and $T$ is a subset of the Cartesian product $S\times T$.

We say that $s$ is related to $t$ if and only if $(s,t)\in R$, that we also write as $sRt$.

In Abstract Algebra, many important relations $R$ have $S=T$ so that, in particular:

$$R\subseteq S\times S$$

Such a relation is called:

Reflexiveif $(s,s)\in S\times S$ for all $s\in S$;

Symmetricif $(s,t)\in R$ implies $(t,s)\in R$;

Transitiveif $(s,t)\in R$ and $(t,u)\in R$ implies $(s,u)\in R$.

A relation that is reflexive **and** symmetric **and** transitive is called an **equivalence relation** and these are very important for Abstract Algebra.

When $R\subseteq S\times S$ is an equivalence relation, we usually change notation and write $s\sim t$ for $(s,t)\in R$ and for $sRt$.

We like equivalence relations because the $\sim$ shares many properties with the usual $=$ sign, and it can be very useful to view $s$, $t$ in $S$ with $s\sim t$ as being *the same*.

Which of the following $R\subseteq S\times S$ defines an equivalence relation on $S$?