Appendice

Caractérisation des termes et des relations

La métamathématique, lorsqu’elle dépasse le niveau très élémentaire du présent chapitre, utilise largement les résultats de la mathématique; nous l’avons signalé dans l’Introduction. Le but de cet Appendice est de donner un exemple simple de ce genre de raisonnements. Nous commencerons par établir certains résultats qui se rattachent à la théorie mathématique des monoïdes libres (A, I, § 7, no 2); nous en ferons ensuite l’ « application » métamathématique à la caractérisation des termes et relations d’une théorie.

1. Signes et mots

\* Soit $S$ un ensemble non vide, dont les éléments seront appelés signes dans ce qui suit (cette terminologie étant appropriée à l’application métamathématique que nous avons en vue). Soit $L_0(S)$ le monoïde libre construit sur $S$ (A, I, § 7, no 2) dont les éléments (appelés mots) sont identifiés aux suites finies $A=(s_i)_{0\leq i\leq n}$ d’éléments de $S$; nous noterons multiplicativement la loi de composition dans $L_0(S)$, $AB$ étant donc la suite obtenue par juxtaposition de $A$ et de $B$. Le mot vide $\varnothing$ est élément neutre de $L_0(S)$. Rappelons que la longueur $l(A)$ d’un mot $A\in L_0(S)$ est le nombre d’éléments de la suite $A$; on a $l(AB)=l(A)+l(B)$; les mots de longueur $1$ sont les signes. Nous désignerons par $L(S)$ l’ensemble des mots non vides de $L_0(S)$.

Supposons en outre donnée une application $s\mapsto n(s)$ de $S$ dans l’ensemble $\mathbf{N}$ des entiers $\geq 0$; pour tout mot non vide $A=(s_i)_{0\leq i\leq k}$ de $L(S)$, on pose $n(A)=$ $\sum_{i=0}^{k} n(s_i)$, et $n(\varnothing)=0$; on dit que $n(A)$ est le poids de $A$. On a évidemment $n(AB)=n(A)+n(B)$.

