## 2.9. Equivalence relations and partitions

#### Indexed partitions

A family of sets (*A*_{i})_{i∈I}
is called *pairwise disjoint* when any pair of them is
disjoint : ∀*i*,*j*∈*I*, *i*≠*j* ⇒
*A*_{i}∩*A*_{j} = ∅

Equivalently, (∀(*i*,*x*),(*j*,*y*) ∈
∐_{k∈I }*A*_{k}, *x*=*y* ⇒ *i*=*j*),
thus ∃*f*, Gr *f* = ^{t}∐_{i∈I} *A*_{i} with

Dom *f* = Im ∐_{i∈I }
*A*_{i} = ⋃_{i∈I}*A*_{i}

Im *f* = {*i*∈*I* | *A*_{i} ≠ ∅}

Inversely, any *f* ∈ *F*^{E} defines a
family *f*^{ •}_{F} = (*f*^{ •}(*y*))_{y∈F}
∈ ℘(*E*)^{F} of pairwise disjoint sets :

∀*y*,*z*∈*F*, *f*^{ •}(*y*)⋂*f*^{ •}(*z*)
≠ ∅ ⇒ ∃*x*∈ *f*^{ •}(*y*)⋂*f*^{ •}(*z*),
*y* = *f*(*x*) = *z*

An *indexed partition* of a set *E* is a family of
nonempty, pairwise disjoint subsets of *E*, whose union is *E*.
It is always injective :

∀*i*,*j* ∈ *I*, *A*_{i}
= *A*_{j} ⇒ *A*_{i}⋂*A*_{j}=*A*_{i}≠∅
⇒ *i*=*j*.

#### Equivalence relation defined by a function

An *equivalence relation* is a symmetric preorder. Any *f*
: *E* → *F* defines an equivalence relation on *E*
by

∼_{f} = {(*x*,*y*)∈*E* |
*f*(*x*)=*f*(*y*)} = ∐(*f*^{ •}০*f*)

Its composite *g* = *h*০*f* with any *h* ∈ *G*^{F}
satisfies ∼_{f} ⊂ ∼_{g}, with

∼_{f} = ∼_{g}
⇔ Inj *h*_{|Im f} ⇒
*f*= (*h*_{|Im f})^{−1}০*g*

In particular, ∼_{f} coincides with the equality
relation Gr Id_{E}
on *E* when *f* is injective. As ⃗∼_{f}
= *f*^{ •}০*f*, the injectivity of the indexed
partition *f*^{ •}_{Im f}
(that we will abusively denote as *f*^{ •}) gives the
characteristic identity of equivalence relations : *x* ∼_{f} *y* ⇔
⃗∼_{f}(*x*)= ⃗∼_{f}(*y*).

If *F* = Im *f*, the injection (2.6) *G*^{F}
∋ *h* ↦ *h*০*f* has image {*g*∈*G*^{E}
| ∼_{f} ⊂ ∼_{g}}: letting *H* = Im(*f*×*g*),

∼_{f} ⊂ ∼_{g} ⇔ ∀(*y*,*z*),
(*y*′,*z*′) ∈ *H*, *y*=*y*′⇒ *z*=*z*′

Dom *H* = *F*

∀*h* ∈ *G*^{F}, *g* = *h*০*f* ⇔ *H*
⊂ Gr *h*.

For any functions *f*,*g* such that Dom *f* = Dom *g* ∧ ∼_{f}
⊂ ∼_{g}, the function with graph Im (*f*×*g*)
is called the *quotient* *g*/*f*: Im *f* ↠ Im *g*,
and is the only function *h* such that

Dom *h* = Im *f* ∧ *g* = *h*০*f*.

Inversion comes as a particular case: Inj *f* ⇒ *f*^{−1} =
Id_{Dom f }/*f*.

**Remark. ** If *R* is reflexive and ∀*x*,*y*,*z*,
(*xRy* ∧ *zRy*) ⇒ *zRx* then *R* is an equivalence relation.

Proof : symmetry is verified as: ∀*x*,*y*, (*xRy* ∧ *yRy*) ⇒
*yRx*.
Then comes transitivity.∎
#### Partition, canonical surjection

A *partition of **E* is a set of nonempty, pairwise disjoint sets whose
union is *E*, thus the image *P* of any indexed partition *f*^{ •}
of *E* (where *f* is any function with domain *E*):
*P* = Im *f*^{ •} = Im(*f*^{ •}০*f*).

∀*R* ⊂ *E*×*E*, ∀*P* ⊂ ℘(*E*), if *P*
= Im ⃗*R*_{E} then

(∀*x*,*y*∈*E*,
*x*∈⃗*R*(*y*) ⇔
⃗*R*(*x*)=⃗*R*(*y*))
⇔ (∀*x*∈*E*, ∀*A*∈*P*, *x*∈*A* ⇔
⃗*R*(*x*)=*A*) ⇔
Id_{P}=(⃗*R*_{E})^{•}

Thus if *R* is an equivalence relation then *P* is a
partition.

Conversely for any partition *P* of *E*,
∃!*g*∈*P*^{E}, Id_{P} = *g*^{•}
thus *P* = Dom *g*^{•} = Im *g* and

*R*=∐*g* ⊂ *E*×*E*⇒
Id_{P}= (⃗*R*_{E})^{•}

thus *R* is an equivalence relation, where

*x* *R* *y* ⇔ (∃*A*∈*P*,
*x*∈*A* ∧ *y*∈*A*) ⇔ (∀*A*∈*P*,
*x*∈*A* ⇒ *y*∈*A*).

The partition Im^{ } ⃗*R*
associated with an equivalence relation *R* on *E* is
called the *quotient of **E* by *R* and denoted *E*/*R*;
the function ⃗*R* is the *canonical
surjection* from *E* to *E*/*R*. For all *x*
∈ *E*, ⃗*R*(*x*)
is the only element of *E*/*R* containing *x*, and
called the *class of **x* by *R*.
#### Order quotient of a preorder

Any preordered set (*E*,*R*) is reflected through ⃖*R*
by the ordered set (Im ⃖*R*,
⊂ ), with

⃖*R*(*x*) = ⃖*R*(*y*) ⇔ (⃖*R*(*x*)
⊂⃖*R*(*y*)∧⃖*R*(*y*)
⊂⃖*R*(*x*)) ⇔ (*x**R**y*
∧ *y**R**x*)

so that ⃖*R*^{} is injective if
and only if *R* is an order. Through ⃖*R*^{},
the preorder *R* is reduced to the order relation ⊂ in Im ⃖*R*^{},
which plays the role of the quotient of *R* in the quotient
set *E*/(*R*⋂^{t}*R*).

On each (ordered) set *E*, only one order will usually be
considered, denoted ≤_{E}, or abusively ≤ . This may
be justified by defining ordered sets as sets of sets, ordered by ⊂
, ignoring their elements.