3.8. Termes algébriques

Ecritures

Le concept de termes algébriques avec un langage purement algébrique L et un ensemble V de symboles de variables (pas de prédicats, de symboles logiques ni de symboles liants), d'abord intuitivement introduit en 1.5), sera formalisé comme systèmes dans un cadre ensembliste. Par commodité, supposons un seul type (la généralisation au cas multi-type est facile), et commençons par une classe plus large de systèmes.
Appelons L-écriture tout L'-système (D,D) où D⊂ (LDD, tel que:

Notons ∀xOD, ΨD(x) = (σ(x), lx) ∈ LD où σ∈LOD et lxDnσ(x).
Le bon fondement a pour formules équivalentes

AOD, (∀xOD, Im lxAVxA) ⇒ A=OD
AD, (VDAD*(LA) ⊂A) ⇒ A = D
AD, VDAD ⇒ ∃xOD\A, Im lxA
AOD, A≠∅ ⇒ ∃xA, A∩ Im lx = ∅

Une écriture close est une écriture sans variable : VD=∅. Donc, ΨD: DLD et SubLD = {D}.
Les variables d'une écriture peuvent se réinterpréter comme constantes: étendant ΨD par IdVD : VDV, forme une (LV)-écriture close.

Sous-écriture et termes

Les écritures n'ont pas de partie stable intéressante (par bon fondement), mais un autre concept de stabilité: une partie AD est une sous-écriture de D (ou une partie co-stable de D) si, notant OA = AOD et ΨA = ΨD|OA, on a (Im ΨALA), i.e. ∀xOA, Im lxA.
En effet, elle reste bien-fondée, comme on peut voir sur la dernière formulation du bon fondement.

Comme avec les parties stables, toute intersection de sous-écritures est une sous-écriture. De plus, toute union de sous-écritures est aussi une sous-écriture (contrairement aux sous-algèbres avec une opération d'arité >1, qui avec des arguments dans différentes sous-algèbres peut donner un résultat échappant à leur union).

La sous-écriture co-engendrée par une partie d'une écriture, est l'intersection de toutes les sous-écritures qui l'incluent. Un terme est une écriture co-engendrée par un unique élément qui est sa racine. Chaque x dans une écriture D définit un terme Tx de racine x, sous-écriture de D co-engendrée par {x}.
Chaque écriture D est ordonnée par xyxTy. C'est évidemment un préordre. Preuve d'antisymétrie (unicité de la racine):
xOD, VDA={yD|xTy} qui est une sous-écriture par transitivité de ≤.
xA ∴ ∃zOD\A, Im lzA.
A∪{z} est une sous-écriture, donc TzA∪{z} par définition de Tz.
zOD\AxTzx=z. Donc x est déterminé par A. ∎
D'autres propriétés de cet ordre seront vues pour les entiers dans 3.6, et dans le cas général avec les relations bien-fondées dans l'étude des correspondances de Galois.

Catégories d'écritures

Comme systèmes relationnels particuliers, les classes de L-écritures forment des catégories concrètes. Entre deux L-écritures D,E,

f ∈MorL(D,E) ⇔ (f[OD]⊂OE ∧ ΨEf|OD= fL০ΨD)

où la condition d'égalité se divise en

σEf|OD = σD
xOD, lf(x)=flx

Une autre catégorie concrète est celle des écritures avec morphismes préservant les variables, où V est fixe et les morphismes f d'une écriture D sont sujettes à f|VD = IdVD. Cela s'exprime de façon équivalente en réinterprétant les variables comme des constantes, comme la catégorie des (LV)-écritures closes.

Inteprétations des écritures dans les algèbres

Pour toute L-écriture D et toute L-algèbre E, une interprétation de D dans E est un morphisme f∈MorL(D,E), c-à-d. f|OD= φEfL০ΨD, aussi exprimable par

xOD, f(x) = σ(x)E(flx)

Toute interprétation vEV de variables dans une algèbre E détermine une interprétation de toute écriture D dans E. Pour simplifier les formulations, restreindre v à VD réduit le problème au cas VD=V.

Théorème. Pour toute L-écriture D avec VD=V et toute L-algebre E, tout vEV est extensible de façon unique en une interprétation de D:
∃!h∈MorL(D,E), h|V = v, de façon équivalente ∃!hEOD, vh ∈MorL(D,E).

L'unicité se déduit du bon fondement : ∀g,h∈MorL(D,E), g|V = v = h|VV⊂ {xD|g(x) = h(x)} ∈ SubLDg=h.
Prouvons maintenant l'existence (utilisant l'opérateur conditionnel).
S = {AD | VA ∧ Im ΨALA}
vK = ⋃AS {f∈MorL(A,E) | f|V =v}
f,gK, B = Dom f ∩ Dom g ⇒ (f|BKg|BK) ⇒ f|B=g|B
fK Gr f = Gr h
C= Dom h = ⋃fK Dom fS
hK
(CD*(LC) ∋ x↦ (xC ? h(x) : φE(hLD(x))))) ∈ K
D*(LC) ⊂ C
C=D

Opérations définies par les termes

Tout élément t d'une L-écriture D définit un symbole d'opération V-aire, interprétant chaque L-algèbre E par ∀vEV, tE(v) = h(t) pour l'unique h∈MorL(D,E) tel que h|VD = v|VD. Ceci formalise l'opération définie par un terme, à savoir le L-terme de racine t dans D (qui peut remplacer D ici sans modifier les interprétations de t).

Ce symbole d'opération interprété étant la structure définie par (IdV,t), est préservée par tous les L-morphismes, donc peut s'ajouter à L sans changer la catégorie des L-algèbres.
Les symboles sL reviennent comme cas particuliers des termes qu'ils forment eux-mêmes où Ψ(t) = (s, IdV).
Pour le cas des termes "petits" (concrètement écrits), cette préservation a aussi un schéma d'une preuve pour chaque terme: ré-exprimant le terme comme une formule définissant une relation (le graphe de l'opération) utilisant les symboles ∃ et ∧, on peut utiliser la préservation des structures définies par de telles formules.
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
3.9. Term algebras
3.10. Integers and recursion
3.11. Presburger Arithmetic
4. Model Theory