Composition des relations

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 = {(x₀,y₁) | (x,y)∈R×S ∧ x₁=y₀}
∀R⊂E×F, ∀S⊂F×G, R;S = {(x,z)∈E×G | ∃y∈F, xRy ∧ ySz}
= ∐_x∈E S^⋆R⃗(x)

Cela étend la composition des fonctions présentées comme relations fonctionnelles, avec les mêmes éléments neutres (1_E = 𝛿_E = Gr Id_E).
(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 ∀y∈F, xRy ⇒ ySz, 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 (_⋆): ∀R⊂E×F, ∀S⊂F×G,

∀A⊂E, (S⚬R)^⋆A = S^⋆(R^⋆A)
∀B⊂G, (R;S)_⋆B = R_⋆(S_⋆B)

Pour cette action, chaque objet (ensemble) E a une base constituée de ses singletons : ({x})_x∈E, 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 E_i est donné par leur union, avec les morphismes 𝛿_{E_i} de chaque E_i 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: ∀R⊂E×F, ∀A⊂E, ∀B⊂F,

＊×(R^⋆A) = (＊×A);R
(R_⋆B)×＊ = 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×＊) = ∅ ⇔ A ∩ R_⋆(B) = ∅ ⇔ B ∩ R^⋆(A) = ∅
(∁_F⚬R^⋆, ∁_E⚬R_⋆) ∈ Gal(℘(E), ℘(F))
(R^⋆, ∁_E⚬R_⋆⚬∁_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,

R⊂S ⇒ R;T ⊂ S;T
R⊂S ⇒ T;R ⊂ T;S
(R∪S);T = R;T ∪ S;T
T;(R∪S) = T;R ∪ T;S

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

T;⋃_i∈I R_i = ⋃_i∈I T;R_i
T⚬⋃_i∈I R_i = ⋃_i∈I T⚬R_i

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

∀S⊂E×F, S ⊂ R;S
∀S⊂F×E, S ⊂ S;R

La transitivité de R peut s'écrire R;R ⊂ R.
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 A⊂E, reflété par la correspondence de Galois (End, Sub)∈ Gal(℘(℘(E)), ℘(E^E)) introduite en 3.4, équivaut à celui des relations uniques R ⊂ E² (structures non fonctionnelles nommées par un seul symbole de fonction) dans la correspondence de Galois (Po, Sub)∈ Gal(℘(℘(E)), ℘(E²)) définie comme reliant tout A⊂E à (x,y)∈E² par (x∈A ⇒ y∈A):

A ∈ Sub_R E ⇔ R^⋆A ⊂ A ⇔ (∀(x,y)∈R, x∈A ⇒ y∈A) ⇔ ∁_E A ∈ Sub_^tR E

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

E ∋ z ↦ (z=x ? y : z).

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

∀x,y∈E, (x,y)∈Po(G⃗[K]) ⇔ (∀z∈K, zGx ⇒ zGy) ⇔ 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|x∈A}. A savoir, ∈⃗ définit un pré-plongement de (E,Po(S)) vers (℘(S),⊂).

La clôture Po(Sub_RE) de tout R ⊂ E² 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. (∀i∈I, R^⋆A_i ⊂ A_i) ⇒ R^⋆⋃_i∈I A_i = ⋃_i∈I R^⋆A_i ⊂ ⋃_i∈I A_i ∎
Deuxième preuve. Utiliser A ∈ Sub_R E ⇔ ∁_E A ∈ Sub_^tR E et la propriété similaire avec les intersections.∎

Proposition. ∀A⊂E, 〈A〉_R = ⌈R⌉^⋆A.

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

∀y∈E, x⌈R⌉y ⇔ (∀A∈Sub_RE, x∈A ⇒ y∈A) ⇔ y∈〈{x}〉_R

Puis, ⌈R⌉^⋆A = ⋃_x∈A 〈{x}〉_R ⊂ 〈A〉_R car A ↦ 〈A〉 _R est monotone.
On conclut ⌈R⌉^⋆A ∈ Sub_R E par le lemme ci-dessus.∎

D'après la fin de 3.3 on obtient ∀A⊂E, 〈A〉_R = A ∪ R^⋆〈A〉_R.
Par la fidélité de l'action, on peut aussi l'écrire

⌈R⌉ = 𝛿_E ∪ R⚬⌈R⌉

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

Clôture transitive

Pour tout R⊂E², le plus petit T⊂E² transitif tel que R⊂T (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, R ⊂ T et R⚬T ⊂ T⚬T ⊂ T, donc ⌈R⌉⚬R ⊂ T par le résultat ci-dessus (⌈R⌉⚬R est le plus petit T tel que R ∪ R⚬T ⊂ T).
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 R ⊂ E² est dite bien fondée si ∀A⊂E, A ⊂ R^⋆A ⇒ A = ∅.
Cela ne dépend pas de E, et implique que tout S ⊂ R 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 R ⊂ E² est bien fondée, T = R⚬P et P = 𝛿_E ∪ T (à savoir, P=⌈R⌉), alors T est bien fondée:

∀A⊂E, A ⊂ T^⋆A ⇒ P^⋆A = A∪ T^⋆A = R^⋆P^⋆A = ∅ ∎

Note : le bon fondement de R implique l'unicité de P tel que P = 𝛿_E ∪ R⚬P.
Cela se voit en considérant A = {x∈E | P⃖(x) ≠ P'⃖(x)} où P et P' ont cette propriété ; c'est un premier exemple de définition par induction bien-fondée, concept qui sera développé plus tard.

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⌉ = 𝛿_E ∪ T.∎
(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 R ⊂ E² est appelée un bon ordre strict sur E si

∀A⊂E, A = ∅ ∨ ∃!:A\(R^⋆A)

Il est facile de voir que tout bon ordre strict est un ordre total strict bien fondé ; inversement, tout R ⊂ E² bien fondé dont le complément ∁_E² R est antisymétrique, est un bon ordre strict sur E.
Etant donné que l'ordre total correspondant ≤ est ∁_E² ^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

∀A⊂E, A = ∅ ∨ ∃!x∈A, A ⊂ ≤⃗(x)

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

Minimum et maximum

Dans tout ensemble ordonné (E,≤), un x∈E est appelé un minorant (resp. majorant) d'une partie A⊂E si A ⊂ ≤⃗(x) (resp. A ⊂ ≤⃖(x)). Si de plus x∈A, 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) : ∀A⊂E, ∀x∈E,

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