エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

多重集合・自由可換モノイド(7)

演算が「多重集合・自由可換モノイド(2)」と同じようになったので書き方を戻すことにします。単項イデアル整域のイデアル全体の集合の作る半環について考えます。単項イデアル整域の素元分解が可能であることの説明を数式で書いてみたのですが、少し長くなりました。「一意性」については今後の記事で説明します。

 R単位元をもつ可換べき等半環とします。

 R は加法に関してべき等可換モノイドとなります(単位元  0)。

  •  (x + y) + z = x + (y + z) \ (\forall x, y, z \in R)
  •  x + y = y + x \ (\forall x, y \in R)
  •  0 + x = x + 0 = x \ (\forall x \in R)
  •  x + x = x \ (\forall x \in R)

 R は乗法に関して可換モノイドとなります(単位元  1)。

  •  (xy)z = x(yz) \ (\forall x, y, z \in R)
  •  xy = yx \ (\forall x, y \in R)
  •  1x = x1 = x \ (\forall x \in R)

 R は乗法の加法に対する分配法則が成り立ちます。

  •  (x + y)z = xz + yz \ (\forall x, y, z \in M)
  •  x(y + z) = xy + xz \ (\forall x, y, z \in M)

さらに以下の条件が成り立つとします。

  •  0 \ne 1
  •  1 + x = 1 \ (\forall x \in R)
  •  0x = 0 \ (\forall x \in R)
  • 任意の  x, y, d \in R に対して  xd = yd d \ne 0 ならば  x = y
  • 任意の  x, y \in R に対して  x + y = x ならば  z \in R が存在して  xz = y が成り立つ。この  z y/x と書く。

 R に順序  \le x \le y \iff x + y = x で定義します。 x \le y のとき  x y の約数、 y x の倍数と呼びます。 x \le y y \ge x とも書きます。 x \le y かつ  x \ne y のとき  x \lneq y x \ge y かつ  x \ne y のとき  x \gneq y と書きます。

ここでは  \land は「かつ」、 \lor は「または」の意味で使います。

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

 X \subseteq R Y \subseteq R に対して  X \cdot Y = \{ xy \mid x \in X, y \in Y\} S \subseteq R^2 に対して  \mathrm{Prod}(S) = \{ xy \mid \langle x, y \rangle \in S\} a \in R に対して  \mathrm{Prod}^{-1}(a) = \{\langle x, y \rangle \in R^2 \mid xy=a\} S \subseteq R に対して  \mathrm{Prod}^{-1}(S) = \bigcup_{a \in S} \mathrm{Prod}^{-1}(a) と定義します。 \langle x, y \rangle x, y の組を表します( (x, y) x, y で生成されたイデアルを表す場合があるのでここでは  \langle x, y \rangle と書きます)。

 a \in R に対して

  •  \{a \le \} = \{ x \in R \mid a \le x \}
  •  \{\le a \} = \{ x \in R \mid x \le a \}
  •  \{a \lneq \} = \{ x \in R \mid a \lneq x \}
  •  \{\lneq a \} = \{ x \in R \mid x \lneq a \}

と定義します。

 X \subseteq R Y \subseteq R に対して

  •  X \land Y = \{\langle x, y \rangle \in R^2 \mid x \in X \land y \in Y\}
  •  X \lor Y = \{\langle x, y \rangle \in R^2 \mid x \in X \lor y \in Y\}

と定義します。 X Y x, y に依存する部分集合  X(x,y) Y(x,y) のとき

  •  X(x,y) \land_{\langle x, y \rangle} Y(x,y) = \{\langle x, y \rangle \in R^2 \mid x \in X(x,y) \land y \in Y(x,y)\}
  •  X(x,y) \lor_{\langle x, y \rangle} Y(x,y) = \{\langle x, y \rangle \in R^2 \mid x \in X(x,y) \lor y \in Y(x,y)\}

と定義します。 X(x,y) = \{x \in R \mid P(x,y)\} Y(x,y) = \{y \in R \mid Q(x,y)\}( P(x,y) Q(x,y) x, y に関する条件)のとき

  •  X(x,y) \land_{\langle x, y \rangle} Y(x,y) = \{P(x,y)\} \land_{\langle x, y \rangle} \{Q(x,y)\}
  •  X(x,y) \lor_{\langle x, y \rangle} Y(x,y) = \{P(x,y)\} \lor_{\langle x, y \rangle} \{Q(x,y)\}

