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

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

エレファントな整数論(16)

自由生成可換モノイド

可換モノイド  M (演算を  + と書きます)の部分集合  X は以下の条件 (F1) を満たすとします。

(F1)

 m, n \ge 1 x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n \in X x_1 + x_2 + \cdots + x_m = y_1 + y_2 + \cdots + y_n ならば、任意の  i \in \{1, 2, \cdots, m\} に対して  j \in \{1, 2, \cdots, n\} が存在して、 x_i = y_j となって、 x_1, x_2, \cdots , x_m から  x_i を除いたものを  x'_1, x'_2, \cdots , x'_{m-1} y_1, y_2, \cdots , y_n から  y_j を除いたものを  y'_1, y'_2, \cdots , y'_{n-1} とすると、
 x'_1 + x'_2 + \cdots + x'_{m-1} = y'_1 + y'_2 + \cdots + y'_{n-1}
となります。

可換モノイド  M の部分集合  X が (F1) を満たすならば以下の (F2) を満たします。

 x_1, x_2, \cdots , x_n \in X a_1, a_2, \cdots , a_n, b_1, b_2, \cdots , b_n \in \mathbb{N} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + b_n x_n ならば、任意の  i \in \{1, 2, \cdots, n\} に対して  a_i \le b_i となり、 c \le a_i に対して
 a_1 x_1 + a_2 x_2 + \cdots + (a_i - c) x_i + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + (b_i - c) x_i + \cdots + b_n x_n
となります。

[証明]  a_i = 0 のときは主張は成り立っています。

 a_i > 0 とすると (F1) より  b_i > 0 a_1 x_1 + a_2 x_2 + \cdots + (a_i - 1) x_i + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + (b_i - 1) x_i + \cdots + b_n x_n となります。

これを繰り返すと主張が成り立ちます。[証明終わり]

可換モノイド  M の部分集合  X が (F2) を満たすならば以下の (F3) を満たします。

 x_1, x_2, \cdots , x_n \in X a_1, a_2, \cdots , a_n, b_1, b_2, \cdots , b_n \in \mathbb{N} a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b_1 x_1 + b_2 x_2 + \cdots + b_n x_n ならば、任意の  i \in \{1, 2, \cdots, n\} に対して  a_i = b_i となります。

[証明] (F2) より任意の  i \in \{1, 2, \cdots, n\} に対して  a_i \le b_i となります。左辺と右辺を入れ替えると  a_i \ge b_i となり  a_i = b_i となります。[証明終わり]

 \mathbb{N}[(X)] を、 X から  \mathbb{N} への写像  f X_f = \{ x \in X \mid f(x) \ne 0 \} が有限集合であるもの全体の集合とすると、 \mathbb{N}[(X)]写像の加法に関して可換モノイドとなります。

(F4)  M X で生成された可換モノイドで (F3) を満たすならば、モノイドの同型  \bar{\varphi}: \mathbb{N}[(X)] \to M が存在します。

[証明]  \varphi: X \to M を包含写像( x \in X x \in M を対応させる写像)とします。 f \in \mathbb{N}[(X)] X から  \mathbb{N} への写像 X_f = \{ x \in X \mid f(x) \ne 0 \} が有限集合であるものとなります。 X_f = \{ x_1, x_2, \cdots, x_n \} とします。 \bar{\varphi}(f) = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n) と定義します。この定義は  X_f を含む任意の有限集合で定義しても同じものとなります。よって  f, g \in \mathbb{N}[(X)] に対して、 X_{f+g} のかわりに  X_f \cup X_g を含むある有限集合  X' で定義しても同じものになり、 X_f のかわりに  X' としても  X_g のかわりに  X' としても同じものになります。

よって  \bar{\varphi}(f + g) = \bar{\varphi}(f) + \bar{\varphi}(g) が成り立つので  \bar{\varphi} はモノイドの準同型となります。

 \bar{\varphi}(f) = \bar{\varphi}(g) とします。 X_f \cup X_g \subseteq \{x_1, x_2, \cdots, x_n \} とします。 \bar{\varphi}(f) = f(x_1) \varphi(x_1) + f(x_2) \varphi(x_2) + \cdots + f(x_n) \varphi(x_n) \bar{\varphi}(g) = g(x_1) \varphi(x_1) + g(x_2) \varphi(x_2) + \cdots + g(x_n) \varphi(x_n) であるから (F3) より任意の  x_i に対して  f(x_i) = g(x_i) となって、 f = g となります。よって  \bar{\varphi}単射となります。

 M X で生成されるので  \bar{\varphi}全射となります。

よって  \bar{\varphi} はモノイドの同型となります。[証明終わり]

このような可換モノイドを自由生成可換モノイドと呼ぶことにします。

整数の素因数分解の一意性

整数全体の環は整域なので、以前に述べた整域に関する議論が成り立ちます。
 M = \{ P \mid P \ は有限個の素数の積で生成される単項イデアル \}
とおくと、 Mイデアルの乗法に関して自由生成可換モノイドとなります。

よって  m, n \ge 1 とし、 p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n素数 p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n とすると、 m = n であり、適当に並べ替えると任意の  1 \le i \le m に対して  p_i = q_i または  p_i = -q_i となります。

正の素数に限定した場合を考えると  m, n \ge 1 とし、 p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n を正の素数 p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n とすると、 m = n であり、適当に並べ替えると任意の  1 \le i \le m に対して  p_i = q_i となります。

自由生成可換モノイドに関する帰納法

 f \in \mathbb{N}[(X)] に対して  \displaystyle \#f = \sum_{x \in X} f(x) と定義すると、 \# : \mathbb{N}[(X)] \to \mathbb{N} はモノイドの準同型となります。 n \in \mathbb{N} に対して  X * n = \{ f \in \mathbb{N}[(X)] \mid \#f = n \} と定義します。すると  \mathbb{N}[(X)] = \displaystyle \bigcup_{n \in \mathbb{N}} (X * n) となります。よって  \{0\} \subseteq M \subseteq \mathbb{N}[(X)]

  • 任意の  n \in \mathbb{N} に対して  X * n \subseteq M ならば  X * (n+1) \subseteq M

であるならば  M = \mathbb{N}[(X)] となります。