3. Algèbre

Cette section sur l'algèbre sera principalement (pour environ 3/4) formée de concepts extraits de la littérature existante sur l'algèbre universelle et la théorie des catégories. Cet exposé vise à être relativement court, optimisé et autonome, axé sur les aspects de base relativement peu nombreux qui m'ont semblé pertinents pour fournir un cadre solide aux principaux concepts des fondements des mathématiques, de la géométrie et de la physique. De son côté, la littérature sur le sujet apparait pléthorique avec des choix de formalisation moins efficaces et de nombreux autres concepts moins pertinents pour cet objectif. N'y étant pas érudit (étant découragé par son volume), je ne peux pas vérifier l'originalité des points et astuces que j'ai inventés avec parfois un vocabulaire et des notations originaux.

3.1. Correspondances de Galois

Points fixes, fonctions idempotentes

L'ensemble des points fixes de toute fonction f se définit par

∀Fnc f, Fix f = {x∈ Dom f | f(x) = x} ⊂ Dom f ∩ Im f

Ainsi, ∀Fnc f,g, Im f ⊂ Fix g ⇔ (Im f ⊂ Dom g ∧ g⚬f = f)

Une fonction f est dite idempotente si, de façon équivalente,

Im f ⊂ Dom f ∧ f⚬f = f
Im f = Fix f

Fonctions croissantes, décroissantes, strictement croissantes

Entre deux ensembles ordonnés E et F, une fonction f : E → F sera dite : Strictement croissante implique ∀x,y∈E, x < y ⇔ f(x) < f(y).
Réciproquement si l'ordre de E est total et ∀x,y∈E, x < y ⇒ f(x) < f(y) alors f est strictement croissante.
Toute composée d'une chaine de fonctions croissantes ou décroissantes, est croissante si le nombre de fonctions décroissantes dans la chaine est pair, ou décroissante s'il est impair.
Toute fonction strictement croissante ou strictement décroissante est injective.
Si f ∈ FE et g ∈ EF sont toutes deux croissantes (resp. toutes deux décroissantes) et g⚬f = IdE, alors f est strictement croissante (resp. strictement décroissante).

Ordre entre fonctions, fonctions extensives

Pour tous ensembles E, F où F est ordonné, l'ensemble FE est ordonné comme produit (f ≤ g ⇔ ∀x∈E, f(x) ≤ g(x)).
Alors, ∀f,g∈FE, ∀h∈EG, f ≤ g ⇒ f⚬h ≤ g⚬h, autrement dit f ↦ f⚬h est toujours croissante.
Le cas particulier F = V2 est que h⋆ est croissante de ℘(E) vers ℘(G) pour l'ordre d'inclusion.
Si F et G sont ordonnés et u ∈ GF est croissante (resp. décroissante) alors FE ∋ f ↦ u⚬f ∈ GE est croissante (resp. décroissante).
Dans un ensemble ordonné E, une fonction f ∈ EE est dite extensive si IdE ≤ f, autrement dit ∀x∈E, x ≤ f(x).
La composée de deux fonctions extensives est extensive.

Correspondances de Galois : définition et exemples

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|∀x∈E, ∀y∈F, x ≤E⊤(y) ⇔ y ≤F ⊥(x)} = tGal(F,E)
Gal+(E,F) = {(u,v) ∈ FE×EF|∀x∈E, ∀y∈F, x ≤E v(y) ⇔ u(x) ≤F y} = Gal(E,F−)

Lemme. ∀⊥ ∈ FE, !⊤ ∈ EF, (⊥,⊤) ∈ Gal(E,F).
Preuve: ∀⊤ ∈ EF, (⊥,⊤) ∈ Gal(E,F) ⇔ ≤⃖E⚬⊤ = ⊥⋆⚬ ≤⃗F, or ≤⃖E est injective.∎

Correspondances de Galois entre ensembles des parties. Toute relation R ⊂ X×Y definit un (⊥,⊤) ∈ Gal(℘(X),℘(Y)) par