と書くことにします。

 X \subseteq R Y(x) \subseteq R に対して( Y(x) x \in R に依存する部分集合)、任意の  x \in R に対して  x \in Y(x) であることを  X \subseteq_x Y(x) と書くことにします。

 x \in R f: R \to R に対して、 f(x) x(x \mapsto f(x)) X \subseteq R f: R \to R に対して、 f(X)=\{f(x) \mid x \in X\} X(\{x \mapsto f(x)\}) と( x X の右側に)書くことにします。

  •  \mathrm{Pr}(R) = \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \}
  •  \mathrm{Ir}(R) = \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \}

が成り立ちます。

 \mathrm{Pr}(R) = \mathrm{Ir}(R)

[証明]
 \begin{eqnarray*}
 & & \mathrm{Pr}(R) \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{xy\le\} \lor_{\langle x, y \rangle} \{xy\le\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{xy \le x\} \lor_{\langle x, y \rangle} \{xy \le y\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{y \le 1\} \lor_{\langle x, y \rangle} \{x \le 1\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{\le 1\} \lor \{\le 1\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \} \\
 & = & \mathrm{Ir}(R)
\end{eqnarray*}
 \begin{eqnarray*}
 & & \mathrm{Ir}(R) \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) (\{\langle x, y \rangle \mapsto \langle p / (p + x), p + x \rangle\}) \subseteq \{1\} \lor \{1\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) (\{\langle x, y \rangle \mapsto \langle p + x, p + x \rangle\}) \subseteq \{p\} \lor \{1\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) (\{\langle x, y \rangle \mapsto \langle x, p + x \rangle\}) \subseteq \{p \le\} \lor \{1\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) (\{\langle x, y \rangle \mapsto \langle x, (p + x)y \rangle\}) \subseteq \{p \le\} \lor \{y\} \} \\
 & \subseteq & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) (\{\langle x, y \rangle \mapsto \langle x, y \rangle\}) \subseteq \{p \le\} \lor \{p \le\} \} \\
 & = & \{ p \in R \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & = & \mathrm{Pr}(R)
\end{eqnarray*}
[証明終わり]

 R の部分集合  S が生成する  R の乗法に関する部分モノイドを  S^* と書きます。

 X \subseteq R に対して  R \setminus X X^c S \subseteq R^2 に対して  R^2 \setminus S S^c と書きます。

 \mathrm{Prod}^{-1}( (\mathrm{Ir}(R)^* \cup \{0\})^c) \subseteq \mathrm{Prod}^{-1}({\mathrm{Ir}(R)^*}^c) \subseteq {\mathrm{Ir}(R)^*}^c \lor {\mathrm{Ir}(R)^*}^c

[証明]  X \subseteq R Y \subseteq R に対して、 \langle x, y \rangle \in \mathrm{Prod}^{-1}( (X \cdot Y)^c) とすると  xy \in (X \cdot Y)^c であるから  x \in X^c または  y \in Y^c となります。よって  \mathrm{Prod}^{-1}( (X \cdot Y)^c) \subseteq X^c \lor Y^c となります。

 S \subseteq R とすると  S^* \cdot S^* \subseteq S^* であるから  {S^*}^c \subseteq (S^* \cdot S^*)^c となり、よって  \mathrm{Prod}^{-1}({S^*}^c) \subseteq \mathrm{Prod}^{-1}( (S^* \cdot S^*)^c) \subseteq {S^*}^c \lor {S^*}^c が成り立ちます。

よって  \mathrm{Prod}^{-1}({\mathrm{Ir}(R)^*}^c) \subseteq {\mathrm{Ir}(R)^*}^c \lor {\mathrm{Ir}(R)^*}^c となって主張が成り立ちます。[証明終わり]

 \mathrm{Prod}^{-1}( (\mathrm{Ir}(R)^* \cup \{0\})^c) \subseteq \mathrm{Prod}^{-1}(\{0\}^c) \subseteq \{0\}^c \land \{0\}^c

[証明]  0x = x0 = 0 より  \mathrm{Prod}(\{0\} \lor \{0\}) \subseteq \{0\} となります。よって
 \{0\}^c \subseteq \mathrm{Prod}(\{0\} \lor \{0\})^c \subseteq \mathrm{Prod}( (\{0\} \lor \{0\})^c) = \mathrm{Prod}(\{0\}^c \land \{0\}^c)
となって  \mathrm{Prod}^{-1}(\{0\}^c) \subseteq \{0\}^c \land \{0\}^c が成り立ちます。[証明終わり]

 X の任意の元が空集合ではない集合であるとき、 X の任意の元から一つずつ元を取り出した集合を  X (\{\ni\}) と書くことにします。 (\{\ni\}) (選択関数)は  X に右側に書くことにします。 X空集合ではない集合であるとき、 X の一つの元を  X (\ni) と(右側に)書くことにします。

 (\mathrm{Ir}(R)^* \cup \{0\})^c \subseteq \{ a \in R \mid \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\}) \ne \varnothing \}

