2.11. Correspondance de Galois

L'ensemble des points fixes d'une fonction f s'écrit

Fix f ={xDom f | f(x)=x} ⊂ Im f
Alors,
Im f ⊂ Fix g ⇔ ((Im fDom g)∧(gf=f))
Im f= Fix f ⇔ ((Im f ⊂ Dom f)∧(ff=f)) : une telle fonction f est dite idempotente.

Définition. Pour tous ensembles ordonnés E, F, notant F l'ensemble F avec l'ordre transposé, l'ensemble des correspondances de Galois (décroissantes) entre E et F, et celui des correspondances de Galois croissantes de E vers F, se définissent par
Gal(E,F) = {(⊥,) ∈ FE×EF|∀xE, ∀yF, xE(y) ⇔ yF ⊥(x)} = tGal(F,E)
Gal+(E,F) = {(u,v) ∈ FE×EF|∀xE, ∀yF, xE v(y) ⇔ u(x) ≤F y} = Gal(E,F)

Exemple fondamental. Toute relation RX×Y definit un (⊥,) ∈ Gal(℘(X),℘(Y)) par
AX, ⊥(A) ={yY |∀xA, x R y}= xAR(x)
BY, (B) ={xX |∀yB, x R y}={xX | BR(x)}
Puis, ⊥(∅)=Y and ⊤(∅)=X

Preuve :
AX, ∀BFA ⊂ ⊤(B) ⇔ (∀xA, ∀yB, x R y) ⇔ B ⊂ ⊥(A).∎
Nous montrerons plus loin que c'est une bijection : Gal(℘(X),℘(Y)) ≅ ℘(X×Y).

Lemme. ∀⊥ ∈ FE, !EF,(⊥,) ∈ Gal(E,F).
Preuve: ∀EF, (⊥,) ∈ Gal(E,F) ⇔ E =⊥*F, or E est injective.∎

Propriétés. Pour tous (⊥,) ∈ Gal(E,F), les clôtures Cl =০⊥ ∈ EE et Cl′=⊥০FF satisfont
1) Cl et Cl′ sont extensive.
2) ⊥ et sont décroissantes
3) Cl et Cl′ sont croissantes
4) ⊥০০⊥ = ⊥, et de même ০⊥০ =
5) Im =Im Cl =Fix Cl, appelé l'ensemble des éléments clos de E
6) ClCl = Cl
7) (⊥ strictement décroissante) ⇔ Inj⊥ ⇔ Cl = IdE ⇔ Im =E
8) ∀x,x′ ∈ E, ⊥(x) ≤ ⊥(x′) ⇔ (Im(x) ⊂ ≤(x′)).
9) Notant K=Im, ০⊥|K= IdK donc ⊥|K est strictement décroissante et ⊥|K−1 =|Im.

Preuves:
1) ⊥(x) ≤ ⊥(x)⇒x(⊥(x)).
1) ⇒2) ∀x,yE, xy(⊥(y))⇒⊥(y) ≤ ⊥(x).
1)∧2) ⇒4) IdECl⇒⊥০Cl ≤ ⊥ ≤ Cl′০⊥ = ⊥০০⊥.
4)⇒5) Cl =০⊥⇒ Im Cl ⊂ Im⊤ ;
Cl =ImFixClImCl.
2)⇒3) et 4)⇒6) sont évidents.
7) (Inj⊥∧⊥০Cl =⊥) ⇔ Cl =IdE ⇔ (Im =ECl =);
Cl
=IdE ⇒ ⊥ strictement décroissante ⇒ Inj⊥.
8) ⊥(x) ≤ ⊥(x′) ⇔ (∀yF, x(y) ⇒ x′≤(y)).
9) K= Fix(০⊥) ⇒ ০⊥০IdK=IdK.
Autre preuve : (⊥|K,) ∈ Gal(K,F) avec surjective.
Dans |Im০⊥|K=IdK les rôles de et ⊥ sont symétriques. ∎

Remark. Les propriétés 1) et 2) impliquent réciproquement que (⊥,) ∈ Gal(E,F).
Preuves: ∀xE, ∀yF, x(y) ⇒ y ≤ ⊥((y)) ≤ ⊥(x).∎
Des analogues des propriétés ci-dessus pour les correspondances de Galois croissantes sont obtenus en inversant l'ordre dans F: si (u,v) ∈ Gal+(E,F) alors u et v sont croissantes, vu est extensive et uvIdF.

Clôture. Une clôture d'un ensemble ordonné E est une fonction fEE aux propriétés équivalentes:
1) Il existe un ensemble F et un (u,v) ∈ Gal(E,F) ou Gal+(E,F) tel que vu=f
2) f est croissante, idempotente et extensive
3) ∀xE,∀y∈ Im f, xy ⇔ f(x) ≤ y, autrement dit (f, IdK) ∈ Gal+(E,K) où K=Im f.

Preuve d'équivalence :

3)⇒1) ⇒2);
pour 2) ⇒3), ∀xE,∀yK, xf(x) ≤ yxyf(x) ≤ f(y) = y. ∎

Notes:

Pour aller plus loin sur les correspondances de Galois

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