Each equivalence relation groups together objects that are similar in some sense. These groups of objects are called equivalence classes. Let us first consider en example.

Example 4.2.1

Let r be a relation on the set of integers such that x r y  iff sgn(x) = sgn(y) where sgn is a function which returns  1 if the argument is positive,  -1 if the argument is negative, and returns 0 if the argument is zero. It is clear that r is an equivalence relation. It is easy to see that for every positive integer x, (x, 1) ∈r and for every negative integer x, (x, -1) ∈r, and 0  belongs neither to the first nor to the second group. Hence, the set of integers is decomposed into three subsets, namely {x: x < 0}, {x : x > 0} and {0}, that are uniquely determined by the relation r. These subsets are called equivalence classes or classes of abstraction of r.

 We say that the element x is a representative of the class  [x].

Example 4.2.2

1. Let r be a binary relation on the set N of natural numbers defined as follows: (x,y) ∈ r iff x+y is an even number. The relation is reflexive, since  x+x = 2x is an even number.  It is a symmetric relation by the commutativity of addition. The relation is also transitive: if x + y is an even number and y + z is an even number then
• either numbers  x and y are both even and then numbers y and z must be also even,
• or x and y are both odd, but then y and z must be odd numbers too.

As a consequence, the sum  x + z is even in any case. The equivalence class of number 0 contains all even numbers,  [0] = P. The abstraction class of number 1 contains all odd numbers,  [1] = NP. These two classes exhaust all natural numbers.

2. Let X be the set of all non-zero vectors on the plane with the origin in the point O = (0, 0). Every such vector can be characterized uniquely by the coordinates of the terminal point w = (w.x, w.y). Consider a binary relation in the set X defined as follows:

   w₁ ∼ w₂ iff there exist a non-zero real number z, such that  w₁.x = z * w₂.x and w₁.y = z*w₂.y,

   for every pair pf vectors  w₁, w₂ in the set  X.

   It follows from the above definition that two vectors belonging to the set X are in the relation r iff their terminal points lie on the same line which passes through the origin O of the system of coordinates. It is obvious that it ia an equivalence relation.

   An abstraction class of a vector w which terminates in the point (1, 0) is the ax Ox of the system of coordinates. The relation has infinitely many abstraction classes. Each abstraction class is represented by a line passing through the point O.

Question 4.2.1 How many equivalence classes has the equivalence relation defined for any natural numbers x and y by formula:

The following lemma establishes the fundamental laws of abstraction classes. First, each abstarction class is a non-empty set. Second, if two elements are  equivalent then their abstraction classes are equal. Third, different abstraction classes are disjoint sets.

Proof.

Ad (1) The property (1) follows immediately from the reflexivity of the relation  ∼.

Ad (2) Let us assume that  x ∼ y. Then the following formulas are equivalent:

z ∈ [x] iff z ∼ x iff z ∼ y iff z ∈ [y].

Hence [x] = [y].

Conversely, assume that  [x] = [y]. By  (1) x ∈ [x] and consequently  x ∈ [y]. From the definition of abstarction classes it follows that x ∼ y.

Ad (3) Let [x] ≠ [y]. Suppose that [x] ∩ [y] ≠ ∅  then there exists an element  z such that  z ∈ [x] and z ∈ [y]. Hence  z ∼ x and z ∼ y. Therefore, from the symmetry and from transitivity of the relation  ∼, we obtain x ∼ y, which by the point (2) of the present lemma leads to a contadiction.

Remark. Proofs like the one presented in the point (3) of the above lemma are called apagogic or proofs by "reductio ad absurdum" or indirect proofs. We shall say more on the proofs of this type in the lecture 6.

In the preceding paragraph of this lecture we have proved that each function determines an equivalence relation (c.f. lemma 4.1.1).It turns out that the converse also holds: each equivalence relation ~ in a set X determines a function f _∼ mapping the set X in a powerset P(X).The function is defined as follows: f _∼(x) = [x]. The function is called a canonical mapping. Function f_~  is defined for every element x of the set X, because every element belongs to an abstraction class for which it is a representative. The function f _∼is not, in general, an epimorphism, since for every  y ∼ x, f _∼ (x) = [x] = [y] = f _∼ (y). We shall say more on the properties of this mapping in the lecture 10.

Question 4.2.2 A relation r was defined by means of a function f, in the way described in the lemma 4.1.1. Give the necessary and sufficient condition for the abstarction classes containing exacly one element.

« previous section

next section »