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

$\mathrm{Min}(R)$ ならば $R = \mathrm{Ir}(R)^* \cup \{0\}$

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