自由モノイドのイテレーター(2) - 非専門的シンギュラリティー研究所

有限文字列と無限文字列からなるモノイド

$C^* = C^0 + C^1 + C^2 + \cdots$ を $C$ で生成された自由モノイドとします。演算子を $*$ とします。 $C$ の元を文字、 $M$ の元を有限の長さの文字列とみなします。

$s, s' \in C^*$ の積は $s = c_1 * c_2 * \cdots * c_n$ 、 $s' = c'_1 * c'_2 * \cdots * c'_m$ のとき

$s * x = c_1 * c_2 * \cdots * c_n * c'_1 * c'_2 * \cdots * c'_m$

$C^\infty$ を $C^*_n = C^n + C^{n+1} + C^{n+2} + \cdots$ と包含写像からなる射影系による射影的極限とします。この元を無限の長さの文字列とみまします。

$s \in C^*$ と $x \in C^\infty$ の積 $s \otimes x$ を定義することができます。 $s = c_1 * c_2 * \cdots * c_n$ 、 $x = c'_1 * c'_2 * \cdots$ のとき

$s * x = c_1 * c_2 * \cdots * c_n \otimes c'_1 * c'_2 * \cdots$

$M^\infty = (C^* + C^\infty)^*$ とおくと $M^\infty$ はモノイドになります。演算子を $\oplus$ とします。

$\oplus$ 、 $\otimes$ を $*$ と同一視し、 $M^\infty$ の単位元を $C^*$ の単位元と同一視することによって、 $M^\infty$ は演算子 $*$ に関してモノイドになります。

前回の議論のためには $M^\infty$ がモノイドである必要はなく、有限文字列と無限文字列の積が自然に定義できれば良いのですが、「積が定義された集合」というだけでは説明がわかりにくいですし、モノイドとして定義できそうなので、モノイドとして定義することにします。

さらに詳しく調べるために、無限文字列が射影的極限として定義できるかどうかを調べたのですが、この定義では積を定義する方法としてあまり有効ではないようです。以下にまとめます。

射影的極限による定義

「wikipedia:射影極限」を参考にしています。ChatGPT でいろいろ書いてもらったものを間違っているところは修正してまとめます。

自由モノイド

集合 $A$ に対して $A^k$ を $k$ 個の $A$ の直積、 $+$ を集合の直和とすると $A^* = 1 + A + A^2 + A^3 + \cdots$ は $A$ で生成された自由モノイドとなります。演算子を $\cdot$ 、単位元を $\varepsilon$ とします( $1 = \{\varepsilon\}$ )。 $A$ の元を文字、 $A^*$ の元を有限の長さの文字列と同一視することができます。演算は「文字列の連結」、単位元は「空文字列」となります。

射影系の定義

集合族の定義

$S_n$ を、長さ $n$ 以上の全ての文字列の集合とします。すなわち、次のように定義されます：
$S_n = \{ s \in A^* \mid |s| \geq n \}$
ここで $|s|$ は文字列 $s$ の長さを表します。

$s$ を長さがちょうど $n$ の文字列とし、 $s \cdot A^*$ を、 $s$ に任意の有限文字列を結合した文字列全体の集合とします：
$s \cdot A^* = \{ s \cdot t \mid t \in A^* \}$
$S_n$ は、こうした形の集合 $s \cdot A^*$ によって分割されます。

$A^*_n$ は、これらの $S_n$ の部分集合全体の集合とします。すなわち、 $A^*_n$ は $S_n$ を上記のように分割するすべての集合 $s \cdot A^*$ を集めたものです：
$A^*_n = \{ s \cdot A^* \mid s \in A^*, |s| = n \}$
これは、長さが $n$ 以上の文字列を持つ部分集合に関する構造です。

半群構造

$A^*_n$ の元である各集合 $s \cdot A^*$ 同士に対して、積を次のように定義します：
$(s_1 \cdot A^*) \cdot (s_2 \cdot A^*) = s_1 \cdot A^*$
つまり、長さ $n$ の文字列 $s_1$ と $s_2$ の積が常に最初の $s_1$ によって決定され、結果は $s_1 \cdot A^*$ となります。この積に基づいて構築される構造が半群になるかどうかを確認しましょう。

半群の条件

半群であるためには、次の条件を満たす必要があります：

結合性：積演算が結合的であること。すなわち、任意の $a, b, c$ に対して次が成り立つこと：
$(a \cdot b) \cdot c = a \cdot (b \cdot c)$

結合性を確認するため、3つの元 $s_1 \cdot A^*, s_2 \cdot A^*, s_3 \cdot A^*$ の積を計算します。

$(s_1 \cdot A^*) \cdot (s_2 \cdot A^*) \cdot (s_3 \cdot A^*)$ を計算すると、次が成り立ちます：
$( (s_1 \cdot A^*) \cdot (s_2 \cdot A^*)) \cdot (s_3 \cdot A^*) = (s_1 \cdot A^*) \cdot (s_3 \cdot A^*) = s_1 \cdot A^*$
一方、 $s_1 \cdot A^* \cdot ( (s_2 \cdot A^*) \cdot (s_3 \cdot A^*))$ についても：
$s_1 \cdot A^* \cdot ( (s_2 \cdot A^*) \cdot (s_3 \cdot A^*)) = s_1 \cdot A^*$

両側で同じ結果 $s_1 \cdot A^*$ になるため、積は結合的です。

射影写像と準同型

