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

一般マグマの多項式の書き換え規則の合成(2)

前回の説明で間違っているところがあったので訂正します。

書き換え規則 $\rho = (x_1, \cdots, x_n \mapsto a \to b)$ に対して、 $a(x_1, \cdots, x_n)$ の部分項の位置 $p$ の部分項を $a(x_1, \cdots, x_n)_p$ 、 $b(x_1, \cdots, x_n)$ の部分項の位置 $p$ の部分項を $b(x_1, \cdots, x_n)_p$ とします。 $a(x_1, \cdots, x_n)$ の部分項の位置全体の集合を $Q_\rho$ 、 $b(x_1, \cdots, x_n)$ の部分項の位置全体の集合を $P_\rho$ とします。 $α$ の部分項の位置 $p$ の部分項を $β$ で置き換えたものを $α(p←β)$ とします。

二つの書き換え規則 $\rho = (x_1, \cdots, x_n \mapsto a \to b)$ と $\mu = (y_1, \cdots, y_m \mapsto c \to d)$ を合成することを考えます。 $\sigma = u(b(x_1, \cdots, x_n)_p, c(y_1, \cdots, y_m))$ のとき $ρ \stackrel{p}{\triangleright} μ$ を \begin{cases}
ρ \stackrel{p}{\triangleright} μ & = & (x_1, \cdots, x_n, y_1, \cdots, y_m \mapsto \\ & & \hspace{1em} a(x_1, \cdots, x_n)[σ] \to \\
& & \hspace{2em} b(x_1, \cdots, x_n)(p←d(y_1, \cdots, y_m))[σ]) & (σ \in Σ) \\
ρ \stackrel{p}{\triangleright} μ & = & ⊥ & (σ = ⊥) \\
\end{cases} と定義します。 $\sigma = u(b(x_1, \cdots, x_n), c(y_1, \cdots, y_m)_p)$ のとき $ρ \stackrel{p}{\triangleright} μ$ を \begin{cases}
ρ \stackrel{p}{\triangleright} μ & = & (x_1, \cdots, x_n, y_1, \cdots, y_m \mapsto \\ & & \hspace{1em} c(x_1, \cdots, x_n)(p←a(y_1, \cdots, y_m))[σ] \to \\
& & \hspace{2em} d(x_1, \cdots, x_n)[σ]) & (σ \in Σ) \\
ρ \stackrel{p}{\triangleright} μ & = & ⊥ & (σ = ⊥) \\
\end{cases} と定義します。

書き換え規則の集合 $R$ と $S$ に対して $R \cdot S = \{λ \stackrel{p}{\triangleright} μ, λ \stackrel{\hat{p}}{\triangleright} μ \mid λ \in R, μ \in S, p \in P_λ, \hat{p} \in Q_μ\} \setminus \{⊥\}$ と定義します。 $1$ を何も変換しない規則とし、書き換え規則の集合 $R$ に対して \begin{cases}
R^0 & = & \{1\} \\
R^{n+1} & = & R^n \cdot R \\
\end{cases} と定義します。

以下では、書き換え規則 $(x_1, \cdots, x_n \mapsto λ \to μ)$ を、 $λ(x'_1, \cdots, x'_n) \to μ(x'_1, \cdots, x'_n)$ と書きます。ここで $x'_i$ は、 $x_i$ に書き換え規則の集合内の番号 $r$ と合成の回数 $t$ によってインデックスをつけたもの( $x_i$ を $y$ とすると $y_{r,t}$ )とします。 $p \in P_λ$ のとき、 $λ \stackrel{p}{\triangleright} ρ$ を $μ$ とするとき $λ \stackrel{\rho,p}{\Longrightarrow} μ$ と書きます。 $p \in Q_μ$ のとき、 $λ \stackrel{p}{\triangleright} ρ$ を $μ$ とするとき $λ \stackrel{\rho,\hat{p}}{\Longrightarrow} μ$ と書きます。部分項の位置 $p$ は、項を文字列で書いたときの左から順番につけた番号で表すとします。

単位元をもつマグマの準同型(1)

$M$ を単位元 $e$ をもつマグマ、 $M'$ を単位元 $e'$ をもつマグマ、 $f: M \to M'$ をマグマの準同型とします。このとき $e' \in f(M)$ ならば $f(e) = e'$ が成り立つことを示します。

以下の表記では、 $x$ のように「 $'$ 」がつかないものは $M$ に属するもの、 $x'$ のように「 $'$ 」がついたものは $M'$ に属するものとします。

