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

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

多重集合・自由可換モノイド(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 の最小性に矛盾。

よって  M = \mathrm{Ir}(M)^* が成り立ちます。[証明終わり]