多重集合・自由可換モノイド(5) - エレファント・ビジュアライザー調査記録

ここでは、データの順序に依存しないアルゴリズムをプログラミング言語のデータ構造で表すことを考えています。単項イデアル整域のイデアルの演算を抽象化したものを考えます。いったん今までの結果をまとめます。

$M$ を可換モノイドで簡約可能とします。単位元を $1$ とします。 $M$ は二元の最大公約数をとる演算 $\land$ をもち、最大公約数に関して可換べき等半群とします。

$1 \land x = 1 \ (\forall x \in M)$
$(x \land y) z = xz \land yz \ (\forall x, y, z \in M)$

が成り立つとします。

$M$ に順序 $\le$ を $x \le y \iff x \land y = x$ で定義します。 $x \le y$ のとき $x$ を $y$ の約数、 $y$ を $x$ の倍数と呼びます。

$\mathrm{Pr}(M) = \{ p \in M \mid p \le xy \implies p \le x \lor p \le y \ (\forall x, y \in M) \}$
とおき、 $\mathrm{Pr}(M)$ の元を素元と呼びます。
$\mathrm{Ir}(M) = \{ p \in M \mid p = xy \implies x = 1 \lor y = 1 \ (\forall x, y \in M) \}$
とおき、 $\mathrm{Ir}(M)$ の元を既約元と呼びます。

$\mathrm{Pr}(M) = \mathrm{Ir}(M)$

[証明] $\mathrm{Pr}(M) \subseteq \mathrm{Ir}(M):$
$\begin{eqnarray*} p \in \mathrm{Pr}(M) & \iff & \bigl[ \ p \le xy \implies p \le x \lor p \le y \ (\forall x, y \in M) \ \bigr] \\ & \implies & \bigl[ \ p = xy \implies xy \le x \lor xy \le y \ (\forall x, y \in M) \ \bigr] \\ & \iff & \bigl[ \ p = xy \implies y = 1 \lor x = 1 \ (\forall x, y \in M) \ \bigr] \\ & \iff & p \in \mathrm{Ir}(M) \end{eqnarray*}$
これは最大公約数の存在に関係なく成り立ちます。

$\mathrm{Pr}(M) \supseteq \mathrm{Ir}(M):$
$p \in \mathrm{Ir}(M)$ とし $p \le xy$ とします。 $p \land x \le p$ であり $p \in \mathrm{Ir}(M)$ であることから $p \land x = p$ または $p \land x \le 1$ となります。 $p \land x = p$ のときは $p = p \land x \le x$ となります。 $p \land x = 1$ のときは $p \le py \land xy = (p \land x)y = y$ となります。

よって $p \in \mathrm{Ir}(M)$ ならば $p \in \mathrm{Pr}(M)$ となります。[証明終わり]

$M$ の部分集合 $S$ が生成する $M$ の部分モノイドを $S^*$ と書きます。

最大公約数の存在に関係なく以下が成り立ちます。

$M = \mathrm{Pr}(M)^* \implies \mathrm{Pr}(M) = \mathrm{Ir}(M)$

[証明] $p \in \mathrm{Ir}(M) = \mathrm{Pr}(M)^* \cap \mathrm{Ir}(M)$ とすると

$p = q_1 \cdots q_n$ となる $q_i \in \mathrm{Pr}(M)$ が存在します。

$p \in \mathrm{Ir}(M)$ よりある一つの $q_i$ 以外は $1$ となります。

よって $p = q_i \in \mathrm{Pr}(M)$ となって $\mathrm{Ir}(M) \subseteq \mathrm{Pr}(M)$ となります。

$\mathrm{Pr}(M) \subseteq \mathrm{Ir}(M)$ は最大公約数の存在に関係なく成り立つので $\mathrm{Pr}(M) = \mathrm{Ir}(M)$ となります。[証明終わり]

任意の自然数 $n$ に対して $a_n \in M$ が定義されて任意の自然数 $n$ に対して $a_n \gneq a_{n+1}$ であるとき、元の列 $\{a_n \mid n \in \mathbb{N}\}$ を $M$ の無限下降列と呼びます。

以下の条件を考えます。

$\mathrm{Min}(M):$ $M$ の任意の部分集合 $S$ で $S$ の任意の元 $x, y$ の最大公約数 $x \land y$ が $S$ に属するもの(最大公約数に関して閉じているもの)には最小元 $\min S$ が存在する。

$\mathrm{Min}(M) \implies M = \mathrm{Ir}(M)^*$

[証明] $M \supsetneq \mathrm{Ir}(M)^*$ とし $a \in M \setminus \mathrm{Ir}(M)^*$ をとります。

$M$ の無限下降列 $\{a_n \mid n \in \mathbb{N}\}$ で $a_n \in M \setminus \mathrm{Ir}(M)^*$ であるものを以下のように帰納的に定義することができます。

$a_0 = a$ とおきます。

$a_n \in M \setminus \mathrm{Ir}(M)^*$ に対して $a_n \notin \mathrm{Ir}(M)$ であるから $a_n = bc$ 、 $b \ne 1$ 、 $c \ne 1$ となる $b, c \in M$ が存在します。 $b, c \in \mathrm{Ir}(M)^*$ ならば $a_n \in \mathrm{Ir}(M)^*$ となりますが $a_n \notin \mathrm{Ir}(M)^*$ なので $b \notin \mathrm{Ir}(M)^*$ または $c \notin \mathrm{Ir}(M)^*$ となります。よってこのどちらかをとれば $a_{n+1} \notin \mathrm{Ir}(M)^*$ となる $a_{n+1}$ をとることができます。これを $a_{n+1}$ とおくと $a_n \gneq a_{n+1}$ となります。なぜなら $a_{n+1} = b$ のときを考えると、 $b = bc$ とすると $1 = c$ となって $c \ne 1$ に反するので $b \ne bc$ となるので、 $a_{n+1} = b \lneq bc = a_n$ となるためです。

以上で $M$ の無限下降列 $\{a_n \mid n \in \mathbb{N}\}$ を定義することができました。

$a_n \land a_m = a_{\max\{n,m\}}$ なので $\{a_n \mid n \in \mathbb{N}\}$ は最大公約数に関して閉じています。 $\mathrm{Min}(M)$ より $\min \{a_n \mid n \in \mathbb{N}\} = a_n$ が存在します。 $a_n \gneq a_{n+1}$ となって $a_n$ の最小性に矛盾。