3.12. Composition des relations

La catégorie des relations

Cette catégorie étend la catégorie des ensembles en gardant les mêmes objets (les ensembles) et en définissant Mor(E,F) comme l'ensemble ℘(E×F) de toutes les relations entre E et F. Leur composition est définie par

grR,S, R;S = {(x0,y1) | (x,y)∈R×Sx1=y0}
RE×F, ∀SF×G, R;S = {(x,z)∈E×G | ∃yF, xRyySz}
= ∐xE SR(x)

Cela étend la composition des fonctions présentées comme relations fonctionnelles, avec les mêmes éléments neutres (1E = 𝛿E = Gr IdE).
(C'est la seule façon naturelle d'étendre la composition, car l'autre expression de la composée de fonctions par leurs graphes, avec ∀yF, xRyySz, perdrait l'associativité dans les cas non fonctionnels).
Cette catégorie agit fidèlement par images directes () sur les ensembles de parties de ses objets, et co-agit sur eux par préimages (): ∀RE×F, ∀SF×G,

AE, (SR)A = S(RA)
BG, (R;S)B = R(SB)

Pour cette action, chaque objet (ensemble) E a une base constituée de ses singletons : ({x})xE, suivant la bijection canonique (℘(F))E ⥬ ℘(E×F).
Donc, les coproduits dans cette catégorie sont donnés par les unions disjointes d'objets (qui opèrent comme des produits sur les ensembles de parties sur lesquels ils agissent). Ainsi, un coproduit d'ensembles deux à deux disjoints Ei est donné par leur union, avec les morphismes 𝛿Ei de chaque Ei vers lui.
Par symétrie de dualité, cette union disjointe sert aussi de produit.
Les œufs de cette action sont les ({x}, {x}) pour tout x. Un choix standard de singleton est donné par les notations * = {•}. Ensuite, les images directes et inverses peuvent être ré-exprimées en termes de composition: ∀RE×F, ∀AE, ∀BF,

*×(RA) = (*×A);R
(RB)×* = R;(B×*)

Par ces action et co-action, les morphismes dans cette catégorie se comportent comme une troisième forme de présentation des correspondances de Galois. En effet par associativité de la composition,

(*×A);R;(B×*) = ∅ ⇔ AR(B) = ∅ ⇔ BR(A) = ∅
(∁FR, ∁ER) ∈ Gal(℘(E), ℘(F))
(R, ∁ER⚬∁F) ∈ Gal+(℘(E), ℘(F))

Réexprimer les propriétés des relations

Chaque côté (forme curryfiée) de la composition des relations, se comporte de manière similaire aux images directes, qu'on peut considérer comme la constituant: ∀grR,S,T,

RSR;TS;T
RST;RT;S
(RS);T = R;TS;T
T;(RS) = T;RT;S

et pour toute famille de graphes Ri indexée par I et tout graphe T,

T;iI Ri = iI T;Ri
TiI Ri = iI TRi

La réflexivité (𝛿ER) d'une relation R sur un ensemble E, implique

SE×F, SR;S
SF×E, SS;R

La transitivité de R peut s'écrire R;RR.
Ainsi si R est un préordre alors R;R = R mais la réciproque n'est pas toujours vraie.

Préordres engendrés

Le rôle des ensembles de transformations de E comme définissant des conditions de stabilité sur les parties AE, reflété par la correspondence de Galois (End, Sub)∈ Gal(℘(℘(E)), ℘(EE)) introduite en 3.4, équivaut à celui des relations uniques RE2 (structures non fonctionnelles nommées par un seul symbole de fonction) dans la correspondence de Galois (Po, Sub)∈ Gal(℘(℘(E)), ℘(E2)) définie comme reliant tout AE à (x,y)∈E2 par (xAyA):

A ∈ SubR ERAA ⇔ (∀(x,y)∈R, xAyA) ⇔ ∁E A ∈ SubtR E

En effet tout ensemble de transformations peut être remplacé par l'union de leurs graphes ; inversement, tout (x,y)∈E2 peut être remplacé par

Ez ↦ (z=x ? y : z).

Ainsi l'ensemble Im Po des éléments clos de ℘(E2) est l'ensemble des préordres de E. En effet, pour tout ensemble K et tout GK×E,

x,yE, (x,y)∈Po(G[K]) ⇔ (∀zK, zGxzGy) ⇔ G(x)⊂G(y)

qui, d'après 2.9, donne tous les préordres sur E (intersections des préimages de l'ordre naturel sur {0,1}).
L'ordre d'inclusion sur tout S⊂℘(E) apparaît ainsi avec {(A,x)∈S×E|xA}. A savoir, ∈ définit un pré-plongement de (E,Po(S)) vers (℘(S),⊂).

La clôture Po(SubRE) de tout RE2 est appelée le préordre sur E engendré par R ; on le notera ⌈R⌉.

Parties stables engendrées

