## 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 and be sets.

i) is said to be a **subset** of if each element of belongs to . Usually, this fact we denote by . Likewise, for every set .

ii) and are equal if they consist of the same elements. We say that is a **proper subset** of , if and . Consequently, we accept the notation .

iii) Obviously, a set consisting of no elements we call the **empty set** . Moreover, for any nonempty set we accept the agreement .

**Definition 2**. The **product set** of sets and is defined as a set of all ordered pairs , where and .

**Example 1**. Let and . Then we have . Further, note that , but .

**Definition 3**. Any subset of we call a **relation** between and , in other words .

Furthermore, we say that is **in the relation** to if , and denote this fact by . Respectively, the negation means .

**Definition 4**. An **equivalence relation** on a set is a relation satisfying the following conditions for arbitrary :

i) (**reflexivity**);

ii) If then (**symmetry**);

iii) If and then (**transitivity**).

In cases when is an equivalence relation we will use the notation instead of .

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

i) *Descendant relation*. A relation if is a descendant of is transitive, but not reflexive nor symmetric.

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

Recall that and are the sets of reals and integers respectively.

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

i) For define a relation if . This is an equivalence relation on .

ii) Let if . This relation is not symmetric.

iii) For define if is even. Consequently we obtain an equivalence relation on .

iv) A relation if is odd can not be an equivalence relation on because it is not reflexive and not transitive.

v) Let . Clearly, if is not an equivalence relation since it is not transitive.

vi) Any function induces an equivalence relation on setting if .

**Definition 5**. Assume that is an equivalence relation on a given set . We say that is the **equivalence class** determined by under the equivalence relation .

The set of all equivalence classes we call the **quotient set** of over , in symbols .

**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 is an equivalence relation on then

i) ;

ii) ;

iii) .

**Proof**.

i) By reflexivity for every . So .

ii) Let . Then and imply , showing .

By symmetry we also have . Then analogously. Therefore, .

iii) Suppose that , and let be their common element. According to symmetry and transitivity it follows then and , which implies .

Theorem 1 is proved.

The converse of Theorem 1 is also true.

**Theorem 2**. Every partition of a set to a disjoint union of its subsets defines on an equivalence relation if and belong to the same subset of .

## Leave a Reply

You must be logged in to post a comment.