多重集合・自由可換モノイド(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)$ とします。

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

[証明] $\mathrm{Min}(M)$ とすると $\mathrm{Desc}(M \setminus \mathrm{Ir}(M)^*) = \varnothing$ となります。 $\mathrm{Descr}(M \setminus \mathrm{Ir}(M)^*) \ne \varnothing$ であることから $M \setminus \mathrm{Ir}(M)^* = \varnothing$ となります。よって $M = \mathrm{Ir}(M)^*$ が成り立ちます。[証明終わり]