エレファントな群とリー代数(7) - エレファント・コンピューティング調査報告

±マグマ

集合 $M$ が二項演算 $+$ と単項演算 $-$ を持つとき $(M, +, -)$ を±マグマと呼ぶことにします。「単項・二項マグマ」と呼んでいましたが長いのでこう呼ぶことにします。ここでは、マグマに関する議論に演算を付け加えたものをまとめて説明していきます。

この議論に関する一般論があると思うのですが、ウェブで検索しても見つかりませんでした。「Universal Algebra for Computer Scientists」という本に少し書かれているようです。この本を持っているので今後読んでみたいと思います。「完備化」についてはWikipediaに「クヌース・ベンディックス完備化アルゴリズム」という記事があります。「完備化」についても今後調査したいと思います。

部分±マグマ

$(M, +, -)$ を±マグマとします。 $X, Y \subseteq M$ に対して $X + Y = \{ x + y \mid x \in X, y \in Y \}$ 、 $- X = \{ - x \mid x \in X \}$ と書くことにします。 $X \subseteq M$ が $X + X \subseteq X$ 、 $- X \subseteq X$ を満たすとき $X$ は $+$ 、 $-$ の $X$ への制限に関して±マグマとなります。このような $X$ を $M$ の部分±マグマと呼ぶことにします。

±マグマの準同型

