Raising the bar

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 $latex A$ and $latex B$ be sets.
i) $latex B$ is said to be  a subset of $latex A$ if each element of $latex B$ belongs to $latex A$. Usually, this fact we denote by $latex B \subseteq A$. Likewise,  $latex A\subseteq A$ for every set $latex A$ .

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

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

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

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

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

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

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

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

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

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

ii)  Blood relation. A relation $latex x\sim y$ if $latex x$ has an ancestor who is also an ancestor of $latex 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 $latex x\sim y$ if $latex x$ and $latex y$ have the same parents we define an equivalence relation.

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

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

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

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

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

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

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

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

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

The set $latex \{R_a~|~ a\in X\}$ of all equivalence classes we call  the quotient set of $latex X$ over $latex R$, in symbols $latex 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 $latex R$ is an equivalence relation on $latex X$ then
i) $latex X=\bigcup_{x\in X}R_x$;
ii) $latex aRb \Rightarrow R_a=R_b$;
iii) $latex \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 $latex x\in R_x$ for every $latex x\in X$. So $latex X= \bigcup_{x\in X}R_x$.

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

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

The converse of Theorem 1 is also true.

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