エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

論理計算と随伴関手(4)

半環について考える前に、半群についてもう少し考えてみます。

集合 S によって自由生成された自由半群 FSG(S) は S の元からなる1個以上有限個の文字列の全体として定義することができます。

集合 S によって自由生成された自由モノイド FM(S) は S の元からなる0個以上有限個の文字列の全体として定義することができます。

単位元を持たない半群 G に対して、集合の直和 G + \{e\} に以下のように積を定義します。 x \in G に対して xe = ex = x として、それ以外の積は G の積とします。このように定義すると G + \{e\} はモノイドとなります。

半群 G 上の同値関係 \sim が任意の w, x, y, z \in G に対して w \sim x、 y \sim z ならば wy \sim xz となるとき、同値類の全体は( x の同値類を [x] と書くと) [x][y] = [xy] と積を定義すると半群になります。

半群 (G, \cdot) と半群 (H, *) に対して、その元からなる1個以上有限個の列 x_1 y_1 \cdots x_n y_n または x_1 y_1 \cdots x_n y_n x_{n+1} または y_1 x_1 \cdots y_n x_n または y_1 x_1 \cdots y_n x_n y_{n+1} の全体からなる集合を [GH] とおきます( x_i \in G、 y_i \in H)。これに以下のように積( \alpha \beta のように書くことにします)を定義します。 \alpha x という形の元と y \beta という形の元の積の場合( x, y \in G、 \alpha と \beta は列)、 x \cdot y = z とすると積は (\alpha x)(y \beta) = \alpha z \beta と定義します。また \alpha x という形の元と y \beta という形の元の積の場合( x, y \in H、 \alpha と \beta は列)、 x * y = z とすると積は (\alpha x)(y \beta) = \alpha z \beta と定義します。それ以外の場合は、ある集合によって自由生成された自由半群の場合と同様に文字列の連結として定義します。このように定義すると [GH] は半群となります。

G を半群、 S を集合とします。 H = FSG(S) に対して上記の [GH] を考えます。写像 f: S \rightarrow G を拡張して半群の準同型 g: [GH] \rightarrow G とすることができます。

f: G \rightarrow H を半群の同型とします。 f(x) は x の逆元を表すので f(xy) = f(y)f(x) が成り立つとします。 K=[GH] 上の同値関係を考えます。 G が単位元を持たないときは K=[GH]+\{e\} を考えます。 xf(x) \sim e、 f(x)x \sim e、 xe \sim x、 ex \sim x の推移閉包から同値関係 \equiv を作ります。同値類の全体 K/\equiv は群となります。

半群 (G, \cdot) の台集合 G によって自由生成された自由半群 FSG(G) を考えます(演算を \cdot とし、 x \cdot y を xy と書くことにします)。 f: FSG(G) \rightarrow G を f(x_1 x_2 \cdots x_n) = x_1 x_2 \cdots x_n と定義すると f は半群の準同型となります。

集合 S によって自由生成された自由可換半群 FASG(S) は S の元からなる1個以上有限個の多重集合(重複を許す集合)の全体として定義することができます。

集合 S によって自由生成された自由可換モノイドは S の元からなる0個以上有限個の多重集合の全体として定義することができます。

集合 S によって自由生成された自由半群 G=FSG(S) (演算を xy のように書くことにします)によって自由生成された自由可換半群 R=FASG(G) (演算を + とします)を考えます。 R に積を (x_1 + x_2 + \cdots + x_m)(y_1 + y_2 + \cdots + y_n) = \sum_{i=1}^m \sum_{j=1}^n x_i y_j によって定義することができ、 R は半環になります。これを集合 S によって自由生成された自由半環と呼びます。