Oct 20

Equivalence Relations

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.

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.


Leave a Reply

You must be logged in to post a comment.