書き換え規則の集合 \begin{cases}
\rho_{1} & = & ( & x & \mapsto & e x & \to & x & ) \\
\rho_{2} & = & ( & x & \mapsto & x & \to & e x & ) \\
\rho_{3} & = & ( & x' & \mapsto & x' e' & \to & x' & ) \\
\rho_{4} & = & ( & x' & \mapsto & x' & \to & x' e' & ) \\
\rho_{5} & = & ( & x, y & \mapsto & f(x y) & \to & f(x) f(y) & ) \\
\rho_{6} & = & ( & x, y & \mapsto & f(x) f(y) & \to & f(x y) & ) \\
\rho_{7} & = & ( & & \mapsto & f(x) & \to & e' & ) \\
\rho_{8} & = & ( & & \mapsto & e' & \to & f(x) & ) \\
\end{cases} から規則の合成によって \begin{matrix}
1 & \stackrel{\rho_{4},0}{\Longrightarrow} & x'_{4,1} \to x'_{4,1} e' & \stackrel{\rho_{8},2}{\Longrightarrow} & x'_{4,1} \to x'_{4,1} f( x ) \\
& \stackrel{\rho_{6},0}{\Longrightarrow} & f( x_{6,3} ) \to f( x_{6,3} x ) & \stackrel{\rho_{1},1}{\Longrightarrow} & f( e ) \to f( x ) \\
& \stackrel{\rho_{7},0}{\Longrightarrow} & f( e ) \to e' \\
1 & \stackrel{\rho_{8},0}{\Longrightarrow} & e' \to f( x ) & \stackrel{\rho_{2},1}{\Longrightarrow} & e' \to f( e x ) \\
& \stackrel{\rho_{5},0}{\Longrightarrow} & e' \to f( e ) f( x ) & \stackrel{\rho_{7},3}{\Longrightarrow} & e' \to f( e ) e' \\
& \stackrel{\rho_{3},0}{\Longrightarrow} & e' \to f( e ) \\
\end{matrix} を得ることができます。

単位元をもつマグマの準同型(2)

$M$ を単位元 $e$ をもつマグマ、 $M'$ を単位元 $e'$ をもつマグマ、 $f: M \to M'$ をマグマの準同型、 $f(e) = e'$ とします。このとき $x^{-1}$ が $x$ の逆元ならば $f(x^{-1})$ は $f(x)$ の逆元となることを示します。

書き換え規則の集合 \begin{cases}
\rho_{1} & = & ( & & \mapsto & x^{-1} x & \to & e & ) \\
\rho_{2} & = & ( & & \mapsto & e & \to & x^{-1} x & ) \\
\rho_{3} & = & ( & x, y & \mapsto & f(x y) & \to & f(x) f(y) & ) \\
\rho_{4} & = & ( & x, y & \mapsto & f(x) f(y) & \to & f(x y) & ) \\
\rho_{5} & = & ( & & \mapsto & f(e) & \to & e' & ) \\
\rho_{6} & = & ( & & \mapsto & e' & \to & f(e) & ) \\
\end{cases} から規則の合成によって \begin{matrix}
1 & \stackrel{\rho_{4},0}{\Longrightarrow} & f( x_{4,1} ) f( y_{4,1} ) \to f( x_{4,1} y_{4,1} ) & \stackrel{\rho_{1},1}{\Longrightarrow} & f( x^{-1} ) f( x ) \to f( e ) \\
& \stackrel{\rho_{5},0}{\Longrightarrow} & f( x^{-1} ) f( x ) \to e' \\
1 & \stackrel{\rho_{6},0}{\Longrightarrow} & e' \to f( e ) & \stackrel{\rho_{2},1}{\Longrightarrow} & e' \to f( x^{-1} x ) \\
& \stackrel{\rho_{3},0}{\Longrightarrow} & e' \to f( x^{-1} ) f( x ) \\
\end{matrix} を得ることができます。

単位元をもつマグマの準同型(3)

$M$ を単位元 $e$ をもつマグマ、 $M'$ を単位元 $e'$ をもつマグマ、 $f: M \to M'$ をマグマの準同型とします。このとき $x^{-1}$ が $x$ の逆元、 $f(x^{-1})$ が $f(x)$ の逆元ならば $f(e) = e'$ となることを示します。

書き換え規則の集合 \begin{cases}
\rho_{1} & = & ( & & \mapsto & x^{-1} x & \to & e & ) \\
\rho_{2} & = & ( & & \mapsto & e & \to & x^{-1} x & ) \\
\rho_{3} & = & ( & x, y & \mapsto & f(x y) & \to & f(x) f(y) & ) \\
\rho_{4} & = & ( & x, y & \mapsto & f(x) f(y) & \to & f(x y) & ) \\
\rho_{5} & = & ( & & \mapsto & f(x^{-1}) f(x) & \to & e' & ) \\
\rho_{6} & = & ( & & \mapsto & e' & \to & f(x^{-1}) f(x) & ) \\
\end{cases} から規則の合成によって \begin{matrix}
1 & \stackrel{\rho_{2},0}{\Longrightarrow} & e \to x^{-1} x & \stackrel{\rho_{3},\hat{1}}{\Longrightarrow} & f( e ) \to f( x^{-1} ) f( x ) & \stackrel{\rho_{5},0}{\Longrightarrow} & f( e ) \to e' \\
1 & \stackrel{\rho_{6},0}{\Longrightarrow} & e' \to f( x^{-1} ) f( x ) & \stackrel{\rho_{4},0}{\Longrightarrow} & e' \to f( x^{-1} x ) & \stackrel{\rho_{1},1}{\Longrightarrow} & e' \to f( e ) \\
\end{matrix} を得ることができます。