3.2. Notion d'algèbre

Algèbre. Étant donné un langage algébrique L, une L-algèbre est la donnée (E,φ) d'un ensemble E et d'une L-structure algébrique φ : LEE, somme d'une famille d'interprétations de chaque symbole sL comme opération ⃗φ(s)∈OpE(ns).
Là encore, on considèrera habituellement une classe de L-algèbres avec un seul choix de structure algébrique sur chaque ensemble:

sE : EnsE
φE = ∐sL sE : LEE

Ce serait ainsi si les sE étaient les restrictions d'un même opérateur ns-aire à chaque E, mais ce cas ne permettrait pas l'interpréter des symboles de constantes r et s dans des algèbres E et F avec rE=sE mais rFsF.
Ceux-ci forment une catégorie concrète avec le concept de morphisme suivant.

Morphismes d'algèbres. Pour toutes L-algèbres E, F,

MorL(E,F) = {fFE | ∀(s,x)∈LE, sF(fx) = f(sE(x))} = {fFE| φFfL = f০φE}.

Quand cL est une constante (i.e. nc =0), cette condition sur f dit que f(cE)=cF.

Ces catégories peuvent être vues comme catégories de systèmes relationnels particuliers, comme suit.

Soit le langage relationnel L' copie de L où la copie s'L' de chaque sL est d'arité augmentée ns' = ns+1, de sorte que
L'E ≡ ∐sL Ens×E ≡ (LEE ≡ {(s,x,y) | sLxEnsyE}.
Chaque opération ns-aire sE définit une relation ns'-aire s'EGr sE. Elles s'assemblent en une L'-structure
E = Gr φE ≡ ∐sL s'E.
Les conditions résultantes pour qu'un fFE soit un morphisme sont équivalentes :
(∀(x,y)∈E, (fL(x),f(y))∈F) ⇔ (∀xLE, φF(fL(x))= fE(x))).

Sous-algèbres. Une partie AE d'une L-algèbre E est dite stable par L ou une L-sous-algèbre de E si φE[LA] ⊂ A. C'est aussi une L-algèbre, de structure φA restriction de φE à LA. L'ensemble des L-sous-algèbres de E est noté SubL E = {AE | φE[LA]⊂A}.

Si une formule de la forme (∀(variables), formule sans quantificateur) est vraie dans E, alors elle est vraie dans chaque A∈SubLE.

Images d'algèbres. Pour deux L-algèbres E,F, ∀f ∈MorL(E,F), Im f ∈ SubLF.

Preuve : φF[L⋆Im f] = φF[Im fL] = Im (f০φE) ⊂ Im f

Généralisons ces concepts aux catégories de L'-systèmes relationnels (E,E) dont la structure E ⊂ (LEE n'a plus besoin d'être fonctionnelle:

Parties stables. Le concept de stabilité d'une partie A d'un L'-système E généralise celui de sous-algèbre :

A ∈ SubL E ⇔ (E*(LA) ⊂A) ⇔ (∀(s,x,y)∈E, Im xAyA).

On a E ∈ SubL E. La stabilité n'est plus préservée par les images directes de morphismes, mais est préservée par les préimages:

Préimages de parties stables.f∈MorL(E,F), ∀B∈SubLF, f *(B) ∈ SubL E.

Preuve. Soit A=f *B.
Pour les L-algèbres, ∀(s,x)∈LA, fxBnsf(sE(x)) = sF(fx) ∈BsE(x)∈A.
Pour les L'-systèmes, ∀(x,y)∈E, (fL(x),f(y))∈F∴ (xLAfL(x)∈LBf(y)∈ByA).∎

Proposition. Pour tout L'-système E et toute L-algèbre F,

f,g∈MorL(E,F), {xE|f(x)=g(x)}∈ SubLE.

Preuve : ∀(s,x,y)∈E, fx=gxf(y) = sF(fx) = g(y). ∎

Intersections de parties stables.X ⊂ SubLE,X ∈ SubL E où ∩X {xE|∀BX, xB}.

