Exercise 1, § 2

Let S be the set of signs $\mathsf{P}$, $\mathsf{P}^-$, $\mathsf{X}$, $\mathsf{X}^-$, $x_1$, ..., $x_n$, the letters $x_i$ being of weight 0, $\mathsf{P}$ and $\mathsf{P}^-$ of weight 1, and $\mathsf{X}$, $\mathsf{X}^-$ of weight 2. For each word A in L(S) we define the variance of A as follows : each letter $x_i$, and the signs $\mathsf{P}$, $\mathsf{X}$, have variance 0; the signs $\mathsf{P}^-$, $\mathsf{X}^-$ have variance 1; the variance of A is the sum \* (in the field $\mathbf{F}_2$) \* of the variances of the signs which appear in A (in other words, it is 0 if A contains an even number of signs of variance 1, and is 1 otherwise).

A signed echelon type is a balanced word A in L(S) (Chapter I, Appendix, no. 3) which satisfies one of the following two conditions: (1) A is one of the letters $x_i$; (2) if A is of the form $f\mathrm{A}_1\mathrm{A}_2 \ldots \mathrm{A}_p$ (Chapter I, Appendix, no. 3, Corollary 2 of Proposition 2), where $f$ is one of the signs $\mathsf{P}$, $\mathsf{P}^-$, $\mathsf{X}$, $\mathsf{X}^-$, $p$ is equal to 1 or 2 and the $\mathrm{A}_i$ $(1 \leqslant i \leqslant p)$ are balanced words, then each of the $\mathrm{A}_i$ is a signed echelon type; further, if $f = \mathsf{X}$, then $\mathrm{A}_1$ and $\mathrm{A}_2$ have variance 0, and if $f = \mathsf{X}^-$, then $\mathrm{A}_1$ and $\mathrm{A}_2$ have variance 1.

A signed echelon type is said to be covariant if it has variance 0, contravariant if it has variance 1. If in a signed echelon type A we replace $\mathsf{P}^-$ and $\mathsf{X}^-$ by $\mathsf{P}$ and $\mathsf{X}$, respectively, we obtain an echelon type A\* (§ 1, Exercise 1). Every realization of the echelon type A\* on $n$ terms $\mathrm{E}_1$, ..., $\mathrm{E}_n$ is called a realization of the signed echelon type A on $\mathrm{E}_1$, ..., $\mathrm{E}_n$, and is written $\mathrm{A}(\mathrm{E}_1, \ldots, \mathrm{E}_n)$.

Let $\mathrm{E}_1$, ..., $\mathrm{E}_n$, $\mathrm{E}'_1$, ..., $\mathrm{E}'_n$ be sets, and let $f_i$ be a mapping of $\mathrm{E}_i$ into $\mathrm{E}'_i$ $(1 \leqslant i \leqslant n)$. Show that to each signed echelon type S on $x_1$, ..., $x_n$ we may associate a mapping $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ having the following properties :

(i) If S is covariant (resp. contravariant), then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is a mapping of $\mathrm{S}(\mathrm{E}_1, \ldots, \mathrm{E}_n)$ into $\mathrm{S}(\mathrm{E}'_1, \ldots, \mathrm{E}'_n)$ (resp. of $\mathrm{S}(\mathrm{E}'_1, \ldots, \mathrm{E}'_n)$ into $\mathrm{S}(\mathrm{E}_1, \ldots, \mathrm{E}_n)$).

(ii) If S is a letter $x_i$, then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is $f_i$.

(iii) If S is $\mathsf{P}\mathrm{T}$ (resp. $\mathsf{P}^-\mathrm{T}$), and if $g = \{f_1, \ldots, f_n\}^{\mathrm{T}}$ is a mapping of F into F′, then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is the extension of $g$ to sets of subsets (resp. the extension of $\overset{-1}{g}$ to sets of subsets).

(iv) If S is $\mathsf{X}\mathrm{TU}$ or $\mathsf{X}^-\mathrm{TU}$, if $\{f_1, \ldots, f_n\}^{\mathrm{T}}$ is a mapping $g : \mathrm{F} \to \mathrm{F}'$ and if $\{f_1, \ldots, f_n\}^{\mathrm{U}}$ is a mapping $h : \mathrm{G} \to \mathrm{G}'$, then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is the extension $g \times h : \mathrm{F} \times \mathrm{G} \to \mathrm{F}' \times \mathrm{G}'$.

The mapping $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is called the signed canonical extension of $f_1, \ldots, f_n$ corresponding to the signed echelon type S. If S is an echelon type (i.e., if $\mathsf{P}^-$ and $\mathsf{X}^-$ do not appear in S), then the signed canonical extension $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is equal to $\langle f_1, \ldots, f_n \rangle^{\mathrm{S}}$.

Show that, if $f_i$ is a mapping of $\mathrm{E}_i$ into $\mathrm{E}'_i$, and if $f'_i$ is a mapping of $\mathrm{E}'_i$ into $\mathrm{E}''_i$ $(1 \leqslant i \leqslant n)$, then for a covariant signed echelon type S we have

and for a contravariant signed echelon type we have

Deduce, that if $f_i$ is a bijection of $\mathrm{E}_i$ onto $\mathrm{E}'_i$ and if $f'_i$ is its inverse bijection $(1 \leqslant i \leqslant n)$, then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is a bijection and $\{f'_1, \ldots, f'_n\}^{\mathrm{S}}$ its inverse. Moreover, if $\mathrm{S}^*$ is the (unsigned) echelon type corresponding to the signed echelon type S, then $\{f_1, \ldots, f_n\}^{\mathrm{S}}$ is equal to $\langle f_1, \ldots, f_n \rangle^{\mathrm{S}^*}$ or to $\langle f'_1, \ldots, f'_n \rangle^{\mathrm{S}^*}$ according as S is covariant or contravariant.