$n > m$ のとき、任意の $A^*_n$ の元 $s \cdot A^* \in A^*_n$ は、ある一つの $A^*_m$ の元に含まれます。具体的には、長さ $n$ 以上の文字列は、長さ $m$ 以上の文字列でもあるため、 $A^*_n$ の各元は $A^*_m$ の元の一部として含まれます。

この対応に基づいて、自然な射影写像 $\pi_{n,m}: A^*_n \to A^*_m$ を次のように定義します：
$\pi_{n,m}(s \cdot A^*) = \text{長さ} \, m \, \text{まで切り詰めた文字列に対応する集合}$
この射影写像 $\pi_{n,m}$ は半群の準同型となります。つまり、任意の $x, y \in A^*_n$ に対して次が成り立ちます：
$\pi_{n,m}(x \cdot y) = \pi_{n,m}(x) \cdot \pi_{n,m}(y)$

$n > m > l$ に対して、 $\pi_{n,l} = \pi_{m,l} \circ \pi_{n,m}$ が成り立ちます。

射影的極限による無限文字列の定義

各 $A^*_n$ の射影写像による射影系に基づいて、射影的極限を構成します。これにより、無限文字列を次のように定義します：
$\displaystyle A^\infty = \varprojlim_{n \in \mathbb{N}} A^*_n = \left\{ (x_n)_{n \in \mathbb{N}} \in \prod_{n=0}^{\infty} A^*_n \ \middle| \ \forall n > m, \ \pi_{n,m}(x_n) = x_m \right\}$
射影的極限によって得られる無限文字列は、各 $n$ における長さ $n$ 以上の文字列の整合的な集合の極限とみなされます。

有限文字列と無限文字列の積

このようにして定義された無限文字列に対して、有限文字列との積を次のように定義することができます。有限文字列 $x \in A^*$ と無限文字列 $y \in A^\infty$ の積 $x \cdot y$ は、文字列の自然な結合に基づいて定義されます：
$x \cdot y = \text{有限文字列} \, x \, \text{を無限文字列} \, y \, \text{の前に結合した文字列}$
この積により、有限文字列と無限文字列の積を整合的に定義できます。

有限と無限の文字列全体のモノイドの定義

有限文字列全体 $A^*$ と無限文字列全体 $A^\infty$ の和集合 $A^* \cup A^\infty$ に対して、元同士の積を定義してモノイド構造を持たせる方法について考えます。この場合、以下の点を考慮しながら積を定義する必要があります。

1. 有限文字列と有限文字列の積: これは通常の文字列の結合に基づいて行われます。
2. 無限文字列と有限文字列の積および有限文字列と無限文字列の積: これらは整合的に定義する必要があります。
3. 無限文字列同士の積: 無限文字列同士の積も定義する必要があります。

さらに、モノイドの定義に従って、単位元が存在し、結合性が成り立つような積の定義を求めます。

単位元

まず、モノイドには単位元が必要です。ここでは、空文字列 $\varepsilon$ を単位元として採用します。この単位元は次のように機能します：

任意の有限文字列 $x \in A^*$ に対して：
$\varepsilon \cdot x = x \cdot \varepsilon = x$
任意の無限文字列 $x \in A^\infty$ に対して：
$\varepsilon \cdot x = x \cdot \varepsilon = x$

この空文字列は、有限文字列にも無限文字列にも適用可能であり、モノイドの単位元として機能します。

積の定義

次に、積の定義を行います。各場合について考慮します。

1. 有限文字列同士の積

任意の有限文字列 $x, y \in A^*$ に対して、通常の文字列の結合として定義します：
$x \cdot y = xy$
ここで、 $xy$ は $x$ と $y$ を単純に連結した文字列です。

2. 有限文字列と無限文字列の積

有限文字列 $x \in A^*$ と無限文字列 $y \in A^\infty$ の積 $x \cdot y$ は、 $x$ を $y$ の前に結合した無限文字列として定義します。これにより、結果は無限文字列になります：
$x \cdot y = \text{有限文字列} \, x \, \text{を無限文字列} \, y \, \text{の前に結合した無限文字列}$
同様に、無限文字列 $y \in A^\infty$ と有限文字列 $x \in A^*$ の積も次のように定義します：
$y \cdot x = y$
この場合、無限文字列の後に有限文字列を結合しても結果は変わらず、無限文字列 $y$ そのものが結果になります。

3. 無限文字列同士の積

無限文字列 $x, y \in A^\infty$ の積は、無限文字列の最初の部分に基づいて定義します。具体的には、無限文字列同士の積は最初の文字列 $x$ をそのまま返すように定義します：
$x \cdot y = x$
この定義により、無限文字列同士の積も整合的に定義されます。

結合性の確認

この積の定義に基づいて、結合性が成り立つことを確認します。任意の $a, b, c \in A^* \cup A^\infty$ に対して次を確認します：

有限文字列同士の積：通常の文字列結合なので結合則が成り立ちます：
$(x \cdot y) \cdot z = x \cdot (y \cdot z)$

有限文字列と無限文字列の積：有限文字列 $x \in A^*$ と無限文字列 $y \in A^\infty$ の場合も、積の定義により結合則が成り立ちます：
$(x \cdot y) \cdot z = x \cdot y = x \cdot (y \cdot z)$
無限文字列が含まれる積でも、定義に基づき結合性が維持されます。

無限文字列同士の積：無限文字列同士の積も定義に基づき結合的です：
$(x \cdot y) \cdot z = x \cdot z = x = x \cdot (y \cdot z)$