4.2. Systèmes quotient

Quotients de systèmes relationnels

Etant donné un langage relationnel L et deux L-systèmes E et F, un quotient de E vers F est un morphisme surjectif f : E↠F tel que Lf[E] = F. On dit aussi que le système F est un quotient de E par ∼f.
Cette condition définit F par E et f, comme la plus petite L-structure sur F telle que f ∈ MorL(E, F).

Pour toute toute relation d'équivalence R sur E, l'ensemble quotient E/R reçoit la L-structure E/R définie par LR⃗[E], faisant de (R⃗) un quotient de E vers E/R.
Alors pour tout h : E → X,

R ⊂ ∼h ⇒ (h ∈ MorL(E,X) ⇔ h/R ∈ MorL(E/R,X)).

Puis si L est un langage algébrique, la condition pour qu'un f : E↠F entre L-systèmes soit un quotient, s'écrit

{(Lf(x),f(y)) | (x,y) ∈ E} = F.

Cela implique∀B⊂F, B ∈ SubLF ⇔ f *(B) ∈ SubLE.
Tout morphisme d'un système sériel vers une algèbre partielle est un quotient vers son image, qui est une algèbre stable.

Quotients dans les catégories concrètes

Le concept de quotient a une définition équivalente exprimable pour toute catégorie concrète C, similaire au concept de plongement en échangeant les côtés. Cela peut s'expliquer en étant le même concept que celui de plongement dans la catégorie opposée, le caractère concret de la catégorie étant réexprimé comme un lien avec la catégorie des ensembles, indépendamment des détails de la catégorie des ensembles, ainsi remplaçable par toute autre catégorie, à savoir la catégorie opposée à la catégorie des ensembles.

Ainsi, un quotient de E vers F dans C est un morphisme surjectif f : E↠F tel que, ∀CX, de façon équivalente

Mor(F,X) = {g∈XF | g⚬f ∈ Mor(E,X)}
Mor(F,X) = {h/f | h ∈ Mor(E,X) ∧ ∼f ⊂ ∼h}
{h ∈ Mor(E,X) | ∼f ⊂ ∼h} = {g⚬f | g∈Mor(F,X)}

Toute rétraction est un quotient.

Congruences

Etant donné un langage algébrique L, une congruence sur un L-système E est une relation d'équivalence R sur E telle que, de façon équivalente Preuve d'équivalence. Ainsi, le quotient de toute algèbre ou autre système sériel par une congruence, est une algèbre. Dans ce cas, une congruence peut être essentiellement décrite comme une relation binaire satisfaisant les axiomes de l'égalité.

Quotients de modules

Les quotients de modules ne sont pas toujours des modules. Mais pour tout langage algébrique L, tout L-système E, et tout L-système équationnel (K, b), où b : V→K, V est sans structure et ACV est vérifié, si E est un b-module alors son quotient par toute congruence est aussi un b-module.
Preuve. Cette preuve nécessite seulement que f soit un morphisme surjectif, pas précisément un quotient. En pratique, cela ne sera utilisé qu'avec des quotients. En effet, f est un quotient pour la plus petite structure de F qui fait de f un morphisme ; de plus grandes structures préservent l'existence ; la preuve d'unicité utilise que F reste une algèbre partielle, mais quand E est sériel (comme il arrive souvent), cette hypothèse implique que f est de toute façon un quotient.
En fait, l'hypothèse ACV n'est pas nécessaire, car les systèmes équationnels infinis seront considérés comme équivalents à des ensembles de systèmes finis, où le choix fini s'applique.

Intersections de congruences

Sur tout L-système E, toute intersection de relations d'équivalence est une relation d'équivalence ; et toute intersection de congruences est une congruence.
Cela peut être vu comme un cas d'intersection de parties stables, comme les relations d'équivalence sont les relations stables par une structure, et de même pour les congruences. Mais voici un autre point de vue sur cela:

Soit ∀i∈I, fi ∈ MorL(E,Fi), P = ∏i∈I Fi et g = ⊓i∈I fi ∈ MorL(E, P). Alors

∼g = ⋂i∈I ∼fi.

Si tous les Fi sont des algèbres partielles alors P est aussi une algèbre partielle, ce qui explique que ∼g est une congruence.
Soit G = Im g ⊂ P. Comme tout morphisme, g sera un quotient vers son image G si E est sériel et P est une algèbre partielle, mais pas nécessairement sinon.
Soit ∀i∈I, hi = πi|G ∈ MorL(G,Fi). Alors fi = hi⚬g. Comme pour tout composé de morphismes, si fi est un quotient alors hi est aussi un quotient.

Congruence minimale

La congruence minimale sur tout L-système E est l'intersection de toutes ses congruences. Notons-la ≃E, ou simplement ≃ lorsque E est donné par le contexte. C'est l'égalité si et seulement si E est une algèbre partielle.
Appelons condensé de E son quotient par sa congruence minimale, et πE la surjection naturelle dessus:

⤓E = E/≃
πE = ≃⃗E : E ↠ ⤓E

(⤓E, πE) est initial dans la categorie des (X,f) où X est une L-algèbre partielle, f ∈ MorL(E,X), et

Mor((X,f),(Y,g)) = {h ∈ MorL(X,Y) | h ⚬ f = g}
Mor((⤓E, πE),(Y,g)) = {g/πE}

