The following theorem called principle of abstraction or principle of identification of equivalent elements establishes a link between the notion of partition and the notion of equivalence relation.

Let [X] denote the set of all classes of abstraction of an relation  ∼ in the set  X, i.e. [X] = {[x] : x ∈ X}. The set  [X] is a partition of the set X according to the above theorem. Indeed, it suffices to verify that

1. by the lemma  4.2.1 the classes of abstraction are disjoint sets,
2. every set belonging to [X] is non-empty, because for every  y ∈ X, y ∈ [y],
3. the union of all sets of the family [X] (i.e. the union of all abstraction classes) is equal to X, since every element of the set X belongs to an abstraction class.

Let a family  (X_i)_{i ∈I} be a partition of a non-empty set X. Let us define

x ∼ y iff there exist  k ∈ I, such that x ∈ X_k and y ∈ X_k

The relation ~ is an equivalence relation.

The reflexivity follows from the fact that every element of X belongs to a certain set of the partition (X_i)_{i ∈I}. The property of symmetry is evident from the definition of the relation ~. The transitivity follows from the fact that the subsets of any partition are disjoint sets. If  x,y ∈ X_n, and y, z ∈ X_m, then  n=m, i.e. the elements x and z have to belong to the same set of the partition.

Question 4.4.1 Is it possible to define an equivalence relation in a non-empty set X in such a way that one of its abstraction classes is empty?

Example 4.4.1

1. Let us return to the example  4.1.3 (1). The equivalence relation defined in N by the formula
   
   x ∼ y iff  x mod 3 = y mod 3,
   
   determines a partition of the set N into three abstraction classes [0], [1], [2] such that [0] = {3k: k ∈ N}, [1] = {3k+1: k ∈ N}, [2] = {3k+2: k ∈ N}. It is obvious that each natural number belongs to exactly one and only one class.
2. Let  ≈ be a binary relation in the family of subsets of a given set X which is defined for arbitrary sets A, B ∈ P(X) as follows:
   A ≈ B iff there exist a mutually one-to-one function (bijection) mapping set A onto set B.
   This relation is an equivalence relation  (cf. example  4.1.3(2)). If A is an n-element set  then  [A] = {B ∈ P(X): set  B has n elements}. Relation  ≈ is called equipotency relation, the sets being in this relation are called equipotent sets. We shall develop this topic in the lecture 9.

Question 4.4.2 Consider the equipotency relation ≈ in the set of all subsets of the set N of natural numbers (cf. example 4.4.1) and the equivalence classes of this relation. Which of the following properties are valid?

(a)  N ∈ [P]

(b)  P ∈ [N]

(c) {2} ∈ [P]

(d) {1,2,3,4,5,6} ≈ {1,3,5,7,11,13}

Question 4.4.3  Let  m be a fixed non-zero natural number. Prove that the relation r, defined for every  x, y ∈ N by formula:

x r y iff the integer number  (x-y) is divisible by  m,

is an equivalence relation and define its abstraction classes.

« previous section

next section »