L'algèbre libre sur une signature engendrée par un ensemble de variables dont les éléments sont des termes syntaxiques construits à partir de symboles d'opération et de variables, pris sans imposition d'identités autres que les règles syntaxiques de formation.

Principe

Les termes se forment inductivement à partir des variables et des symboles d'opération ; l'algèbre des termes est l'objet initial dans la catégorie des algèbres de la signature, exprimant la propriété universelle selon laquelle toute affectation de variables s'étend de façon unique en un homomorphisme.

Démonstration

Pour la signature des monoïdes (opération binaire ⋅ et unité e), l'algèbre des termes contient tous les mots formels construits à partir du symbole binaire, de la constante e et des variables ; un homomorphisme depuis cette algèbre évalue chaque terme formel en sa valeur sémantique dans un monoïde donné.

Mauvaise application

Confondre l'algèbre des termes avec un quotient par des identités équationnelles (par exemple, traiter des termes syntaxiquement différents comme égaux parce qu'ils coïncident dans une algèbre particulière) ; on perd alors la propriété de liberté et d'initialité.

Conséquence

Les algèbres des termes fournissent des représentants syntaxiques canoniques, servent de modèles initiaux pour spécifier et raisonner sur des structures algébriques, et rendent la substitution et l'unification en opérations concrètes correspondant à des homomorphismes.

Inversion

L'inverse est une algèbre quotient obtenue en imposant des identités (une théorie équationnelle) sur l'algèbre des termes ; on obtient alors l'algèbre libre de la théorie plutôt que l'algèbre brute des termes, et l'égalité devient équationnelle plutôt que syntaxique.

Limite

S'applique à des signatures finies en arité et traite les termes modulo l'égalité syntaxique seulement ; exclut la quotientation par des axiomes, les constructeurs de termes d'ordre supérieur et les identifications sémantiques propres à des modèles particuliers.

Tension sémantique

Algèbre Des Termes est en tension avec l'algèbre libre modulo identités : la première traite les termes purement syntaxiquement et est initiale dans la catégorie de toutes les algèbres, tandis que la seconde encode une théorie équationnelle donnée et identifie les termes en conséquence.

Synthèse

Une Algèbre Des Termes est l'algèbre libre brute des termes syntaxiques pour une signature, incarnant la formation inductive des termes et la propriété universelle selon laquelle les affectations de variables s'étendent de façon unique en homomorphismes.