Free Version
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:

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

Symmetric if $(s,t)\in R$ implies $(t,s)\in R$;

Transitive if $(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$?

A

$S$ is the set of positive integers and $(s,t)\in R$ if and only if $s$ divides $t$

B

$S$ is the set of positive integers and $(s,t)\in R$ if and only if $s-t$ is divisible by $7$

C

$S=\{$Jay Leno, Jerry Seinfeld, Chaim Yankel$\}$ and $(s,t)\in R$ if and only if $s$ knows $t$

D

$S=\{$myself (where myself has no siblings), my son (where we assume myself does have a son)$\}$,

and

$(s,t)\in R$ if and only if the father of $t$ is the son of the father of $s$.

E

$S$ is the set of positive integers and $(s,t)\in R$ if and only if $s < t$