[証明]
 \begin{eqnarray*}
 & & (\mathrm{Ir}(R)^* \cup \{0\})^c \subseteq \mathrm{Ir}(R)^c \\
 & = & \{ a \in R \mid \mathrm{Prod}^{-1}(a) \not\subseteq \{1\} \lor \{1\} \} \\
 & = & \{ a \in R \mid \mathrm{Prod}^{-1}(a) \cap (\{1\}^c \land \{1\}^c) \ne \varnothing \} \\
 & \subseteq & \{ a \in R \mid \mathrm{Prod}^{-1}(a) \cap (\{x \ne 1 \land xy=a\} \land_{\langle x,y \rangle} \{y \ne 1 \land xy=a\}) \ne \varnothing \} \\
 & \subseteq & \{ a \in R \mid \mathrm{Prod}^{-1}(a) \cap (\{y \ne a \land y \le a\} \land_{\langle x,y \rangle} \{x \ne a \land x \le a\}) \ne \varnothing \} \\
 & = & \{ a \in R \mid \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\}) \ne \varnothing \} \\
\end{eqnarray*}
[証明終わり]

 S R の部分集合とします。 d: S \to S で任意の  x \in S に対して  x \gneq d(x) が成り立つものの全体を  \mathrm{Descr}(S) とします。

  •  \mathrm{Descr}(S) = \{ d: S \to S \mid x \gneq d(x) (\forall x \in S)\}

 s \in S d \in \mathrm{Descr}(S) の組  \langle s, d \rangle の全体を  \mathrm{Desc}(S) とします。

  •  \mathrm{Desc}(S) = S \times \mathrm{Descr}(S)
 \mathrm{Descr}(R \setminus (\mathrm{Ir}(R)^* \cup \{0\})) \ne \varnothing

[証明]
 (\mathrm{Ir}(R)^* \cup \{0\})^c (\{a \mapsto \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\})\}) の任意の元は空集合ではありません。よって
 \begin{eqnarray*}
 & & (\mathrm{Ir}(R)^* \cup \{0\})^c (\{a \mapsto \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\})\}) (\{\ni\}) \\
 & \subseteq & ({\mathrm{Ir}(R)^*}^c \lor {\mathrm{Ir}(R)^*}^c) \cap (\{0\}^c \land \{0\}^c) \cap (\{\lneq a\} \land \{\lneq a\})
\end{eqnarray*}
が成り立ちます。よって
 \begin{eqnarray*}
 & & (\mathrm{Ir}(R)^* \cup \{0\})^c (\{a \mapsto \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\})\}) (\{\ni\}) \\
 & & (\{\langle x, y \rangle \mapsto \{ x, y \} \cap {\mathrm{Ir}(R)^*}^c\}) (\{\ni\}) \\
 & \subseteq_a & (\mathrm{Ir}(R)^* \cup \{0\})^c \cap \{ \lneq a\}
\end{eqnarray*}
が成り立ちます。

 d: R \setminus (\mathrm{Ir}(R)^* \cup \{0\}) \to R \setminus (\mathrm{Ir}(R)^* \cup \{0\})
 \begin{eqnarray*}
d(a) & = & a (a \mapsto \mathrm{Prod}^{-1}(a) \cap (\{\lneq a\} \land \{\lneq a\})) (\ni) \\
 & & (\langle x, y \rangle \mapsto \{ x, y \} \cap {\mathrm{Ir}(R)^*}^c) (\ni)
