Next: Posets
Up: Binary relations
Previous: Binary relations between elements
Contents
Definition 4.3.1
The relation
on
is an equivalence relation if it is reflexive,
symmetric and transitive.
We often denote these properties by ``RST''; note that ``R'' (for reflexivity) concerns
single elements, ``S'' (for symmetry) concerns pairs of elements, and ``T'' (for transitivity) concerns triples of elements.
These are ``nice'' properties designed to make
behave something like , with respect to some specific property of the elements of the set.
Example 4.3.2
Consider the set
of all integers and the relation
on
defined as follows:
This relation is an equivalence relation on
:
 (i)
 R:
, thus
.
 (ii)
 S:
, i.e
.
 (iii)
 T:
It follows that, i.e.
.
Example 4.3.3
The binary relation given in Example
2.6 is an equivalence relation.
Definition 4.3.4
If
is an equivalence relation on the set
and
, then
is called
the equivalence class of
.
Example 4.3.5
In Example
2.6, each possible eye color determines an equivalence class.
Definition 4.3.6
Let
be a set. A collection
of non empty subsets of
form a
partition of if the following conditions hold:
 (i)

.
 (ii)
 If , then
.
For example, the set of odd integers and the set of even integers form a partition of
.
Theorem 4.3.7
If
is an equivalence relation then the equivalence classes
form a partition of
.
The converse of this is true: if we have a partition of we can
define an equivalence relation on by
iff and are in
the same part.
Remark 4.3.8 (For algebraists only)
An application of this is the proof of Lagrange's Theorem. The idea
is to show that being in the same (left/right) coset is an equivalence
relation.
Definition 4.3.9
Given an equivalence relation
on
, the
set of all equivalence classes is called
the quotient set and is denoted by
.
Example 4.3.10
On the set
of all the real numbers we define the following relation:
Th relation
is an equivalence relation on
(the proof is very similar to the proof in example
3.11).
The equivalence class of the real number
is the set
, and any equivalence class contains a single element in the interval
. Thus the unit circle in the plane is graphical representation of the quotient set: every point on the circle determines a single angle with the positive semi
axis, i.e. a single element of
.
Example 4.3.11 (Congruences in
)
This example is very important, both in Algebra and in Number Theory.
Let
be a positive integer. We define a binary relation in
, called
congruence modulo as follows:
Congruence modulo
is an equivalence relation on
:
Let us describe the equivalence classes for various values of the positive integer
:
 If , we have:
i.e. every integer is congruent to every integer modulo . There is only one equivalence class modulo (therefore this congruence is not so interesting!).
 If , there are two equivalence classes: the one contains all the even numbers, the other one contains all the odd numbers.
 If , there are three equivalence classes, namely:
These examples are particular cases of a general result:
Theorem 4.3.12
Let
be a positive integer. There are exactly
congruence classes of integers modulo
.
Proof.
Let us use the Euclidean Division (v.i. Proposition
2.18 in Chapter
6): for any
, there exists a unique pair
, where
,
and
. The integer
is called the
quotient and
is the
remainder.
We have:
, i.e.
. By transitivity, two integers are congruent modulo
if, and only if, they have the same remainder in division by
. Therefore, the equivalence classes are completely determined by the integers
verifying the double inequality
, i.e. there are exactly
equivalence classes.
Returning to a general relation
, for each
we define
there is a path of length at from
to 

and
, the transitive
closure of
.
is defined as
.
Next: Posets
Up: Binary relations
Previous: Binary relations between elements
Contents
root
20020610