Si $A=A'BA''$, on dit que le mot $B$ est un segment de $A$ (segment propre si en outre $B\ne A$). Si $A'$ (resp. $A''$) est vide, on dit que $B$ est un segment initial (resp. final) de $A$. Si $l(A')=k$, on dit que $B$ commence à la $(k+1)$-ème place.

Si $A=BCDEF$ (où les mots $B,C,D,E,F$ peuvent être vides), on dit que les segments $C$ et $E$ de $A$ sont disjoints.

2. Mots significatifs

Nous appellerons suite significative toute suite $(A_i)_{1\leq i\leq n}$ de mots de $L_0(S)$ qui possède la propriété suivante: pour chaque mot $A_i$ de la suite, l’une des deux conditions suivantes est vérifiée:

1° $A_i$ est un signe de poids 0.

2° Il existe $p$ mots $A_{i_1},A_{i_2},\ldots,A_{i_p}$ de la suite, d’indices $<i$, et un signe $f$ de poids $p$, tels que $A_i=fA_{i_1}A_{i_2}\ldots A_{i_p}$.

On appelle mots significatifs les mots qui figurent dans les suites significatives. On a immédiatement le résultat suivant:

3. Caractérisation des mots significatifs

Un mot $A\in L_0(S)$ est dit équilibré s’il possède les deux propriétés suivantes:

1° $l(A)=n(A)+1$ (ce qui implique que $A$ n’est pas vide).

2° Pour tout segment initial propre $B$ de $A$, on a $l(B)\leq n(B)$.

4. Application aux assemblages d’une théorie mathématique

Supposons que l’ensemble $S$ soit l’ensemble des signes d’une théorie mathématique $\mathscr T$. Nous poserons $n([\,])=0$, $n(\tau)=n(\neg)=1$, $n(\vee)=2$, $n(x)=0$ pour toute lettre $x$; enfin, pour tout signe spécifique $s$ de $\mathscr T$, $n(s)$ est le poids de $s$, fixé par la donnée de $\mathscr T$.

Soit $A$ un assemblage de $\mathscr T$. Nous désignerons par $A^*$ le mot obtenu en effaçant les liens de $A$, et nous dirons que $A$ est équilibré si $A^*$ est équilibré (dans $L_0(S)$). Nous appellerons segment de $A$ tout assemblage obtenu en munissant un segment $S$ de $A^*$ des liens qui, dans $A$, joignent deux signes de $S$.

Critère 1. — Si $A$ est un terme ou une relation de $\mathscr T$, $A$ est équilibré.

Soit en effet $A_1,A_2,\ldots,A_n$ une construction formative de $\mathscr T$ où figure $A$. Raisonnant par récurrence, supposons démontré que les $A_j$ d’indice $j<i$ sont équilibrés, et prouvons que $A_i$ est équilibré. Cela s’établit comme dans la première partie de la démonstration de la prop. 2, sauf lorsque $A_i$ est de la forme $\tau_x(B)$, avec $B=A_j$, $j<i$. Dans ce cas, soit $C$ l’assemblage obtenu en remplaçant $x$, en chacune de ses occurrences dans $B$, par $[\,]$; le mot $A_i^*$ est identique à $\tau C^*$; or $B^*$ est équilibré, donc $C^*$ est équilibré (puisque $n([\,])=n(x)=0$); par suite $A_i^*$ est équilibré.

Nous avons donc obtenu une condition nécessaire pour qu’un assemblage de $\mathscr T$ soit un terme ou une relation. Cette condition, on va le voir, n’est pas suffisante.

Soit $A$ un assemblage équilibré de $\mathscr T$. Si $A$ commence par une lettre ou un $[\,]$, $A$ se réduit nécessairement à ce signe initial (cor. 2 de la prop. 2). Dans tous les autres cas, nous allons définir le ou les assemblages antécédents à $A$.

1° Si $A$ commence par un $\tau$, ou un $\vee$, ou un signe spécifique, $A^*$ se met de manière unique sous la forme $fB_1B_2\ldots B_p$, $f$ étant un signe de poids $p\geq 1$ et les $B_i$ étant équilibrés (cor. 2 de la prop. 2). Nous appellerons assemblages antécédents à $A$ les segments $A_1,A_2,\ldots,A_p$ de $A$ qui correspondent aux segments $B_1,B_2,\ldots,B_p$ de $A^*$. En outre, nous dirons que $A$ est parfaitement équilibré si $A$ est identique à $fA_1A_2\ldots A_p$, autrement dit si, dans $A$, aucun lien ne joint $f$ à l’un des $B_i$, ou deux des $B_i$ distincts entre eux.

2° Si $A$ commence par un $\tau$, $A^*$ est de la forme $\tau B$, $B$ étant équilibré (cor. 2 de la prop. 2). Nous appellerons assemblage antécédent à $A$ l’un quelconque des assemblages $A_1$ définis de la façon suivante: on remplace les $[\,]$ de $B$ qui sont liés dans $A$ au $\tau$ initial par une lettre $x$ distincte des autres lettres figurant dans $B$, et on rétablit les liens qui joignent, dans $A$, deux signes de $B$. (Si, au lieu de $x$, on substitue une lettre $y$ qui ne figure pas non plus dans $B$, on obtient un assemblage qui n’est autre que $(y|x)A_1$.) En outre, nous dirons que $A$ est parfaitement

E I.46 DESCRIPTION DE LA MATHÉMATIQUE FORMELLE Appendice

équilibré si A est identique à $\tau_x(A_1)$, autrement dit si aucun lien ne joint le $\tau$ initial à des signes de $B$ autres que des $\square$.

On peut alors énoncer le critère suivant:

CRITÈRE 2. — Soit $A$ un assemblage équilibré de $\mathscr{T}$.

Pour que $A$ soit un terme, il faut et il suffit que l’une des conditions suivantes soit vérifiée: 1) $A$ se réduit à une lettre; 2) $A$ commence par un $\tau$, est parfaitement équilibré, et les assemblages antécédents sont des relations (d’après CF8, il suffit de vérifier qu’un assemblage antécédent est une relation).

Pour que $A$ soit une relation, il faut et il suffit que l’une des conditions suivantes soit vérifiée: 1) $A$ commence par un $\vee$ ou un $\neg$, est parfaitement équilibré, et les assemblages antécédents sont des relations; 2) $A$ commence par un signe spécifique, est parfaitement équilibré, et les assemblages antécédents sont des termes.

Les conditions sont suffisantes d’après les critères CF1 à CF4 (I, p. 19). Montrons qu’elles sont nécessaires. Si $A$ est une relation, on a vu (I, p. 19) que $A$ commence par un $\vee$, ou un $\neg$, ou un signe spécifique. On raisonne de façon analogue dans les trois cas. Si par exemple $A$ commence par un $\vee$, $A$ est de la forme $\vee BC$, où $B$ et $C$ sont des relations, de sorte que $B$, $C$ sont les assemblages antécédents à $A$; $A$ est donc parfaitement équilibré. Si $A$ est un terme, ou bien il se réduit à une lettre, ou bien il commence par un $\tau$. Si $A$ commence par un $\tau$, la définition d’une construction formative prouve que $A$ est de la forme $\tau_x(B)$, où $B$ est une relation et $x$ une lettre, de sorte qu’on peut prendre $B$ pour assemblage antécédent à $A$ et que $A$ est parfaitement équilibré.

Lorsqu’on veut savoir si un assemblage donné $A$ (non réduit à une lettre) est une relation (resp. un terme) de $\mathscr{T}$, on vérifie d’abord que $A$ est équilibré, et qu’il commence par un $\vee$, un $\neg$ ou un signe spécifique (resp. un $\tau$). On forme le ou les assemblages antécédents, et on vérifie s’il y a lieu que $A$ est parfaitement équilibré. Ceci fait, on est ramené à un problème analogue, mais concernant des assemblages plus courts. De proche en proche, on est ramené à des assemblages dont chacun est réduit à un signe, pour lesquels la solution est immédiate.

Exercices

See the exercises for Appendix 0.