\end{eqnarray*}
と定義すると、 d \in \mathrm{Descr}(R \setminus (\mathrm{Ir}(R)^* \cup \{0\})) となって  \mathrm{Descr}(R \setminus (\mathrm{Ir}(R)^* \cup \{0\})) \ne \varnothing となります。[証明終わり]

 R の任意の部分集合  S に対して  \mathrm{Desc}(S) = \varnothing であるという条件を  \mathrm{Min}(R) とします。

多重集合・自由可換モノイド(6)

「数学ではできるがコンピューターではできないこと」、「コンピューターではできるが数学ではできないこと」があると考えられていると、私の感想ですが、思います。これらは実際にできないということではなく、それを記述する方法がないのではないかと、私の感想ですが、思います。ここではその方法を考えていきます。

素因数分解の「可能性」と「一意性」について多重集合を「コンピューターの記法」で記述することを考えていたのですが、素因数分解の「可能性」については多重集合は使わなくてもよいので数式で書くことにします。

ここでは単項イデアル整域のイデアル全体の集合の積と最大公約数の演算を考えます。前回の説明では条件が不足していたので追加します。

 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)
  • 任意の  x, y \in M に対して  x \land y = x ならば  z \in M が存在して  xz = y が成り立つ。この  z y/x と書く。(これを追加)

が成り立つとします。

 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) の元を既約元と呼びます。

 a \in M に対して  \mathrm{Prod}^{-1}(a) = \{\langle x, y \rangle \in M^2 \mid xy=a\} S \subseteq M に対して  \mathrm{Prod}^{-1}(S) = \bigcup_{a \in S} \mathrm{Prod}^{-1}(a) と定義します。

 a \in M に対して

  •  \{a \le \} = \{ x \in M \mid a \le x \}
  •  \{\le a \} = \{ x \in M \mid x \le a \}

と定義します。

 X \subseteq M Y \subseteq M に対して

  •  X \times Y = \{\langle x, y \rangle \in M^2 \mid x \in X, \ y \in Y\}
  •  X \lor Y = \{\langle x, y \rangle \in M^2 \mid x \in X \lor y \in Y\}

と定義します。

 X \subseteq M Y(x) \subseteq M に対して( Y(x) x \in M に依存する部分集合)、任意の  x \in M に対して  x \in Y(x) であることを  X \subseteq_x Y(x) と書くことにします。

 X \subseteq M f: M \to M に対して、 f(X) X(x \mapsto f(x)) と書くことにします。

  •  \mathrm{Pr}(M) = \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \}
  •  \mathrm{Ir}(M) = \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \}

が成り立ちます。

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

[証明]
 \begin{eqnarray*}
 & & \mathrm{Pr}(M) \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq_{\langle x, y \rangle} \{xy\le\} \lor \{xy\le\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq_{\langle x, y \rangle} \{x \in M \mid xy \le x\} \lor \{y \in M \mid xy \le y\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq_{\langle x, y \rangle} \{x \in M \mid xy \le y\} \lor \{y \in M \mid xy \le x\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq \{\le 1\} \lor \{\le 1\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \} \\
 & = & \mathrm{Ir}(M)
\end{eqnarray*}
 \begin{eqnarray*}
 & & \mathrm{Ir}(M) \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(p) \subseteq \{1\} \lor \{1\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) (\langle x, y \rangle \mapsto \langle p / (p \land x), p \land x \rangle) \subseteq \{1\} \lor \{1\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) (\langle x, y \rangle \mapsto \langle p \land x, p \land x \rangle) \subseteq \{p\} \lor \{1\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) (\langle x, y \rangle \mapsto \langle x, p \land x \rangle) \subseteq \{p \le\} \lor \{1\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) (\langle x, y \rangle \mapsto \langle x, (p \land x)y \rangle) \subseteq \{p \le\} \lor \{y\} \} \\
 & \subseteq & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) (\langle x, y \rangle \mapsto \langle x, y \rangle) \subseteq \{p \le\} \lor \{p \le\} \} \\
 & = & \{ p \in M \mid \mathrm{Prod}^{-1}(\{p\le\}) \subseteq \{p\le\} \lor \{p\le\} \} \\
 & = & \mathrm{Pr}(M)