±マグマ $(M. +, -)$ から±マグマ $(M', \oplus, \ominus)$ への写像 $f: M \to M'$ が演算を保存するとき、すなわち

$f(x + y) = f(x) \oplus f(y)$
$f(- x) = \ominus f(x)$

を満たすとき、 $f$ を±マグマ $(M. +, -)$ から±マグマ $(M', \oplus, \ominus)$ への±マグマの準同型と呼びます。

部分集合で生成された部分±マグマ

$X$ を±マグマ $M$ の部分集合とします。 $N \subseteq M$ に対して、 $N$ が $X$ を含む $M$ の部分マグマであり、 $X$ を含む $M$ の部分±マグマの最小のものであるとき、 $N$ を $X$ で生成された $M$ の部分±マグマと呼ぶことにします。±マグマ $M$ が $X$ で生成された $M$ の部分±マグマであるとき $M$ を $X$ で生成された±マグマと呼ぶことにします。

$\displaystyle \bigcap \{ N \mid N \ は \ X \ を含む \ M \ の部分±マグマ \}$ は $X$ で生成された $M$ の部分±マグマとなります。

±マグマの「多項式」

±マグマと $M$ と集合 $X$ の元に、「 $(\!\!($ 」、「 $)\!\!)$ 」、「 $\oplus$ 」、「 $\ominus$ 」をを付け加えたものからなる、有限個の列全体の集合を $S(M, X)$ とします。

$a \in M$ だけの長さ $1$ の列を $[a]$ とし、 $M' = \{ [a] \mid a \in M\}$ とします。同様に $x \in X$ だけの長さ $1$ の列を $[x]$ とし、 $X' = \{ [x] \mid x \in X\}$ とします。 $\alpha \in M'$ に対して $\alpha = [a]$ となる $a$ を $\grave{\alpha}$ とします。

$S(M, X)$ に二項演算 $\boxplus: S(M, X) \times S(M, X) \to S(M, X)$ を \begin{cases}
α \boxplus β = [\grave{α} + \grave{β}] & (α, β \in M' \ のとき) \\
α \boxplus β = (\!\!(α \oplus β)\!\!) & (それ以外のとき) \\
\end{cases}、単項演算 $\boxminus: S(M, X) \times S(M, X)$ を \begin{cases}
\boxminus α = [- \grave{α}] & (α \in M' \ のとき) \\
\boxminus α = (\!\!(\ominus α)\!\!) & (それ以外のとき) \\
\end{cases} と定義すると $(S(M, X), \boxplus, \boxminus)$ は±マグマとなります。

$M' \cup X'$ で生成された $(S(M, X), \boxplus, \boxminus)$ の部分±マグマを $M[X]$ と書くことにします。 $M[X]$ の演算を $+$ 、 $-$ と書くことにします。以下では $M'$ を $M$ 、 $X'$ を $X$ と書きます。

「多項式」からの写像の準同型への拡張

$(M[X], +, -)$ の台集合 $M[X]$ の部分集合 $B$ に対して \begin{cases}
B^{\pm(1)} = B \\
B^{\pm(n+1)} = (B^{\pm(n)} + B^{\pm(n)}) \cup (- B^{\pm(n)}) \\
\end{cases} と帰納的に $B^{\pm(n)}$ を定義します。 $\displaystyle M[X] = \bigcup_{n \in \mathbb{N}} (M \cup X)^{\pm(n)}$ となります。

$(M', +, -)$ を±マグマ、 $g: M \sqcup X \to M'$ を単射( $M \sqcup X$ は集合の直和)、 $g$ の $M$ への制限が±マグマの準同型であるとします。

$\alpha \in M[X]$ に対して $\displaystyle n_\alpha = \min \{ n \in \mathbb{N} \mid \alpha \in \bigcup_{k \le n} (M \cup X)^{\pm(k)} \}$ が存在します。 $\alpha \in M \cup X$ または $\alpha = \beta + \gamma$ となる $\displaystyle \beta, \gamma \in \bigcup_{k \le n_\alpha-1} (M \cup X)^{\pm(k)}$ が存在する( $\alpha \in M[X]^+$ とします)か、または $\alpha = - \beta$ となる $\displaystyle \beta \in \bigcup_{k \le n_\alpha-1} (M \cup X)^{\pm(k)}$ が存在します( $\alpha \in M[X]^-$ とします)。\begin{cases}
g^*(\alpha) = g(\alpha) & (\alpha \in M \cup X \ のとき) \\
g^*(\alpha) = g^*(\beta) + g^*(\gamma) & (\alpha \in M[X]^+, \alpha = \beta + \gamma \ のとき) \\
g^*(\alpha) = - g^*(\beta) & (\alpha \in M[X]^-, \alpha = - \beta \ のとき) \\
\end{cases} と帰納的に定義することにより、±マグマの準同型 $g^*: M[X] \to M'$ を定義することができます。

「多項式」への「代入」

$\sigma: X \to M[X]$ とすると、上の議論により、 $\sigma$ を拡張した $M$ を保存する±マグマの準同型 $\sigma^*: M[X] \to M[X]$ が一意的に存在します。

$\alpha \in M[X]$ に対して $\alpha[\sigma] = \sigma^*(\alpha)$ と定義します。 $X = \{x_1, x_2, \cdots, x_n\}$ のとき $\alpha[\sigma]$ を $\alpha[\sigma(x_1), \sigma(x_2), \cdots, \sigma(x_n)]$ と書くことにします。これを $\alpha$ の $X$ に $\sigma$ を代入する、または $x_1, x_2, \cdots, x_n$ に $\sigma(x_1), \sigma(x_2), \cdots, \sigma(x_n)$ を代入するということにします。 $\sigma$ を代入写像と呼ぶことにします。

$(X \mapsto \alpha): M[X]^X \to M[X]$ を $\sigma: X \to M[X]$ を $\alpha[\sigma]$ に写す写像とします。 $X = \{x_1, x_2, \cdots, x_n\}$ のとき $(x_1, x_2, \cdots, x_n \mapsto \alpha): M[X]^n \to M[X]$ を $\langle \sigma(x_1), \sigma(x_2), \cdots, \sigma(x_n) \rangle \in M[X]^n$ を $\alpha[\sigma(x_1), \sigma(x_2), \cdots, \sigma(x_n)]$ に写す写像とします。これは $\langle a_1,a_2, \cdots, a_n \rangle \in M[X]^n$ を $\alpha[a_1, a_2, \cdots, a_n]$ に写す写像となります。これらを $\alpha$ の「ラムダ式化」と呼ぶことにします。

部分項の位置

$\alpha \in M[X]^+$ に対して、 $\alpha = \alpha_L + \alpha_R$ となる $\alpha_L, \alpha_R$ が一意的に存在します。 $\alpha$ を $\alpha_L$ に写す写像を $L: M[X]^+ \to M[X]$ 、 $\alpha$ を $\alpha_R$ に写す写像を $R: M[X]^+ \to M[X]$ と定義することができます。 $\alpha \notin M[X]^+$ のときは $M[X]$ に含まれない元 $\bot$ (失敗を表す)を追加した $M[X] \sqcup \{\bot\}$ を考え、 $L(\alpha) = R(\alpha) = \bot$ と定義することによってこれらを拡張して、 $L, R: M[X] \to M[X] \sqcup \{\bot\}$ とします。さらに $L(\bot) = R(\bot) = \bot$ と定義することによって拡張して、 $L, R: M[X] \sqcup \{\bot\} \to M[X] \sqcup \{\bot\}$ とします。

同様に、 $\alpha \in M[X]^-$ に対して、 $\alpha = - \alpha_B$ となる $\alpha_B$ が一意的に存在します。 $\alpha$ を $\alpha_B$ に写す写像を $B: M[X]^- \to M[X]$ と定義することができます。 $\alpha \notin M[X]^-$ のときは $B(\alpha) = \bot$ と定義することによって拡張して、 $B: M[X] \to M[X] \sqcup \{\bot\}$ とします。さらに $B(\bot) = \bot$ と定義することによって拡張して、 $B: M[X] \sqcup \{\bot\} \to M[X] \sqcup \{\bot\}$ とします。

$L(\alpha)$ を $\alpha L$ 、 $R(\alpha)$ を $\alpha R$ 、 $B(\alpha)$ を $\alpha B$ と書くことにすると \begin{cases}
α L = α_L & (α \in M[X]^+) \\
α L = ⊥ & (α \in M[X] \setminus M[X]^+) \\
⊥ L = ⊥
\end{cases} \begin{cases}
α R = α_L & (α \in M[X]^+) \\
α R = ⊥ & (α \in M[X] \setminus M[X]^+) \\
⊥ R = ⊥
\end{cases} \begin{cases}
α B = α_B & (α \in M[X]^-) \\
α B = ⊥ & (α \in M[X] \setminus M[X]^-) \\
⊥ B = ⊥
\end{cases} となります。

各 $\delta_i$ を $L$ 、 $R$ または $B$ としたとき、すべての自然数 $n$ に対する $\alpha \delta_1 \delta_2 \cdots \delta_n$ 全体の集合 $T_\alpha$ を考えます。

$\displaystyle M[X] = \bigcup_{n \in \mathbb{N}} (M \cup X)^{(n)}$ であることから $\displaystyle n_\alpha = \min \{ n \in \mathbb{N} \mid \alpha \in \bigcup_{k \le n} (M \cup X)^{(k)} \}$ が存在するので、すべての $0 \le n \le n_\alpha$ に対する $\alpha \delta_1 \delta_2 \cdots \delta_n$ 全体の集合を $T'_\alpha$ とすると $T_\alpha = T'_\alpha \cup \{\bot\}$ となります。

$T_\alpha \setminus \{\bot\}$ の元を $\alpha$ の部分項と呼ぶことにします。 $\alpha$ の部分項を $\alpha \delta_1 \delta_2 \cdots \delta_n$ と表したときの最も小さい $n$ に対応する $\delta_1 \delta_2 \cdots \delta_n$ 全体の集合を $I_\alpha$ とします。 $\delta_1 \delta_2 \cdots \delta_n$ を $\alpha$ の部分項 $\alpha \delta_1 \delta_2 \cdots \delta_n$ の位置と呼ぶことにします。

$\alpha \in M[X]$ の位置 $\delta_1 \delta_2 \cdots \delta_n \in I_\alpha$ を $\beta \in M[X]$ で置き換えた $\alpha(\delta_1 \delta_2 \cdots \delta_n \gets \beta)$ を \begin{cases}
β & (n = 0) \\
L(α)(δ_2 \cdots δ_n \gets β) + R(α) & (n>0, δ_1 = L) \\
L(α) + R(α)(δ_2 \cdots δ_n \gets β) & (n>0, δ_1 = R) \\
- B(α)(δ_2 \cdots δ_n \gets β) & (n>0, δ_1 = B) \\
\end{cases} と帰納的に定義します。 $n = 0$ のときの位置を $0$ と書くことにします。

書き換え規則

$\alpha, \beta \in M[X]$ とします。 $\alpha, \beta$ の順序のついた組 $\langle \alpha, \beta \rangle$ の「ラムダ式化」 $(x_1, x_2, \cdots, x_n \mapsto \langle \alpha, \beta \rangle): M[X]^n \to M[X]^2$ を上の議論と同様に考えることができます。これを書き換え規則と呼び、 $(x_1, x_2, \cdots, x_n \mapsto \alpha \to \beta)$ と書くことにします。

$\alpha \in M[X]$ に対して、代入写像 $\sigma: Y \to M[X][Y]$ が存在して、ある $\alpha$ の部分項の位置 $p \in I_\alpha$ に対して $p(\alpha) = \beta[\sigma]$ となるとき、 $\alpha$ は書き換え規則 $\rho = (Y \mapsto \beta \to \gamma)$ によって書き換え可能ということにします。 $\alpha$ の部分項の位置 $p$ を $\gamma[\sigma]$ で置き換えた $\alpha(p \gets \gamma[\sigma])$ を書き換え後の項と呼ぶことにします。これを \begin{eqnarray*}
α & \xrightarrow{ρ, σ, p} & α(p \gets γ[σ])
\end{eqnarray*} または \begin{eqnarray*}
α & \xrightarrow{ρ} & α(p \gets γ[σ])
\end{eqnarray*} と書くことにします。