14
Oct 20

Equivalence Relations

We welcome our new author Nurlan Abiev. He intends to cover topics in Mathematics.

Under a set we mean an undefined term thought intuitively as a collection of objects of common property.

Definition 1. Let $A$ and $B$ be sets.
i) $B$ is said to be  a subset of $A$ if each element of $B$ belongs to $A$. Usually, this fact we denote by $B \subseteq A$. Likewise,  $A\subseteq A$ for every set $A$ .

ii) $A$ and $B$ are  equal if they consist of the same elements. We say that $B$ is  a proper subset of $A$,  if $B \subseteq A$ and $B \ne A$. Consequently, we accept the notation $B\subset A$.

iii) Obviously, a set consisting of no elements we  call  the empty set  $\emptyset$. Moreover, for any nonempty set $A$ we accept the agreement $\emptyset\subset A$.

Definition 2. The  product set $X\times Y$ of sets $X$ and $Y$ is defined as a set of all ordered pairs $(x,y)$, where $x\in X$ and $y\in Y$.

Example 1. Let  $X=\{a,b,c\}$ and $Y=\{0,1\}$. Then we have $X \times Y=\{(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)\}$. Further, note that $(b,1) \in X \times Y$, but $(1,b) \notin X \times Y$.

Definition 3.  Any subset $R$ of $X \times Y$ we call  a relation between  $X$ and $Y$, in other words $R \subseteq X\times Y$.

Furthermore, we say that $x$ is in the relation $R$ to $y$ if $(x,y)\in R$, and denote this fact by $xRy$. Respectively, the negation $\overline{xRy}$ means $(x,y)\notin R$.

Definition 4.  An equivalence relation on a set $X$ is a relation $R \subseteq X\times X$ satisfying the following conditions for arbitrary $x,y,z \in X$:
i) $xRx$  (reflexivity);
ii) If $xRy$ then $yRx$  (symmetry);
iii) If $xRy$ and $yRz$ then $xRz$  (transitivity).

In cases when $R$ is an equivalence relation we will use the notation $x\sim y$ instead of $xRy$.

Example 2. Assume that  $X$  is the set of all people in the world. Consider some relations on $X$.

i)  Descendant relation. A relation $x\sim y$ if $x$ is a descendant of $y$ is transitive, but not reflexive nor symmetric.

ii)  Blood relation. A relation $x\sim y$ if $x$ has an ancestor who is also an ancestor of $y$ is reflexive and symmetric, but not transitive (I am not in a blood relation to my wife, although our children are).

iii)  Sibling relation. Assuming $x\sim y$ if $x$ and $y$ have the same parents we define an equivalence relation.

Recall that $\mathbb{R}$ and $\mathbb{Z}$ are the sets of reals and integers respectively.

Example 3. Examples of equivalence (non equivalence) relations:

i) For $x,y\in \mathbb{R}$ define a relation $x\sim y$ if $x-y\in \mathbb{Z}$. This is an equivalence relation on $\mathbb{R}$.

ii) Let $x\sim y$ if $x\le y$. This relation is not symmetric.

iii) For $x,y\in \mathbb{Z}$ define $x\sim y$ if $x-y$ is even. Consequently we obtain an equivalence relation on $\mathbb{Z}$.

iv) A relation $x\sim y$ if $x-y$ is odd can not be an equivalence relation on $\mathbb{Z}$ because it is not reflexive and not transitive.

v) Let $x,y\in \mathbb{R}$. Clearly, $x\sim y$ if $|x-y|\le 1$ is not an equivalence relation since it is not transitive.

vi) Any function $f\colon X\rightarrow Y$ induces an equivalence relation on $X$ setting $x\sim y$ if $f(x)=f(y)$.

Definition 5.  Assume that $R$ is an equivalence relation on a given set $X$. We say that $R_a:=\left\{x\in X \; | ~\; xRa \right\}$ is the equivalence class determined by $a\in X$ under the equivalence relation $R$.

The set $\{R_a~|~ a\in X\}$ of all equivalence classes we call  the quotient set of $X$ over $R$, in symbols $X/ R$.

Theorem 1. Every equivalence relation on a given set provides a partition of this set to a disjoint union of equivalence classes, in other words, if $R$ is an equivalence relation on $X$ then
i) $X=\bigcup_{x\in X}R_x$;
ii) $aRb \Rightarrow R_a=R_b$;
iii) $\overline{aRb} ~\Rightarrow~ R_a\cap R_b=\emptyset$.

Thus any two equivalence classes coincide if they admit a nonempty intersection.

Proof.
i) By reflexivity $x\in R_x$ for every $x\in X$. So $X= \bigcup_{x\in X}R_x$.

ii) Let $x\in R_a$. Then $xRa$ and $aRb$ imply $xRb \:\Leftrightarrow\: x\in R_b$, showing $R_a\subseteq R_b$.
By symmetry we also have $bRa$. Then $R_b \subseteq R_a$ analogously. Therefore, $R_a=R_b$.

iii) Suppose that $R_a \cap R_b \ne \emptyset$, and let $x$ be their common element. According to symmetry and transitivity it follows then $xRa$ and $xRb$, which implies $aRb$.
Theorem 1 is proved.

The converse of Theorem 1 is also true.

Theorem 2. Every partition of a set $X$ to a disjoint union of its subsets defines on $X$ an equivalence relation $x\sim y$ if $x$ and $y$ belong to the same subset of $X$.