4. Arithmétique et fondements du premier ordre
4.1. Termes algébriques
Introduction
Le concept de terme algébrique, à savoir un terme de langage purement algébrique L
avec un ensemble V de symboles de variables (pas de prédicats, de symboles logiques
ni de symboles liants), fut d'abord intuitivement
introduit en 1.5. Nous allons maintenant le formaliser comme une sorte de 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 que nous nommerons L-brouillons.
La formalisation
de ce concept a plusieurs variantes possibles.
Suivant une première approche, un L-brouillon est un
L-système équationnel
(D, b) tel que (Gr b ∪ D) est injective
(où b: VD → D and Gr b ∩ D
= ∅). Cette injectivité signifie que
- D est injective ;
- b est injective, permettant la simplification VD ⊂ D
et b = IdVD.
- Im b ∩ Im D = ∅, donc Im b = ∁D
Im D.
L'ensemble D désigne l'ensemble des occurrences de symboles, divisé entre l'ensemble
Im b d'occurrences de symboles de variables, et l'ensemble Im D d'occurrences de
symboles de L.
Mais cette définition des brouillons impliquant que chaque variable apparaisse une seule fois,
elle ne pourrait pas inclure directement les termes algébriques, où une variable peut avoir plusieurs
occurrences ou aucune, comme cas particuliers. La solution est de d'abord remplacer l'utilisation de b
par celle de son inverse b', fonction d'un ensemble d'occurrences VD ⊂ D
vers l'ensemble V des variables disponibles, puis d'en retirer l'exigence de bijectivité.
On peut garder l'exigence d'injectivité sur b', à savoir l'unicité d'occurrence de toute variable,
car toute multiplicité d'occurrences d'une variable dans un terme peut être remplacée par l'usage
d'une seule occurrence multiplement référencée à l'intérieur du terme (ce remplacement
donne un « terme » synonyme conçu abstraitement, ignorant tout souci de notations visibles).
Mais lorsque plusieurs variables sont disponibles (∃≥2: V), on doit autoriser les
b' non surjectifs (termes laissant certaines variables disponibles inutilisées), en particulier
pour autoriser comme brouillon tout terme fait d'un seul symbole de variable.
D'où la pertinence d'une formalisation où
VD = D∩V et b' = IdVD.
Brouillons
Enfin, définissons un L-brouillon comme un L-système injectif
(D, tGr ψD) où:
- Dom ψD = Im D = OD = D\V est
l'ensemble des occurrences de symboles de L dans D ;
- VD = ∁D OD = D∩V
est l'ensemble des variables utilisées (ou occurrences de variables) de D;
- 〈VD〉L= D (condition de bon fondement).
Notons ψD = σ ⊓ l, i.e. ∀x∈OD,
ψD(x) = (σ(x), lx)
∈ LD où σ∈LOD et
lx∈Dnσ(x).
Le bon fondement a pour formules équivalentes
∀A⊂OD, (∀x∈OD,
Im lx ⊂ A∪V ⇒ x∈A)
⇒ A=OD
∀A⊂D, (VD⊂A ∧
D*(LA) ⊂A) ⇒
A = D
∀A⊂D, VD⊂A≠D
⇒ ∃x∈OD\A, Im lx⊂A
∀A⊂OD, A≠∅ ⇒ ∃x∈A,
A∩ Im lx = ∅
Un brouillon clos est un brouillon sans variable : VD = ∅. Donc,
ψD: D → LD et SubLD
= {D}.
Les variables d'un brouillon peuvent se réinterpréter comme constantes: étendre ψD
par IdVD : VD → V,
forme un (L∪V)-brouillon clos.
Sous-brouillon et termes
Le bon-fondement rendant inintéressantes les parties stables des brouillons, au profit d'un autre concept de
stabilité: une partie A⊂D sera appelée un sous-brouillon de
D (ou une partie co-stable
de D) si, notant OA = A∩OD
et ψA = ψD|OA,
on a (Im ψA⊂ LA), i.e.
∀x∈OA, Im lx⊂A.
Tout sous-brouillon A d'un brouillon D est un brouillon, i.e. satisfait les
axiomes ci-dessus avec V fixe, où le bon-fondement de A est évidemment déduit de celui de
D par sa dernière formulation.
Comme avec les parties stables, toute intersection de sous-brouillons est un sous-brouillon.
De plus, toute union de sous-brouillons est aussi un sous-brouillon (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).
Le sous-brouillon co-engendré par une partie d'un brouillon, est l'intersection de toutes les
sous-brouillons qui l'incluent. Un terme est un brouillon co-engendré
par un unique élément qui est sa racine.
Tout élément x d'un brouillon D définit un terme Tx de
racine x, sous-brouillon de D co-engendré par {x}.
Chaque brouillon D est ordonnée par x ≤ y ⇔ x∈Ty.
C'est évidemment un préordre.
Son antisymétrie, à savoir l'unicité de la racine de tout terme, peut être prouvée comme suit
(une preuve plus élégante à partir de concepts plus généraux est donnée dans
l'étude des correspondances de Galois) :
∀x∈OD, VD ⊂
A={y∈D|x∉Ty} qui est un sous-brouillon
par transitivité de ≤.
x∉A ∴ ∃z∈OD\A,
Im lz⊂A.
A∪{z} est un sous-brouillon, donc Tz⊂A∪{z}
par définition de Tz.
z∈OD\A ∴
x∈Tz ∴ x = z.
Des valeurs équivalentes de x
pour ≤ donnent le même A, auquel le
même z convient. Cette équivalence est donc l'égalité. ∎
Catégories de brouillons
Comme systèmes relationnels particuliers, les classes de L-brouillons forment des
catégories concrètes.
Entre deux L-brouillons D,E,
f ∈ MorL(D,E) ⇔
(f[OD]⊂OE ∧ ψE ⚬
f|OD = Lf⚬ψD)
où la condition d'égalité se divise en
σE⚬f|OD
= σD
∀x∈OD,
lf(x) = f⚬lx.
Les coproduits y sont donnés par l'union
disjointe, comme avec les systèmes relationnels.
Une autre catégorie concrète est celle des brouillons avec morphismes préservant les
variables, où V
est fixe, et
MorL,V(D,E) =
{f ∈ MorL(D,E) | f|VD
= IdVD}.
C'est en gros la catégorie des (L∪V)-brouillons clos (réinterprétant les variables comme des constantes,
sauf qu'une variable peut y avoir plusieurs occurrences dans ces derniers, tandis qu'elle ne pouvait en avoir qu'une
éventuellement référencée plusieurs fois dans les premiers).
La définition des coproduits y est modifiée en
L,V∐i∈I Di
= (⋃i∈I VDi) ∪
∐i∈I
ODi
avec la structure définie comme avant. Dans le cas binaire ce
coproduit entre les brouillons D,E s'écrira D ⊔V E.
Les produits dans ces catégories ne peuvent pas être directement constitués des produits
des ensembles sous-jacents. La description des produits dans le cas préservant les variables
est laissée en exercice une fois compris la condensation des brouillons (4.3).
Images de brouillons
Si D,E sont des L-brouillons et f ∈ MorL(D,E) alors
- Pour tout sous-brouillon F⊂E, f*(F) est co-stable.
- Si f[VD] ⊂ VE alors Im f est co-stable,
et ∀x∈D,
f[Tx] = T f(x).
Inteprétations des brouillons dans les algèbres
Une interprétation d'un L-brouillon D dans une L-algèbre E,
est un morphisme f∈MorL(D,E), autrement dit
f|OD=
φE⚬Lf⚬ψD
∀x∈OD, f(x) =
σ(x)E(f⚬lx)
Toute interprétation v∈EV de variables dans une algèbre E
détermine une interprétation de tout brouillon D dans E. Pour simplifier les formulations, restreindre v à VD réduit le problème au cas
VD=V.
Théorème. Pour tout L-brouillon D et toute L-algebre E,
∀u∈EV,
∃!h∈MorL(D,E),
h|VD = u|VD.
Preuve. Pour simplifier, soit V = VD par restriction de u.
L'unicité a été vue avec les systèmes équationnels,
et servira pour prouver l'existence :
S = {A⊂D | V⊂A ∧ Im ψA⊂
LA}
K = ⋃A∈S
{f∈MorL(A,E) |
f|V = u}
∀f,g ∈K, B = Dom f ∩ Dom g
⇒ (f|B∈K ∧
g|B∈K)
⇒ f|B = g|B
⋃f∈K Gr f = Gr h
C = Dom h = ⋃f∈K Dom f
u ∈ K ∴ V ⊂ C ∈ S ∴ h ∈ K
(C∪D*(LC) ∋ x↦ (x∈C ?
h(x) : φE(Lh(ψD(x)))))
∈ K
D*(LC) ⊂ C
C = D ∎
Autrement dit, toute L-algèbre E est un module pour tout L-brouillon.
Ceci justifie formellement le concept de symbole d'opération
défini par un terme
et interprété comme operation dans chaque L-algèbre, par
les concepts expliqués en 3.11 : le role de symbole d'opération
V-aire joué par tout élément s d'un L-brouillon D (interprété dans chaque L-algèbre E par
∀u∈EV, sE(u) = h(s)
pour l'unique h∈MorL(D,E)
tel que
h|VD = u|VD),
préservée par tous les L-morphismes, est celui du symbole d'opération défini par
le L-terme de racine s co-engendré par s dans D.
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
5. Second-order foundations
6. Foundations of Geometry
Other languages:
EN :
4.1. Algebraic terms