Equivalence Relations

Oct 20

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$ .

Raising the bar

Ins and outs of quantitative courses of University of London

Equivalence Relations

Equivalence Relations

Related

Leave a Reply

Subscribe to Blog via Email

Recent Posts

Menu

Archives

Blog Stats