2.9. Equivalence relations and partitions

Indexed partitions

A family of sets (Ai)iI is called pairwise disjoint when any pair of them is disjoint : ∀i,jI, ijAiAj = ∅
Equivalently, (∀(i,x),(j,y) ∈ ∐kI Ak, x=yi=j), thus ∃f, Gr f = tiI Ai with
Dom f = Im ∐iI Ai = ⋃iIAi
Im f = {iI | Ai ≠ ∅}
Inversely, any fFE defines a family fF = (f(y))yF ∈ ℘(E)F of pairwise disjoint sets :
y,zF, f(y)⋂f(z) ≠ ∅ ⇒ ∃xf(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,jI, Ai = AjAiAj=Ai≠∅ ⇒ i=j.

Equivalence relation defined by a function

An equivalence relation is a symmetric preorder. Any f : EF defines an equivalence relation on E by
f = {(x,y)∈E | f(x)=f(y)} = ∐(ff)
Its composite g = hf with any hGF satisfies ∼f ⊂ ∼g, with
f  = ∼g ⇔ Inj h|Im ff= (h|Im f)−1g
In particular, ∼f coincides with the equality relation Gr IdE on E when f is injective. As  f = ff, the injectivity of the indexed partition fIm f (that we will abusively denote as f) gives the characteristic identity of equivalence relations : xf y ⇔ f(x)= f(y).
If F = Im f, the injection (2.6) GFhhf has image {gGE | ∼f ⊂ ∼g}: letting H = Im(f×g),
f ⊂ ∼g ⇔ ∀(y,z), (y′,z′) ∈ H, y=y′⇒ z=z
Dom H = F
hGF, g = hfH ⊂ 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 fg = hf.
Inversion comes as a particular case: Inj ff−1 = IdDom f /f.

Remark. If R is reflexive and ∀x,y,z, (xRyzRy) ⇒ zRx then R is an equivalence relation.
Proof : symmetry is verified as: ∀x,y, (xRyyRy) ⇒ 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(ff).

RE×E, ∀P ⊂ ℘(E), if P = Im RE then
(∀x,yE, xR(y) ⇔ R(x)=R(y)) ⇔ (∀xE, ∀AP, xAR(x)=A) ⇔ IdP=(RE)
Thus if R is an equivalence relation then P is a partition.
Conversely for any partition P of E, ∃!gPE, IdP = g thus P = Dom g = Im g and
R=∐gE×E⇒ IdP= (RE)
thus R is an equivalence relation, where
x R y ⇔ (∃AP, xAyA) ⇔ (∀AP, xAyA).
For any equivalence relation R on E, the partition Im R is called the quotient of E by R, written E/R.
The function R is the canonical surjection from E to E/R.
For all xE, R(x) is the only element of E/R containing x, and called the class of x by R.
For any function f such that Dom f = ER ⊂ ∼f, we can also write f/R for the function f / 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)) ⇔ (xRyyRx)

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/(RtR).
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.

1. First foundations of mathematics
2. Set theory (continued)
2.1. Tuples, families
2.2. Boolean operators on families of sets
2.3. Products, graphs and composition
2.4. Uniqueness quantifiers, functional graphs
2.5. The powerset axiom
2.6. Injectivity and inversion
2.7. Binary relations ; orders

2.8. Canonical bijections
2.9. Equivalence relations and partitions
2.10. Axiom of choice
2.11. Notion of Galois connection
3. Model theory