Lemme. Toute union de parties R-stables est R-stable.
(Cela ne se généralise pas aux structures d'autres arités).

Première preuve. (∀iI, RAiAi) ⇒ RiI Ai = iI RAiiI Ai
Deuxième preuve. Utiliser A ∈ SubR E ⇔ ∁E A ∈ SubtR E et la propriété similaire avec les intersections.∎

Proposition.AE, 〈AR = ⌈RA.

Preuve. D'abord, lorsque A est un singleton {x}, les deux définitions coïncident :

yE, xRy ⇔ (∀A∈SubRE, xAyA) ⇔ y∈〈{x}〉R

Puis, ⌈RA = xA 〈{x}〉R ⊂ 〈AR car A ↦ 〈AR est monotone.
On conclut ⌈RA ∈ SubR E par le lemme ci-dessus.∎

D'après la fin de 3.3 on obtient ∀AE, 〈AR = ARAR.
Par la fidélité de l'action, on peut aussi l'écrire

R⌉ = 𝛿ER⚬⌈R

Une conséquence facile de ce qui précède est que pour tout ensembles K, E et tout GK×E et RE2, ⌈R⌉⚬G est le plus petit SK×E tel que GRSS, et c'est un cas d'égalité (GRS = S).

Clôture transitive

Pour tout RE2, le plus petit TE2 transitif tel que RT (qui existe comme la transitivité est préservée par les intersections), appelé clôture transitive de R, est

T = R⚬⌈R⌉ = ⌈R⌉⚬R.

Preuve. Par hypothèse, RT et RTTTT, donc ⌈R⌉⚬RT par le résultat ci-dessus (⌈R⌉⚬R est le plus petit T tel que RRTT).
Puis, ⌈R⌉⚬R satisfait les deux conditions pour lesquelles T est le plus petit : R ⊂ ⌈R⌉⚬R, et la transitivité :

R⚬⌈R⌉ ⊂ ⌈R⌉ = ⌈R⌉⚬⌈R⌉ ∴ ⌈R⌉⚬R⚬⌈R⌉⚬R ⊂ ⌈R⌉⚬⌈R⌉⚬R = ⌈R⌉⚬R

Donc T = ⌈R⌉⚬R. Par dualité, T = R⚬⌈R⌉.∎

Relations bien fondées

Une relation RE2 est dite bien fondée si ∀AE, ARAA = ∅.
Cela ne dépend pas de E, et implique que tout SR est également bien fondé.
Toute relation bien fondée est irréflexive : ∀x,¬{x}⊂R{x}.

Proposition. La fermeture transitive T d'une relation bien fondée R est bien fondée.

Preuve. Si RE2 est bien fondée, T = RP et P = 𝛿ET (à savoir, P=⌈R⌉), alors T est bien fondée:

AE, ATAPA = ATA = RPA = ∅ ∎

Note (exercice possible) : si R est bien fondée alors en fait !P, P = 𝛿ERP.

Proposition. Si R est bien fondé alors ⌈R⌉ est un ordre, dont l'ordre strict coïncide avec la clôture transitive de R.

Preuve. La clôture transitive T de R, étant à la fois transitive et irréflexive, est un ordre strict, et ⌈R⌉ = 𝛿ET.∎
(L'antisymétrie d'un R bien fondé peut aussi être déduite par ∀x,y,¬{x,y}⊂R{x,y})

Bon ordre

Une relation RE2 est appelée un bon ordre strict sur E si

AE, A = ∅ ∨ ∃!:A\(RA)

Il est facile de voir que tout bon ordre strict est un ordre total strict bien fondé ; inversement, tout RE2 bien fondé dont le complément ∁E2 R est antisymétrique, est un bon ordre strict sur E.
Etant donné que l'ordre total correspondant ≤ est ∁E2 tR, la condition pour qu'une relation ≤ soit un bon ordre, c'est-à-dire un ordre total dont la version stricte est un bon ordre strict sur E, s'écrit

AE, A = ∅ ∨ ∃!xA, A ⊂ ≤(x)

ou de manière équivalente : il est antisymétrique et ∀AE, A = ∅ ∨ ∃xA, A ⊂ ≤(x).

Minimum et maximum

Dans tout ensemble ordonné (E,≤), un xE est appelé un minorant (resp. majorant) d'une partie AE si A ⊂ ≤(x) (resp. A ⊂ ≤(x)). Si de plus xA, il est alors appelé un minimum ou plus petit élément, (resp. maximum ou plus grand élément) de A, que nous noterons x :min A (resp. x :max A). Ces concepts ne dépendent que de l'ensemble A ordonné par restriction de ≤, ignorant le reste de E et ≤.
Par antisymétrie de ≤, ces relations sont fonctionnelles de ℘(E) vers E, de sorte qu'elles sont généralement notées comme fonctions min (le plus petit élément) et max (le plus grand élément) : ∀AE, ∀xE,

x :min A ⇔ (xAA ⊂ ≤(x)) ⇔ (A∈ Dom min ∧ x = min A)
x :max A ⇔ (xAA ⊂ ≤(x)) ⇔ (A∈ Dom max ∧ x = max A)

La fonction successeur

Dans tout ensemble ordonné (E,≤) d'ordre strict <, le successeur est la relation fonctionnelle S sur E définie par ∀x,yE,

xSyy :min <(x) ⇔ ≤(y) = <(x)

Cette dernière équivalence est facile à vérifier.
Si l'ordre est total alors S est injectif et sa définition est symétrique en ce sens que

xSyx :max <(y) ⇔ ≤(x) = <(y)

Si c'est un bon ordre alors ∀xE, x ∉ Dom S ⇔ <(x) = ∅ ⇔ x :max E.
Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles
3. Algèbre
4. Arithmetic and first-order foundations
4.1. Termes algébriques

5. Second-order foundations
6. Foundations of Geometry

Other languages:
EN : 3.12. Composition of relations