1.5. Expressions et structures définissables
Termes et formules
Etant donnés les deux premiers niveaux d'une théorie (une liste de types et un langage), une expression
est un système fini d'occurrences de symboles, où, intuitivement parlant, une occurrence
d'un symbole dans une expression est un lieu où ce symbole est écrit (détails plus loin).
Chaque expression vient dans le contexte d'une liste de variables libres disponibles donnée.
Toute expression définira une valeur (un objet ou un Booléen) pour chaque donnée possible de:
- un système interprétant les types et les symboles de structure donnés ;
- des valeurs fixes des variables libres disponibles dans ce système.
Le type d'une expression, déterminé par sa syntaxe comme décrit plus bas,
sera le type de ses valeurs. Les expressions de type
booléen sont des formules ; les autres, de type appartenant à la
liste des types donnés
(leurs valeurs seront des objets), sont appelés des termes.
Par exemple « x+x
» est un terme comportant 2 occurrences de la variable «x», et une du symbole d'addition «+».
Les diverses sortes de symboles
Les expressions des théories du premier ordre et de la théorie des
ensembles, peuvent utiliser les symboles des sortes suivantes.
- Variables de chaque type:
- Variables libres, dans la liste des variables disponibles;
-
Variables liées, dont les occurrences sont contenues par des symboles liants (voir 1.8)
- Symboles de para-operateurs:
- Les symboles de structures (opérateurs et prédicats, appartenant au langage)
- Un symbole d'égalité par type (prédicat à deux
arguments de même type) abusivement tous notés =.
- Connecteurs logiques (1.4, énumérés en 1.6)
- L'opérateur
conditionnel peut être introduit pour abréviation (2.4).
- Symboles liants
(1.8):
- Les deux quantificateurs
∀ et ∃ (1.10) sont les seuls symboles
liants en logique du premier ordre ;
- d'autres seront introduits en théorie des ensembles.
En logique du premier ordre, appelons symboles logiques les quantificateurs
et symboles de para-opérateur hors du langage (égalité, connecteurs et opérateur
conditionnel): leur liste et leur signification dans chaque système sont déterminés
par le cadre logique et la liste de types donnée, ce qui justifie de ne pas les
présenter comme composants de théories particulières.Racine et sous-expressions
Chaque expression contient une occurrence spéciale d'un symbole appelé sa racine,
chaque autre occurrence d'un symbole dedans étant la racine d’une unique sous-expression
(une autre expression qu’on peut appeler la sous-expression de cette occurrence).
Le type d'une expression est donné
par le type de
résultats de sa racine.
Les expressions se construisent successivement, en parallèle entre
différentes listes de variables libres disponibles. Les premières et plus
simples sont faites d'un seul symbole (comme racine, ayant déjà une
valeur par lui-même) : les symboles de constante et de variable sont
les premiers termes; les constantes booléennes 1 et 0 sont les plus
simples formules.
Les autres expressions se construisent successivement
comme formées des données suivantes :
- Un choix de racine, occurrence d'un symbole de para-opérateur
(au delà des constantes déjà mentionnées) ou d'un symbole liant.
-
Si la racine est un symbole liant : un choix de symbole de variable à lier;
- Une liste d'expressions précédemment construites, dont le format
(le nombre d'entrées et leurs types) est déterminé
par la racine: pour un symbole de para-opérateur, ce format
est donné par la liste de ses arguments.
Un terme algébrique est un terme n'utilisant que
des variables libres et des symboles d'opérateur ; ce sont les seuls termes en
logique du premier ordre sans opérateur conditionnel. Cette notion pour un
seul type, sera formalisée comme une sorte de système en théorie des
ensembles en 4.1.
Conventions d'écriture
La présentation
de cette liste de sous-expressions directement attachées à la racine
nécessite un choix de convention. Pour un symbole de para-opérateur
autre qu'une constante :- La plupart des symboles
de para-opérateurs binaires ont la forme d'un caractère entre (séparant)
les deux arguments, comme dans x+y.
- Des symboles d'arité plus grande peuvent se présenter de même par
plusieurs caractères délimitant les entrées, comme dans l'addition
x+y+z de 3 nombres.
- Les notations du style de fonctions, comme +(x,y)
au lieu de x+y, sont plus courantes pour les arités
autres que 2 ; les parenthèses peuvent être omises lorsque les arités
sont connues (notation polonaise).
-
Certains symboles n'«apparaissent» qu'implicitement par leur manière
spéciale de disposer leurs arguments : multiplication dans
xy, puissance dans xn.
- Les parenthèses peuvent faire partie de
la notation de symboles (évaluateur de fonction, uplets...).
Les parenthèses peuvent aussi servir à distinguer (séparer) les
sous-expressions, donc distinguer la racine de chaque expression parmi
les autres occurrences de symboles. Par exemple la racine de
(x+y)n est l'opérateur de puissance.
Structures variables
Seuls quelques objets sont habituellement nommés par les symboles de
constantes d'un langage donné. Tout autre objet peut être nommé par
un symbole de variable fixe, dont le statut dépend du choix de la
théorie dans laquelle on se place:
- Une simple variable, utilisable dans les expressions qui par un
symbole liant peuvent lui faire parcourir une certaine notion ;
- Un nouveau symbole de constante, ajouté au langage, formant
une autre théorie de langage plus riche.
La différence disparait dans les interprétations génériques qui
convertissent les constantes en variables (dont les valeurs définissent
différents modèles).
Par analogie avec les constantes qui sont des structures particulières
(opérateurs nulaires), le concept de variable se généralise en celui de
structure variable. Mais ceux au-delà des opérations nulaires
échappent à la liste ci-dessus des symboles
admis dans les expressions.
Cependant, certains types d'utilisation de symboles de structure variable peuvent
être justifiés comme d'abréviations (descriptions indirectes) de l'utilisation
d'expressions légitimes. Le cas principal de ceci est expliqué ci-dessous;
un autre usage (qui y ressemble mais est en fait celui d'une méta-variable)
viendra en 1.10.
Structures définies par des expressions
Partant de n'importe quelle théorie on peut introduire une sorte de symbole
de structure variable (opérateur ou prédicat, même si un prédicat nulaire
est habituellement appelé une "variable booléenne" au lieu d'une "structure"),
définie par les données suivantes qu'il vise à abréger :
- Une expression (les termes définissent des opérateurs;
les formules définissent des prédicats et Booléens);
- Parmi ses variables libres disponibles, une sélection de celles qui seront
liées par cette définition dans le rôle d'arguments de la structure voulue; les
autres variables restant libres sont appelées les paramètres.
Chacune de ses valeurs possibles comme structure ou Booléen vient en fixant
les valeurs des paramètres.
Ainsi, la variabilité d'un tel symbole est l'abréviation de celle de tous les
paramètres.
Toute théorie
peut se développer par la construction
d'une nouvelle notion (type abstrait) donné comme domaine d'une
structure variable définie par une expression donnée, lorsque ses paramètres
parcourent toutes leurs combinaisons de valeurs possibles.
Tel est notre premier cas d'une règle de construction (sorte de
développement
d'une théorie). La revue complète des règles de construction sera
présentée en 4.11.
En théorie des ensembles, toute fonction f est synonyme du foncteur
défini par le terme «f(x)» d'argument x et de paramètre
f (mais le domaine de ce foncteur est Dom f au lieu d'un type).
Les termes sans argument définissent de simples objets (opérateurs nulaires);
celui fait d'une variable d'un type donné, vu comme paramètre, suffit
pour donner tous les objets de ce type.
Déclarons maintenant la méta-notion de "structure" en théorie du modèle,
et donc celles d '"opérateur" et de "prédicat", comme devant contenir toutes
les structures ainsi atteignables: définies par toute expression avec toutes les
valeurs possibles des paramètres. La version minimale d'une telle méta-notion
peut être formalisée comme un rôle donné à l'ensemble de toutes les combinaisons
d'une expression avec des valeurs fixes de ses paramètres. Comme cela fait appel à
l'ensemble infini de toutes les expressions, cette méta-notion échappe habituellement
(est inaccessible) aux capacités de la théorie étudiée : aucune expression fixe ne
peut suffire à la simuler. De plus en interprétant cela en théorie des
ensembles, encore d'autres d'opérations (indéfinissables) entre types interprétés
existent généralement dans l'univers. Parmi les rares exceptions, le domaine
ensembliste complet d'une structure variable dont tous les arguments parcourent
des ensembles finis (comme types interprétés) avec des limites de taille données,
peut être atteinte par une expression dont la taille dépend de ces limites.
Structures invariantes
Une structure invariante d'un système donné (langage interprété), est
une structure définie à partir de son langage sans paramètre (donc constante).
Cette distinction des structures invariantes parmi les autres structures,
généralise la distinction entre les constantes et les variables, à la fois
aux cas d'arité non nulle, et à ce qui peut être défini par des expressions
plutôt que directement nommé dans le langage.
En effet toute structure désignée par un symbole du langage est
directement définie par lui sans paramètre, et donc invariante.
Comme sera détaillé en 4.10, les théories peuvent être développées par des
définitions, consistant à nommer une autre structure invariante par un
nouveau symbole ajouté au langage. Parmi les aspects de la signification
préservée de la théorie, figurent les méta-notions de structure, structure
invariante, et l'ensemble des théorèmes exprimables avec le langage précédent.
Other languages:
EN : 1. First foundations of
mathematics : 1.5. Expressions
and definable structures