## 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*_{|Imf} ⇒
*f*= (*h*_{|Imf})^{−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*^{ •}_{Imf}
(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_{Domf}/*f*.

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

Proof : symmetry is verified as: ∀*x*,*y*, (*x* *R* *y*∧*y* *R* *y*)⇒*y* *R* *x*.
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 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.