# Equivalence Relation

DEFINITION1: Let $X$ be a set and $R\subset{X\times{X}}$. If the relation $R$ is reflexive, symmetric and transitive, then the relation $R$ is called an "equivalence relation" and denoted by $R=\sim$ in general.

DEFINITION2: Let $\sim$ be an equivalence relation over a set $X$ and $a\in{X}$. The set defined as $\{x\in{X}\:|\:a\sim{x}\}\subset{X}$ is called the “equivalence class” of $a$ under $\sim$ and denoted by $\overline{a}$, $[a]$ or $[a]_{\sim}$. Since $a\sim{a}$ for every $a\in{X}$, then $a\in{\overline{a}}$. So the equivalence class $\overline{a}$ is non-empty for every $a\in{X}$. The family of all the equivalence classes of the relation $\sim$ is called the “quotient set” of $X$ by $\sim$ and denoted by ${^X}/{_\sim}$

I.e.,

${^X}/{_\sim}=\{\overline{a}\:|\:a\in{X}\}\subset{\mathbf{P}(X)}$.

DEFINITION3: Let $\sim$ be an equivalence relation over a set $X$ and $a,b\in{X}$. If $b\in{\overline{a}}$, then $b$ is called a “representative class” of the equivalence class $\overline{a}$.

# Relation

DEFINITION1: Let $X$ and $Y$ be two sets. Any subset of the cartesian product $X\times{Y}$ is called a relation with domain $X$ and codomain $Y$. While some sources are giving the definition of relation, they assume $X,Y\ne{\varnothing}$ and it’s said the emptyset being a subset of $X\times{Y}$ isn’t a relation. However, the assumption “the emptyset is a relation” is not a problem for any branch of the mathematics. On the contrary, the assumption “the emptyset is a relation” plays an important role in some branch of the mathematics.

If $X$ and $Y$ are two sets with $n$ and $m$ elements respectively, then the cartesian product $X\times{Y}$ has $n.m$ elements. Since a relation with domain $X$ and codomain $Y$ is an element of the power set $\mathbf{P}(X\times Y)$ and the number of the elements of the power set of a set with $k$ elements is $2^{k}$, then the number of all the relations with domain $X$ and codomain $Y$ is $2^{n.m}$. If $X,Y\ne{\varnothing}$ and at least one of $X$ and $Y$ is infinite set, then the number of all the relations with domain $X$ and codomain $Y$ is also infinity.

Let $R\subset{X\times{Y}}$ be a relation not being the emptyset. The statement $(x,y)\in{R}$ is read “x is R-related to y” and is denoted by $xRy$ or $R(x)=y$.

EXAMPLE1: Let $X=\{a,b,c\}$ and $Y=\{1,2\}$. Since $X$ has 3 elements and $Y$ has 2 elements, the number of all the relations with domain $X$ and codomain $Y$ is $2^{2.3}=2^{6}=64$. We can give some of these $64$ relations:

$R_1=\varnothing$,