Exercice 7, Annexe 0

Soient $R_1,R_2,\ldots,R_n$ des relations logiquement irréductibles distinctes (exerc. 6) d’une théorie $\mathscr{T}$. Soit $A_1,A_2,\ldots,A_p$ une construction logique de base $R_1,R_2,\ldots,R_n$. Supposons chaque $R_i$ affecté de l’un des signes 0, 1. On affecte alors à chaque $A_i$ l’un des signes 0, 1 par la règle suivante : 1° Si $A_i$ est identique à $R_j$, on affecte à $A_i$ le même signe qu’à $R_j$ ; 2° si $A_i$ est identique à $\neg A_j$, $A_j$ précédant $A_i$, on affecte à $A_i$ le signe 1 (resp. 0) si $A_j$ est affecté du signe 0 (resp. 1) ; 3° si $A_i$ est identique à $V A_jA_k$, on affecte à $A_i$ le signe 1 si $A_j$ et $A_k$ sont tous deux affectés du signe 1, le signe 0 dans les autres cas. (On dit qu’on applique la « règle symbolique » suivante : $\neg 0=1$, $\neg 1=0$, $V11=1$, $V10=V01=V00=0$.)

a) Montrer qu’il n’y a qu’une seule manière d’attribuer un signe à chaque $A_i$, conformément à la règle précédente.

b) Si $R$ est logiquement construite sur $R_1,R_2,\ldots,R_n$, le signe affecté à $R$ ne dépend que de la construction logique de base $R_1,R_2,\ldots,R_n$ où figure $R$.

c) Si $R$ et $S$ sont logiquement construites sur $R_1,R_2,\ldots,R_n$ et si les signes affectés à $R$ et $\Rightarrow RS$ sont 0, le signe affecté à $S$ est 0.

d) Supposons désormais que les axiomes de $\mathscr{T}$ soient fournis par les seuls schémas S1 à S4. Soit $R$ un théorème de $\mathscr{T}$, $R_1,R_2,\ldots,R_n$ ses composantes logiques. Montrer que, quelle

Appendice EXERCICES E I.51

que soit la manière d’affecter l’un des signes 0 ou 1 à $R_1, R_2,\ldots,R_n$, le signe correspondant affecté à $R$ est 0 (établir d’abord ceci quand $R$ est un axiome de $\mathscr T$ ; dans le cas général, considérer une démonstration de $R$, et appliquer c)). e) Soit $R$ une relation logiquement irréductible de $\mathscr T$. Montrer que ni $R$, ni « non $R$ » ne sont des théorèmes de $\mathscr T$. En particulier, $\mathscr T$ est non contradictoire (utiliser d)). f) Soient $R_1,R_2,\ldots,R_n$ des relations logiquement irréductibles distinctes de $\mathscr T$. On considère toutes les relations de la forme « $R'_1$ ou $R'_2$ ou ... ou $R'_n$ », où, pour chaque $i$, $R'_i$ est l’une des deux relations $R_i$, « non $R_i$ ». Soient $S_1,S_2,\ldots,S_p$ ces relations. Soient $T_1,T_2,\ldots,T_q$ les relations de la forme « $S_{i_1}$ et $S_{i_2}$ et ... et $S_{i_r}$ », où $i_1,i_2,\ldots,i_r$ est une suite strictement croissante quelconque d’indices. Soit enfin $T_0$ la relation « $R_1$ ou $R_2$ ou ... ou $R_n$ ». Montrer que toute relation logiquement construite sur $R_1,R_2,\ldots,R_n$ est équivalente dans $\mathscr T$ à une et une seule des relations $T_0,T_1,\ldots,T_q$. (Démontrer d’abord que chaque relation $R_i$ est équivalente dans $\mathscr T$ à l’une des relations $T_0,T_1,\ldots,T_q$ ; si $R$ est logiquement construite sur $R_1,R_2,\ldots,R_n$, raisonner de proche en proche sur une construction logique de base $R_1,R_2,\ldots,R_n$ contenant $R$ ; pour l’unicité, utiliser d).) g) Soient $R$ une relation de $\mathscr T$, $R_1,R_2,\ldots,R_n$ ses composantes logiques. Pour que $R$ soit un théorème de $\mathscr T$, il faut et il suffit que, pour toute manière d’affecter l’un des signes 0 ou 1 à $R_1,R_2,\ldots,R_n$, le signe correspondant affecté à $R$ soit 0.