Appendix

Characterization of terms and relations

Metamathematics, when it goes beyond the very elementary level of the present chapter, makes considerable use of the results of mathematics, as we remarked in the Introduction. The purpose of this Appendix is to give a simple example of this type of reasoning [^1]. We shall begin by establishing certain results which belong to the mathematical theory of free semigroups; we shall then use these results in a metamathematical " application " to obtain a characterization of the terms and relations in a theory.

1. Signs and words

\* Let S be a non-empty set, whose elements will be called signs (this terminology being appropriate to the metamathematical application we have in mind). Let $\mathrm{L}_0(\mathrm{S})$ be the free semigroup generated by S; the elements of $\mathrm{L}_0(\mathrm{S})$ are called words and are identified with finite sequences $A = (s_i)_{0 \leqslant i \leqslant n}$ of elements of S. The law of composition in $\mathrm{L}_0(\mathrm{S})$ will be written multiplicatively, so that $AB$ is the sequence obtained by juxtaposition of $A$ and $B$. The empty word $\emptyset$ is the identity element of $\mathrm{L}_0(\mathrm{S})$. We recall that the length $l(A)$ of a word $A \in \mathrm{L}_0(\mathrm{S})$ is the number of elements in the sequence $A$; thus $l(AB) = l(A) + l(B)$, and the words of length 1 are the signs. Let $\mathrm{L}(\mathrm{S})$ denote the set of non-empty words in $\mathrm{L}_0(\mathrm{S})$. ¶ Suppose, moreover, that we are given a mapping $s \rightarrow n(s)$ of S into the set $\mathbf{N}$ of integers $\geqslant 0$. For each non-empty word $A = (s_i)_{0 \leqslant i \leqslant k}$ of L(S), we put