\end{eqnarray*}
[証明終わり]

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

 S M の部分集合とします。 d: S \to S で任意の  x \in S に対して  x \gneq d(x) が成り立つものの全体を  \mathrm{Descr}(S) とします。

  •  \mathrm{Descr}(S) = \{ d: S \to S \mid x \gneq d(x) (\forall x \in S)\}

 s \in S d \in \mathrm{Descr}(S) の組  \langle s, d \rangle の全体を  \mathrm{Desc}(S) とします。

  •  \mathrm{Desc}(S) = S \times \mathrm{Descr}(S)
 \mathrm{Descr}(M \setminus \mathrm{Ir}(M)^*) \ne \varnothing

[証明]  d: M \setminus \mathrm{Ir}(M)^* \to M \setminus \mathrm{Ir}(M)^* を以下のように定義します。

 x \in M \setminus \mathrm{Ir}(M)^* をとると、 x \notin \mathrm{Ir}(M) であるから  x = yz y \ne 1 z \ne 1 となる  y, z \in M が存在します。 y, z \in \mathrm{Ir}(M)^* ならば  x \in \mathrm{Ir}(M)^* となりますが  x \notin \mathrm{Ir}(M)^* なので  y \notin \mathrm{Ir}(M)^* または  z \notin \mathrm{Ir}(M)^* となります。よってこのどちらかを  d(x) とすることによって  d(x) \notin \mathrm{Ir}(M)^* とすることができます。また  x \gneq y x \gneq z なので  x \gneq d(x) となります。

 d \in \mathrm{Descr}(M \setminus \mathrm{Ir}(M)^*) なので  \mathrm{Descr}(M \setminus \mathrm{Ir}(M)^*) \ne \varnothing となります。[証明終わり]

 M の任意の部分集合  S に対して  \mathrm{Desc}(S) = \varnothing であるという条件を  \mathrm{Min}(M) とします。

多重集合・自由可換モノイド(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)^* が成り立ちます。[証明終わり]

多重集合・自由可換モノイド(4)

「単項イデアル整域では既約元は素元である」ということの証明を書いていなかったので付け加えます。

以下の条件を考えます。

 \mathrm{Gcd}(M):  M の任意の元  x, y の最大公約数  x \land y が存在する(ここでは  \land は最大公約数を表すとします)。

  •  x \land y \le x, \ x \land y \le y \ (\forall x, y \in M)
  •  z \le x, \ z \le y \implies  z \le x \land y \ (\forall x, y, z \in M)
  •  x \land y = y \land x \ (\forall x, y \in M)
  •  (x \land y) \land z = x \land (y \land z) \ (\forall x, y, z \in M)
  •  x \land x = x \ (\forall x \in M)
  •  1 \land x = 1 \ (\forall x \in M)
  •  (x \land y) z = xz \land yz \ (\forall x, y, z \in M)

が成り立つとします。

 \mathrm{Gcd}(M) \implies \mathrm{Pr}(M) = \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) となります。[証明終わり]

さらに以下の条件を考えます。

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

多重集合・自由可換モノイド(3)

 M = \overline{R} \setminus \overline{0} とおいて書き直します。

 M を可換モノイドとします。

  •  (xy)z = x(yz) \ (\forall x, y, z \in M)
  •  1x = x \ (\forall x \in M)
  •  xy = yx \ (\forall x, y \in M)

 M は簡約可能とします。

  •  xz = yz \implies x = y \ (\forall x, y, z \in M)

 M は順序をもちます。

  •  x \le x \ (\forall x \in M)
  •  x \le y \land y \le z \implies x \le z \ (\forall x, y, z \in M)
  •  x \le y \land y \le x \implies x = y \ (\forall x, y \in M)

積は順序を保存します。

  •  x \le y \implies xz \le yz \ (\forall x, y, z \in M)

 1 は最小元となります。

  •  1 \le x \ (\forall x \in M)

このような代数的構造の名前は何かありそうですが、調べてみましたが見つからないのでこのまま進めます。

 \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) \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) が生成する  M の部分モノイドを  \mathrm{Pr}(M)^* \mathrm{Ir}(M) が生成する  M の部分モノイドを  \mathrm{Ir}(M)^* とおきます。

 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 の無限下降列と呼びます。 M の無限下降列の全体を  \mathrm{Desc}(M) とします。

 \mathrm{Desc}(M) = \varnothing \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 となるためです。

