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) .
Thus any two equivalence classes coincide if they admit a nonempty intersection.
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.