and $n(\emptyset) = 0$. $n(A)$ is called the weight of $A$. Clearly $n(AB) = n(A) + n(B)$. ¶ If $A = A'BA''$, the word $B$ is said to be a segment of $A$ (a proper segment if also $B \neq A$). If $A'$ (resp. $A''$) is empty, $B$ is said to be an initial (resp. final) segment of $A$. If $l(A') = k$, then $B$ is said to begin at the $(k+1)$th place.

¶ If $A = BCDEF$ (where the words $B$, $C$, $D$, $E$, $F$ may be empty) the segments $C$ and $E$ of $A$ are said to be disjoint.

2. Significant words

A significant sequence is any sequence $(A_j)_{1 \leqslant j \leqslant n}$ of words of $\mathrm{L}_0(\mathrm{S})$ with the following property : for each word $A_i$ of the sequence, one of the following two conditions is satisfied :

(1) $A_i$ is a sign of weight 0.

(2) There exist $p$ words $A_{i_1}$, $A_{i_2}$, ..., $A_{i_p}$ in the sequence, with indices less than $i$, and a sign $f$ of weight $p$ such that

Words which appear in significant sequences are called significant words. Then we have :

3. Characterization of significant words

A word $A \in \mathrm{L}_0(\mathrm{S})$ is said to be balanced if it has the following two properties :

(1) $l(A) = n(A) + 1$ (which implies that $A$ is not empty).

(2) For every proper initial segment $B$ of $A$, $l(B) \leqslant n(B)$.

4. Application to assemblies in a mathematical theory

Suppose that the set S is the set of signs of a mathematical theory $\mathscr{T}$. We put $n(\square)=0$, $n(\tau)=n(\eta)=1$, $n(\vee)=2$, $n(x)=0$ for every letter $x$;

and finally, for every specific sign $s$ of $\mathscr{T}$, $n(s)$ is the weight of $s$, which is fixed when $\mathscr{T}$ is given.

¶ Let $A$ be an assembly in $\mathscr{T}$. We denote by $A^*$ the word obtained by deleting the links in $A$, and we shall say that $A$ is balanced if $A^*$ is balanced [in $L_0(S)$]. A segment of $A$ is any assembly obtained by replacing, in a segment $S$ of $A^*$, the links which, in $A$, join pairs of signs in $S$.

CRITERION 1. If $A$ is a term or a relation in $\mathscr{T}$, then $A$ is balanced.

Let $A_1$, $A_2$, $\ldots$, $A_n$ be a formative construction in $\mathscr{T}$, in which $A$ appears. Let us argue by induction and suppose that we have proved that the $A_j$ of indices $j<i$ are balanced; then we have to prove that $A_i$ is balanced. The proof goes just as in the first part of the proof of Proposition 2, except when $A_i$ is of the form $\tau_x(B)$ with $B=A_j$ and $j<i$. In this case, let $C$ be the assembly obtained by replacing $x$, wherever it occurs in $B$, by $\square$. The word $A^*$ is then identical with $\tau C^*$; now $B^*$ is balanced, and therefore $C^*$ is balanced (because $n(\square)=n(x)=0$). Consequently $A_i^*$ is balanced.

¶ We have thus obtained a necessary condition for an assembly in $\mathscr{T}$ to be a term or a relation. But this condition is not sufficient, as we shall see.

¶ Let $A$ be a balanced assembly in $\mathscr{T}$. If $A$ begins with a letter or a $\square$, then $A$ must consist of this sign alone (Proposition 2, Corollary 2). For all other cases, we shall now define the assembly or assemblies antecedent to $A$.

(1) If $A$ begins with a $\land$, or a $\vee$, or a specific sign, then $A^*$ can be put in exactly one way in the form $fB_1B_2\ldots B_p$, where $f$ is a sign of weight $p\geq 1$ and the $B_i$ are balanced (Proposition 2, Corollary 2). The segments $A_1$, $A_2$, $\ldots$, $A_p$ of $A$ which correspond to the segments $B_1$, $B_2$, $\ldots$, $B_p$ of $A^*$ are called the assemblies antecedent to $A$. Moreover, we shall say that $A$ is perfectly balanced if $A$ is identical with

in other words if no link in $A$ joins $f$ to one of the $B_i$, or joins two distinct $B_i$.

(2) If $A$ begins with a $\tau$, then $A^*$ is of the form $\tau B$, where $B$ is balanced (Proposition 2, Corollary 2). In this case an assembly antecedent to $A$ is any of the assemblies $A_1$ defined as follows : replace the signs $\square$ in $B$ which are linked in $A$ to the initial $\tau$ by a letter $x$ distinct from the other letters which appear in $B$, and replace the links which join two signs of $B$ in $A$. (If, instead of $x$, we substitute a letter $y$ which also does not appear in $B$, we obtain an assembly which is just $(y|x)A_1$.) Moreover, we shall say that $A$ is perfectly balanced if $A$ is identical with $\tau_x(A_1)$, in other words if no link joins the initial $\tau$ to any sign of $B$ other than a $\square$.

¶ We can now state the following criterion :

C2. Let $A$ be a balanced assembly in $\mathscr{T}$.

¶ For $A$ to be a term it is necessary and sufficient that one of the following conditions be satisfied : (1) $A$ consists of a single letter; (2) $A$ begins with a $\tau$, is perfectly balanced, and its antecedent assemblies are relations (by CF8, it is enough to verify that one antecedent assembly is a relation); (3) $A$ begins with a substantific sign, is perfectly balanced, and its antecedent assemblies are terms. ¶ For $A$ to be a relation it is necessary and sufficient that one of the following conditions be satisfied : (1) $A$ begins with a $\vee$ or a $\neg$, is perfectly balanced, and its antecedent assemblies are relations; (2) $A$ begins with a relational sign, is perfectly balanced, and its antecedent assemblies are terms.

The criteria CF1 to CF4 (§ 1, no. 4) show that the conditions are sufficient. Let us show that they are necessary. We have already seen (§ 1, no. 3) that if $A$ is a relation, then $A$ begins with a $\vee$, or a $\neg$, or a relational sign. The reasoning is similar in each of the three cases. If, for example, $A$ begins with a $\vee$, then $A$ is of the form $\vee BC$, where $B$ and $C$ are relations, so that $B$ and $C$ are the assemblies antecedent to $A$; hence $A$ is perfectly balanced. If $A$ is a term, then there are two cases : it consists of a single letter, or it begins with either a substantific sign or a $\tau$. In the second case, we argue as above. If $A$ begins with a $\tau$, the definition of a formative construction shows that $A$ is of the form $\tau_x(B)$, where $B$ is a relation and $x$ a letter, so that we may take $B$ as assembly antecedent to $A$, and $A$ is perfectly balanced.

When we wish to test whether a given assembly $A$ (not consisting of a single letter) is a relation (resp. a term) in $\mathscr{T}$, we first verify that $A$ is balanced and that it begins with a $\vee$, a $\neg$, or a relational sign (resp. with a $\tau$ or a substantific sign). Then we form the antecedent assembly or assemblies, and verify (if appropriate) that $A$ is perfectly balanced. Having done this, we are left with an analogous problem relating to shorter assemblies. Thus, step by step, we come down to assemblies each of which consists of a single sign, for which the solution is immediate.

Exercises

See the exercises for Appendix 0.

[^1]: The results established in this Appendix will not be used anywhere else in this series.