2.9. Relations d'équivalence et partitions

Partitions indexées

Les ensembles d'une famille (Ai)iI sont dits deux à deux disjoints si ceux de toute paire d'entre eux sont disjoints : ∀i,jI, ijAiAj=∅.
Autrement dit, (∀(i,x),(j,y) ∈ ∐kI Ak, x=yi=j), donc ∃f, Grf = tiI Ai avec
Dom f = Im ∐iI Ai = ⋃iIAi
Im f ={iI| Ai ≠ ∅} 
Inversement, tout fFE définit une famille fF = (f(y))yF ∈ ℘(E)F d'ensembles deux à deux disjoints :
y,zF, f(y)⋂f(z) ≠ ∅⇒∃xf(y)⋂f(z), y=f(x)=z

Une partition indexée d'un ensemble E est une famille de parties de E non vides, deux à deux disjointes et dont l'union est E. Elle est toujours injective :
i,jI, Ai = AjAiAj=Ai≠∅ ⇒ i=j.

Relation d'équivalence définie par une fonction

Une relation d'équivalence est un préordre symétrique.

Toute fonction f : EF définit une relation d'équivalence sur E par
f ={(x,y) ∈ E| f(x)=f(y)}=∐(ff)
Sa composée g = hf avec tout hGF satisfait ∼f ⊂ ∼g, avec
f  = ∼g ⇔ Inj h|Imff= (h|Imf)−1g
En particulier, ∼f coïncide avec la relation d'égalité Gr IdE sur E quand f est injective. Comme f =ff, l'injectivité de la partition indexée fImf (qu'on notera abusivement f) donne l'identité characteristique des relations d'équivalence : xf y ⇔ f(x)= f(y).
Si F = Im f, l'injection (2.6) GFhhf a pour image {gGE | ∼f ⊂ ∼g}: notant H=Im(f×g),
f ⊂  ∼g ⇔ ∀(y,z), (y′,z′) ∈ H, y=y′⇒ z=z
Dom H = F
hGF, g=hf ⇔ HGr h.
Pour toutes fonctions f,g telles que Dom f = Dom g∧ ∼f ⊂ ∼g, la fonction de graphe Im(f×g) est appelée le quotient g/f: ImfImg, et est la seule fonction h telle que
Dom
h = Im fg = hf.
L'inversion vient comme cas particulier: Inj ff−1 =IdDomf/f.

Note. Si R est réflexive et x,y,z, (x R yz R y)⇒z R x alors R est une relation d'équivalence.
Preuve : on vérifie la symétrie: ∀x,y, (x R yy R y)⇒y R x. La transitivité en découle.∎

Partition, surjection canonique

Une partition de E est un ensemble de parties de E non vides, deux à deux disjoints et dont l'union est E. C'est l'image de toute partition indexée f de E (où f est toute fonction de domain E): P=Imf=Im(ff).
RE×E, ∀P ⊂ ℘(E), si P = Im RE alors
(∀x,yE, xR(y) ⇔ R(x)=R(y)) ⇔ (∀xE, ∀AP, xA ⇔ R(x)=A) ⇔ IdP=(RE)
donc si R est une relation d'équivalence alors P est une partition.
Réciproquement pour toute partition P de E, ∃! gPE, IdP=g donc P=Domg=Img et
R=∐gE×EIdP= (RE)
donc R est une relation d'équivalence, où
x R y ⇔ (∃AP, xAyA) ⇔ (∀AP, xAyA).
La partition Im R associée à une relation d'équivalence R sur E est appelée le quotient de E par R et notée E/R; la fonction R est la surjection canonique de E sur E/R. Pour tout xE, R(x) est l'unique élément de E/R contenant x, et appelé la classe de x par R.

Ordre quotient d'un préordre

Tout ensemble préodonné (E,R) est reflété à travers R par l'ensemble ordonné (Im R, ⊂ ), avec

R(x) = R(y) ⇔ (R(x) ⊂R(y)∧R(y) ⊂R(x)) ⇔ (xRyyRx)

de sorte que R est injective si et seulement si R est un ordre. A travers R , le préordre R se réduit à la relation d'ordre ⊂ dans Im R qui joue le rôle du quotient de R dans l'ensemble quotient E/(RtR).
Sur chaque ensemble (ordonné) E, on n'utilisera généralement qu'un seul ordre noté ≤E, ou abusivement ≤. Cela serait justifiable en définissant les ensembles ordonnés comme ensembles d'ensembles, ordonnés par ⊂ , ignorant leurs éléments.



Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles (suite)
2.1. Uplets, familles
2.2. Opérateurs booléens sur les ensembles
2.3. Produits, graphes et composition
2.4. Quantificateurs d'unicité, graphes fonctionnels
2.5. L'ensemble des parties
2.6. Injectivité et inversion
2.7. Relations binaires, ensembles ordonnés
2.8. Bijections canoniques
2.9. Relations d'équivalence et partitions
2.10. Axiome du choix
2.11. Correspondance de Galois
3. Théorie des modèles