よって  \mathrm{Desc}(M) \ne \varnothing となります。[証明終わり]

多重集合・自由可換モノイド(2)

エレファントな整数論(13)の証明が間違っていたので書き直します。

整域  R の素元全体の集合を  \mathrm{Pr}(R)、既約元全体の集合を  \mathrm{Ir}(R) とします。

 Rイデアル  Ra ( a で生成された単項イデアル)を  \overline{a} と書きます。 X \subseteq R に対して  \{\overline{x} \mid x \in X\} \overline{X} と書きます。 Rイデアル全体の集合を  \mathrm{Ideal}(R) とおきます。 \{0\} 0 と書きます。

 \overline{\mathrm{Pr}(R)} \overline{\mathrm{Ir}(R)} によって( \overline{R} の乗法によって)生成されたモノイドをそれぞれ  \overline{\mathrm{Pr}(R)}^* \overline{\mathrm{Ir}(R)}^* とおきます。

 \overline{R} = \overline{\mathrm{Pr}(R)}^* \cup \overline{0} のとき  R を一意分解整域と呼びます。

 \mathrm{Ideal}(R) = \overline{R} のとき  R を単項イデアル整域と呼びます。

 \overline{\mathrm{Pr}(R)} \subseteq \overline{\mathrm{Ir}(R)}

[証明]
 \begin{eqnarray*}
\overline{p} \in \overline{\mathrm{Pr}(R)} 
 & \iff & \bigl[ \ \overline{a}\overline{b} \subseteq \overline{p} \implies \overline{a} \subseteq \overline{p} \lor \overline{b} \subseteq \overline{p} \ \bigr] \\
 & \implies & \bigl[ \ \overline{a}\overline{b} = \overline{p} \implies \overline{a} \subseteq \overline{a}\overline{b} \lor \overline{b} \subseteq \overline{a}\overline{b} \ \bigr] \\
 & \iff & \bigl[ \ \overline{a}\overline{b} = \overline{p} \implies \overline{b} = \overline{1} \lor \overline{a} = \overline{1} \ \bigr] \\
 & \iff & \overline{p} \in \overline{\mathrm{Ir}(R)}
\end{eqnarray*}
[証明終わり]

 \overline{R} = \overline{\mathrm{Pr}(R)}^* \cup \overline{0} \implies \overline{\mathrm{Pr}(R)} = \overline{\mathrm{Ir}(R)}

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

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

 \overline{p} \in \overline{\mathrm{Ir}(R)} よりある  \overline{q_i} 以外は  \overline{1} となります。

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

 \overline{\mathrm{Pr}(R)} \subseteq \overline{\mathrm{Ir}(R)} より  \overline{\mathrm{Pr}(R)} = \overline{\mathrm{Ir}(R)} となります。[証明終わり]

任意の自然数  n に対して  I_n \in \mathrm{Ideal}(R) が定義されて任意の自然数  n に対して  I_n \subsetneq I_{n+1} であるとき、イデアルの列  \{I_n \mid n \in \mathbb{N}\}イデアルの無限上昇列と呼びます。 Rイデアルの無限上昇列の全体を  \mathrm{Asc}(R) とします。 Rイデアルの無限上昇列が存在しないとき( \mathrm{Asc}(R) = \varnothing のとき)  R はネーター的であるといいます。

 \mathrm{Ideal}(R) = \overline{R} \implies \mathrm{Asc}(R) = \varnothing

[証明]  \mathrm{Ideal}(R) = \overline{R} とし、 \mathrm{Asc}(R) \ne \varnothing とします。 \{I_n \mid n \in \mathbb{N}\}イデアルの無限上昇列とします。 I = \bigcup_{n \in \mathbb{N}} I_n とおくと  I Rイデアルとなります。 I \in \mathrm{Ideal}(R) = \overline{R} より  I = \overline{a} となる  \overline{a} \in \overline{R} が存在します。 a \in I_n となる  n \in \mathbb{N} が存在するので  I \subseteq I_n \subsetneq I_{n+1} \subseteq I となって矛盾。