La congruence sur E engendrée par toute relation d'équivalence R est la préimage de ≃E/R par R⃗.

Dans la categorie des algèbres partielles, le coproduit est donné par le condensé de l'union disjointe.

Condensé de systèmes injectifs

Pour tout L-système injectif (E, tGr ψE), sa congruence minimale ≃E est 〈𝛿E〉L, et ⤓E est injective.

Preuve:

La formule R = 𝛿E ∪ F*(LR) est équivalente à

R⃗ ∈ MorL(E,℘(E)) ∧ ∀x∈E\Dom ψE, R⃗(x) = {x}
où φ℘(E)(s,u) = {x∈OD | σ(x)=s ∧ lx∈∏u}

ce qui détermine R lorsque E est un brouillon.
La formule (*) exprime R ⊂ 𝛿E ∪ F*(LR), et est équivalente à la conjonction de
  1. ∀(x,y)∈R, x ∉ Dom ψE ⇒ x = y
  2. ∀(x,y)∈Dom ψE, xRy ⇒ (x ∼σ y ∧ Im(lx⊓ly) ⊂ R).
Si R est une relation d'équivalence, 2. dit que la structure de E/R est injective, tandis que 1. signifie qu'il a les mêmes variables que E. Ainsi dans un brouillon, les relations d'équivalence satisfaisant (*) sont celles des morphismes préservant les variables vers un autre brouillon.
Ainsi, la congruence minimale d'un brouillon est sa seule congruence par laquelle le quotient est un brouillon (fonctionnel) de mêmes variables ; c'est la préimage de = par tout morphisme préservant les variables vers un brouillon fonctionnel.

4.3

Trajectoires par des ensembles de transformations

Pour tout ensemble de transformations L ⊂ EE, vu comme ensemble de symboles de fonctions interprété dans E,

∀x∈E, 〈{x}〉L = {f(x)|f∈〈L〉{Id,⚬}}
∀X⊂E, 〈X〉L = ⋃f∈〈L〉{Id,⚬} f[X] = ⋃x∈X 〈{x}〉L

Comme sera formalisé plus tard, la raison est que les deux ont la même signification : l'ensemble de tous les composés de tout nombre de fonctions dans L, appliqué à tout x∈X. Mais voici une simple preuve, notant A=〈X〉L, M=〈L〉{Id,⚬} et K={f(x) | (f,x)∈M×X}:
Preuve de A ⊂ K
IdE∈M ∴ X⊂K
∀g∈L, ∀y∈K, ∃(f,x)∈M×X, y=f(x) ∧ g⚬f∈M ∴ g(y) = g⚬f(x)∈K
K ∈ SubLE
Preuve de K ⊂ A
L ⊂ {f∈EE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,⚬}EE
M ⊂ End{A}E
∀f∈M, X ⊂ A ∈ Sub{f}E ∴ f[X] ⊂ A. ∎

4.8

Lemme d'injectivité.

Si E est une L-algèbre partielle surjective et F un L-système injectif alors ∀f ∈MorL(E,F),
  1. A = {x∈E | ∀y∈E, f(x) = f(y) ⇒ x=y} ∈ SubLE.
  2. B = {y∈F | !: f •(y)} ∈ SubLF
    Donc si plus précisément E, F sont des algèbres, {y∈F | ∃!: f •(y)} ∈ SubLF.
C'est essentiellement la même chose mais écrivons des preuves séparées.
La condition f ∈MorL(E,F) se lit Im f ⊂ Dom ψF ∧ Lf|Dom φE = ψF⚬f⚬φE.
  1. ∀x∈LA⋂Dom φE, ∀y∈E, ∃z∈φE•(y),
    f(φE(x)) = f(y) ⇒ Lf(x) = ψF(f(φE(x))) = ψF(f(y)) = ψF(f(φE(z))) = Lf(z)
    ⇒ x = z ⇒ φE(x) = y.
  2. ∀y∈F*(LB), ψF(y) ∈ LB ∴ (!z∈Dom φE, ψF(y) = Lf(z) = ψF(f(φE(z))))
    ∴ !x∈Im φE=E, y = f(x).∎

4.10

Reconstruire les structures dans une catégorie concrète

Dans une petite catégorie concrète, les familles de relations préservées sont précisément toutes les unions possibles de ceux-ci : chaque symbole s de prédicat interprété en relations et préservé dans la catégorie, coïncide avec l'union de ceux ainsi définis pour t parcourant s à travers tous les objets K.

Cependant, la classe des systèmes relationnels obtenue même en donnant ainsi "toutes les structures possibles" aux objets d'une catégorie concrète donnée par ailleurs, comme la topologie, peut encore admettre plus de morphismes que ceux dont on est partis (cette construction se comporte comme une clôture).
Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles
3. Algèbre
4. Arithmétique et fondements du premier ordre
4.1. Termes algébriques
4.2. Systèmes quotient
4.3. Term algebras
4.4. Integers and recursion
4.5. Presburger Arithmetic
4.6. Finiteness and countability
4.7. The Completeness Theorem
4.8. More recursion tools
4.9. Non-standard models of Arithmetic
4.10. Developing theories : definitions
4.11. Constructions
4.A. The Berry paradox
5. Second-order foundations
6. Foundations of Geometry

Other languages:
EN : 4.2. Quotient systems