Exercise 2, § 1

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Let $A$ be a term or a relation in a theory $\mathscr{T}$. By definition of a term or a relation (§ 1, no. 3), there exists a formative construction $C = (A_1, A_2, \dots, A_n)$ in $\mathscr{T}$ such that $A = A_k$ for some $k$. We prove by induction on the index $i$ that every assembly $A_i$ in $C$ satisfies the following three properties:

1. Every sign $\square$ in $A_i$ is linked to exactly one sign $\tau$ situated to its left. 2. Every sign $\tau$ in $A_i$ is either not linked at all or linked to one or more signs $\square$ situated to its right. 3. No sign other than $\tau$ or $\square$ is linked.

Base case. $i = 1$. Since there are no previous assemblies, $A_1$ must be a letter (condition (a) of the definition of a formative construction). A letter contains no $\tau$, no $\square$, and no links. The three properties hold vacuously.

Inductive step. Assume the properties hold for all $A_j$ with $j < i$. The assembly $A_i$ is obtained by one of the conditions (a)–(e) of the definition of a formative construction.

Condition (a): $A_i$ is a letter. Then $A_i$ contains no $\tau$, no $\square$, and no links. The properties hold vacuously.

Condition (b): $A_i = \neg B$ where $B$ is a relation (an assembly of the second species) appearing earlier in $C$. The assembly $A_i$ is the concatenation of the sign $\neg$ and the assembly $B$. The construction rule for $\neg$ creates no new links, and $\neg$ is neither $\tau$ nor $\square$, so it is not linked. The links present in $B$ remain exactly as they were; because $B$ is written to the right of $\neg$, the relative order of all signs inside $B$ is unchanged. By the induction hypothesis $B$ satisfies the three properties: every $\square$ in $B$ is linked to a $\tau$ to its left (inside $B$), every $\tau$ in $B$ is either unlinked or linked to $\square$ to its right (inside $B$), and no other sign in $B$ is linked. Since concatenation does not alter these links and introduces no links between $\neg$ and $B$, the same properties hold for $A_i$.

Condition (c): $A_i = \vee B C$ where $B$ and $C$ are relations appearing earlier in $C$. The assembly $A_i$ is the concatenation of $\vee$, $B$, and $C$. The construction creates no new links, $\vee$ is not $\tau$ or $\square$, and it is not linked. The links inside $B$ and inside $C$ are preserved unchanged, and the relative order of signs within $B$ and within $C$ is maintained because they are placed side by side without overlap. No links are created between $B$ and $C$, nor between $\vee$ and $B$ or $C$. By the induction hypothesis $B$ and $C$ each satisfy the three properties; therefore $A_i$ satisfies them as well.

Condition (d): $A_i = \tau_x(B)$ where $B$ is a relation appearing earlier in $C$ and $x$ is a letter. By the definition of $\tau_x(B)$ (§ 1, no. 1, Example 3, tag 03RY), we form the assembly $\tau B$, link the newly written $\tau$ to every occurrence of the letter $x$ in $B$, and then replace each such $x$ by the sign $\square$. The assembly $B$ satisfies the three properties by the induction hypothesis. The new $\tau$ is placed at the leftmost position of $A_i$. The occurrences of $x$ in $B$ are letters, hence they are not linked in $B$ (by property 3). After replacement they become signs $\square$, each linked exactly to the new $\tau$, which lies to their left. No other links are created: the linking operation only connects the new $\tau$ to the occurrences of $x$; it does not connect the new $\tau$ to any existing $\square$ in $B$ (since those are not $x$), nor does it connect any existing $\tau$ in $B$ to the new $\square$ (because existing $\tau$ are only linked to $\square$ already present in $B$ by the induction hypothesis). The links already present in $B$ remain unaltered. The relative order of $\tau$ and $\square$ inside $B$ is preserved because the new $\tau$ is to the left of all signs of $B$ and the replacement of $x$ by $\square$ does not change the order of the other signs. If $x$ does not occur in $B$, the new $\tau$ is not linked at all, which is allowed by property 2. Thus $A_i$ satisfies the three properties.

Condition (e): $A_i = s A_1 A_2 \dots A_n$ where $s$ is a specific sign of weight $n$ and $A_1,\dots,A_n$ are terms appearing earlier in $C$. The assembly $A_i$ is the concatenation of $s$ and the assemblies $A_1,\dots,A_n$. The construction creates no new links; $s$ is a specific sign (hence neither $\tau$ nor $\square$) and therefore not linked. The links inside each $A_j$ are preserved unchanged, and the relative order of signs within each $A_j$ is maintained because the $A_j$ are written consecutively without overlap. No links are created between different $A_j$ or between $s$ and any $A_j$. By the induction hypothesis each $A_j$ satisfies the three properties; therefore $A_i$ satisfies them as well.

By induction, every assembly in the formative construction $C$, in particular $A$, satisfies the three stated properties. This completes the proof.