よって  \mathrm{Asc}(R) = \varnothing となります。[証明終わり]

 \mathrm{Asc}(R) = \varnothing \implies \overline{R} = \overline{\mathrm{Ir}(R)}^* \cup \overline{0}

[証明]  \overline{R} \supsetneq \overline{\mathrm{Ir}(R)}^* \cup \overline{0} とし  \overline{a} \in \overline{R} \setminus \left( \overline{\mathrm{Ir}(R)}^* \cup \overline{0} \right) をとります。

 Rイデアルの無限上昇列  \{\overline{a_n} \mid n \in \mathbb{N}\} \overline{a_n} \in \overline{R} \setminus \left( \overline{\mathrm{Ir}(R)}^* \cup \overline{0} \right) であるものを以下のように帰納的に定義することができます。

 \overline{a_0} = \overline{a} とおきます。

 \overline{a_n} \in \overline{R} \setminus \left( \overline{\mathrm{Ir}(R)}^* \cup \overline{0} \right) に対して  \overline{a_n} \notin \overline{\mathrm{Ir}(R)} であるから  \overline{a_n} = \overline{b}\overline{c} \overline{b} \ne \overline{1} \overline{c} \ne \overline{1} となる  \overline{b}, \overline{c} \in \overline{R} が存在します。 \overline{b}, \overline{c} \in \overline{\mathrm{Ir}(R)}^* ならば  \overline{a_n} \in \overline{\mathrm{Ir}(R)}^* となりますが  \overline{a_n} \notin \overline{\mathrm{Ir}(R)}^* なので  \overline{b} \notin \overline{\mathrm{Ir}(R)}^* または  \overline{c} \notin \overline{\mathrm{Ir}(R)}^* となります。よってこのどちらかをとれば  \overline{a_{n+1}} \notin \overline{\mathrm{Ir}(R)}^* となる  \overline{a_{n+1}} をとることができます。これを  \overline{a_{n+1}} とおきます。

よって  \mathrm{Asc}(R) \ne \varnothing となります。[証明終わり]

中間報告(12)

クロージャーの調査

クロージャーの調査」では、以下のようなことを考えていく予定です。

関数プログラミングのデータ(クロージャーを含んでも良い)の代数的構造を「無限関数プログラミングデータ」とします。

次に、クロージャーの呼び出しの深さが有限のある決まった回数であるものを考えます。この代数的構造を「有限関数プログラミングデータ」とします。

このデータからクロージャーを取り除いた代数的構造を「有限関数的代数」します。

「有限関数的代数」の多項式の極限のような極限を考えます。これを「無限関数的代数」とします。

「無限関数的代数」によって「無限関数プログラミングデータ」を表すことを考えています。

現在はクロージャーを含む関数型のプログラミング言語で、入出力を行う方法を検討しています。これを拡張して「無限関数的代数」によってこのプログラミング言語を表すことを考えています。

多重集合などを表すプログラム

「エレファントな整数論」では多重集合を数式で表す方法を考えていましたが、数式で表すことはまだできていません。「多重集合・自由可換モノイド」では、多重集合は順序には依存しないので、順序に依存しない記法を考えていましたが、数式で記述するのは難しいので、プログラムで表すことを考えています。

また、素因数分解の一意性についてもプログラムで表すことはできないかと考えています。

群論の計算」では代数方程式の代数的解法を多項式の変形で表す方法を考えていましたが、これもできていません。また、代数学の基本定理、対称式の基本定理も多項式の変形で表そうと考えていましたが、これもできていません。これらもプログラムで表すことはできないかと考えています。また、群のいろいろな定理もプログラムで表すことはできないかと考えています。

「エレファントな線形代数」では、連立1次方程式は方程式の集合なので方程式の順序には依存しないので、方程式の順序に依存しない記法を考えていましたが、まだできていません。これもプログラムで表すことはできないかと考えています。

多重集合や通常の部分集合の順序に依存しない記法は、多重集合などに関する対称性と考えることができます。これをプログラムで表すことを考えていきたいと思います。

多項式の変形については、数式処理システムのようなもので書けないか考えていきたいと思います。

現在できていること

目的としていることには到達していないものも多いのですが、部分的にできているところもあって、どこができている部分なのかはっきり書いていないこともあるので、その部分を書いていきたいと思います。以下のようなところです。

多重集合などに関する文献