∀A⊂X, ⊥(A) = {y∈Y | ∀x∈A, x R y} = ⋂x∈A R⃗(x)
∀B⊂Y, ⊤(B) = {x∈X | ∀y∈B, x R y} = {x∈X | B ⊂ R⃗(x)}

Puis, ⊥(∅)=Y and ⊤(∅)=X
Preuve : ∀A⊂X, ∀B⊂F,  A ⊂ ⊤(B) ⇔ A×B ⊂ R ⇔ B ⊂ ⊥(A).∎
C'est en fait une bijection : Gal(℘(X),℘(Y)) ⥬ ℘(X×Y). Preuve: Correspondances de Galois croissantes entre ensembles des parties. Toute relation R ⊂ X×Y définit un (u,v) ∈ Gal+(℘(X),℘(Y)) par

∀A⊂X, u(A) = {y∈Y | ∃x∈A, x R y} = ⋃x∈A R⃗(x)
∀B⊂Y, v(B) = {x∈X | R⃗(x) ⊂ B}.

Ainsi, le graphe de toute fonction f : X → Y définit

(A ↦ f[A], B ↦ f⋆(B)) ∈ Gal+(℘(X),℘(Y))

Propriétés des correspondances de Galois

Pour tous (⊥,⊤) ∈ Gal(E,F), les clôtures Cl =⊤⚬⊥ ∈ EE et Cl′=⊥⚬⊤ ∈ FF satisfont
  1. Cl et Cl′ sont extensives.
  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. Cl⚬Cl = 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∈E, ⊥(x) ≤ ⊥(x) ∴ x ≤ ⊤(⊥(x)).
(1. ⇒ 2.) ∀x,y∈E, x ≤ y ≤ ⊤(⊥(y))⇒⊥(y) ≤ ⊥(x).
(1.∧2. ⇒ 4.) IdE ≤ Cl ⇒⊥⚬Cl ≤ ⊥ ≤ Cl′⚬⊥ = ⊥⚬⊤⚬⊥.
(4.⇒5.) Cl = ⊤⚬⊥ ∴ Im Cl ⊂ Im⊤ ;
Cl⚬⊤ = ⊤ ∴ Im ⊤ ⊂ Fix Cl ⊂ Im Cl.
2. ⇒ 3. et 4. ⇒ 6. sont évidents.
(7.) (Inj ⊥ ∧ ⊥⚬Cl = ⊥) ⇔ Cl = IdE ⇔ (Im ⊤ = E ∧ Cl⚬⊤ = ⊤);
Cl = IdE ⇒ ⊥ strictement décroissante⇒ Inj ⊥.
(8.) ⊥(x) ≤ ⊥(x′) ⇔ (∀y∈F, 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. ∎

Remarque. Les propriétés 1. et 2. impliquent réciproquement que (⊥,⊤) ∈ Gal(E,F).

Preuves: ∀x∈E, ∀y∈F, 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, v⚬u est extensive et u⚬v ≤ IdF.

Caractérisation des clôtures

Une clôture d'un ensemble ordonné E est une fonction f ∈ EE telle que, de façon équivalente:
  1. Il existe un ensemble F et un (u,v) ∈ Gal(E,F) ou Gal+(E,F) tel que v⚬u=f
  2. f est croissante, idempotente et extensive
  3. ∀x∈E, ∀y∈ Im f, x ≤ y ⇔ f(x) ≤ y, autrement dit (f, IdK) ∈ Gal+(E,K) où K = Im f.
Preuve d'équivalence :

3. ⇒ 1. ⇒ 2.;
pour 2. ⇒3., ∀x∈E,∀y∈K, x ≤ f(x) ≤ y ⇒ x ≤ y ⇒ f(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
3. Algèbre
3.1. Correspondances de Galois
3.2. Systèmes relationnels et catégories concrètes
3.3. Algèbres
3.4. Morphismes particuliers
3.5. Monoïdes et catégories
3.6. Actions de monoides et de catégories
3.7. Inversibilité et groupes
3.8. Propriétés dans les catégories
3.9. Objets initiaux et finaux
3.10. Produits de systèmes
3.11. Bases
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
EN : 3.1. Galois connections