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:

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. 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 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 : 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: 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, formant un développement de la théorie; d’autres utilisations possibles seront introduites en 1.10 (l'interprétation d’une utilisation comme abréviation d’autres travaux revient à utiliser une version développée du cadre logique).

Structures définies par des expressions

Dans toute théorie on peut légitimement introduire un nouveau symbole, désignant soit une structure variable (opérateur ou prédicat), soit une variable booléenne (prédicat nulaire, pas une "structure") comme abréviation de, donc définie par, les données suivantes: La variabilité du symbole est l'abréviation de celle de tous ses paramètres.

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.

Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
1.1. Introduction au fondement des mathématiques
1.2. Variables, ensembles, fonctions et opérations
1.3. Forme des théories: notions, objets et méta-objets
1.4. Structures des systèmes mathématiques
1.5. Expressions et structures définissables
1.6. Connecteurs logiques
1.7. Classes en théorie des ensembles
1.8. Symboles liants
1.9. Axiomes et preuves
1.10. Quantificateurs
1.11. Quantificateurs du 2e ordre
Aspects philosophiques
1.A. Temps en théorie des modèles
1.B. Indéfinissabilité de la vérité
1.C. Théorèmes d'incomplétude
1.D. Le cadre ensembliste unifié
2. Théorie des ensembles - 3. Algèbre

Other languages:
EN : 1. First foundations of mathematics : 1.5. Expressions and definable structures