Preuve: ∀(x,y)∈E, xL⋆∩X ⇒ (∀BX, xLByB) ⇒ y∈∩X. ∎

Autre méthode: E*(L⋆∩X) = E*(∩BX LB) ⊂∩BX E*(LB) ⊂∩X.

Sous-algèbre engendrée par une partie.AE, on note 〈AL,E or simply 〈AL, la plus petite partie L-stable de E incluant A (appelée L-sous-algèbre de E engendrée par A si E est une algèbre):

AL= ∩{B∈SubLE | AB} = {xE | ∀B∈SubLE, ABxB} ∈ SubLE.

Pour E et L fixés, cette fonction de A est une clôture d'image SubLE.
On dit que A engendre E ou est une partie génératrice de E si 〈AL=E.

Sous-algèbre minimale. Pour tout L'-système E, sa partie stable minimale (ou sous-algèbre minimale pour une L-algèbre) se définit par
MinLE = 〈∅〉L,E = ∩SubLE ∈ SubLE.

Une L-algèbre E est minimale is E = MinL E, ou de façon équivalente SubLE = {E}.

Proposition. Pour tout L'-système E, ∀A∈SubLE, Preuve: MinLE ⊂ MinLA car SubL A ⊂ SubL E;
MinL A ⊂ MinL E car ∀B∈SubLE, AB ∈ SubLA. ∎

Parmi les parties de E, les autres L'-systèmes minimaux sont inclus dans MinL E mais ne sont pas stables.
La partie stable engendrée par A est minimale pour le langage étendu par A vu comme ensemble de constantes: 〈AL,E= MinLA E.

Algèbre injective ou surjective. Une L-algèbre (EE) sera dite injective si φE est injective, et surjective si Im φE = E.

Proposition. Pour toutes L-algèbres E, F,

  1. AE, Im φEAA∈SubLE.
  2. Toute L-algèbre minimale est surjective.
  3. MinLE = φE[L⋆MinLE] ⊂ Im φE
  4. AE, ⋃xA〈{x}〉L ⊂ 〈AL = A∪φE[L⋆〈AL] ⊂ A∪Im φE.
  5. f ∈MorL(E,F), f [MinLE] = MinLF ∧ ∀AE, f [〈AL] = 〈f [A]〉L
Preuves:
  1. φE[LA] ⊂ Im φEAA∈SubLE
  2. Im φE ∈ SubLE
  3. MinLE est surjective
  4. A∪φE[L⋆〈AL] ∈ SubLAL
  5. B ∈ SubLF, f *(B)∈SubL E ∴ MinLEf*(B) ∴ f [MinLE]⊂B.∎

Lemme d'injectivité. Si E est une algèbre surjective et F une algèbre injective alors ∀f ∈MorL(E,F),

  1. A= {xE | ∀yE, f(x) = f(y) ⇒ x=y} ∈ SubLE.
  2. Pour chaque quantificateur d'unicité Q (∃! ou !), B = {yF | QxE, y = f(x)} ∈ SubLF
C'est essentiellement la même chose mais écrivons des preuves séparées:
  1. ∀(s,x)∈LA, ∀yE,
    f(sE(x)) = f(y) ⇒ (∃(t,z)∈φE(y), sF(fx) = f(sE(x)) = f(y) = f(tE(z)) = tF(fz) ∴ (s=tfx=fz) ∴ x=z)sE(x)=y.
  2. Comme φF est injective, ∀y∈φF[LB], ∃!: φF(y) ⊂ LBQzLE, φF(fL(z)) = y.
    Comme φFfL = f০φE et φE est surjective, on conclut QxE, y = f(x). ∎

Théorème de Schröder–Bernstein. S'il existe des injections f: EF et g: FE alors il existe une bijection entre E et F.

Preuve : remplaçant F par l'ensemble bijectivement lié Im g, simplifie le problème au cas FE.
Alors une bijection de E vers F se définit par x ↦ (x∈〈E\F{f} ? f(x) : x).∎

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory