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

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

エレファントな線形代数(2)

掃き出し法の順序に依存しない記法(2)

前回の議論では何が解となるのか明確には書いていなかったので、わかるように書き直したいと思います。

連立一次方程式
(*) \left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & \alpha_{11} x_1 + \alpha_{12} x_2 + \cdots + \alpha_{1n} x_n = \beta_1 \\ e_2(x_1, x_2, \cdots, x_n) & \iff & \alpha_{21} x_1 + \alpha_{22} x_2 + \cdots + \alpha_{2n} x_n = \beta_2 \\ \vdots & & \vdots \\ e_n(x_1, x_2, \cdots, x_n) & \iff & \alpha_{n1} x_1 + \alpha_{n2} x_2 + \cdots + \alpha_{nn} x_n = \beta_n \\ \end{matrix} \right.
を、有理数全体の体 \mathbb{Q} に \alpha_{11}, \cdots, \alpha_{1n}, \cdots, \alpha_{n1}, \cdots, \alpha_{nn}, \beta_1, \cdots, \beta_n を付け加えて拡大した体 K で考えます。逆行列を行列式で表すことができることから、連立一次方程式の解は K の元で表すことができます。

V = K^n、 U = \{u_1, u_2, \cdots, u_n\} を V の基底とします。

W = K^n とし、一次方程式 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b を (a_1, a_2, \cdots, a_n, b) \in W \times K と表します。一次方程式全体の集合を \mathcal{E} = W \times K とおきます。 \mathcal{E} は K 上のベクトル空間となります。

h: \mathcal{E} \times V \to \{0, 1\} ( 1 は「真」を、 0 は「偽」を表すとします)を、 e = (a_1, a_2, \cdots, a_n, b) \in \mathcal{E} と v = x_1 u_1 + x_2 u_2 + \cdots + x_n u_n \in V に対して、 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b のとき h(e, v) = 1、 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \ne b のとき h(e, v) = 0 とします。

i = 1, 2, \cdots, n に対して、 \mathcal{Q}^*_i = \{ r \in \mathcal{E} \mid h(r, u_i) = 1 \}、 \displaystyle \mathcal{Q}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{Q}^*_j、 \mathcal{R} = \mathcal{Q}_1 \cup \mathcal{Q}_2 \cup \cdots \cup \mathcal{Q}_n とおきます。

(1) 任意の e_1, e_2 \in \mathcal{E}、 i \in \{1, 2, \cdots, n\} に対して (e_1 + K e_2) \cap \mathcal{Q}^*_i = K e となる e \in \mathcal{E} が存在します。

[証明] e_1 を a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1、 e_2 を a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 とするとき、 e = e_1 - \cfrac{a_{1i}}{a_{2i}} e_2 は e(u_i) を満たします。[証明終わり]

e \in \mathcal{E} に対して S(e) = \{ v \in V \mid h(e, v) = 1 \}、 E \subseteq \mathcal{E} に対して \displaystyle S(E) = \bigcap_{e \in E} S(e) とします。 S(e)、 S(E) は V の部分空間となります。

S(E) = S(R) かつ R \subseteq \mathcal{R} となる R を E の解とします。このとき E \twoheadrightarrow R と書くことにします。 R は一意的にはなりませんがここではこの形で議論を進めます。

E_0 を連立一次方程式(*)とします。 U_0 = U とします。

E_i = E'_{i+1} + \{ e_i \}、 U_i = U_{i+1} + \{ v_i \} ( + は集合の直和)とします。

\displaystyle V_i = \sum_{u \in U_i} K u とおくと V_i = V_{i+1} \oplus K v_{i+1} ( \oplus はベクトル空間の直和)となります。

E''_i = \{ e \in E'_i + K e_i \mid h(e, v_i) = 1 \}
\displaystyle = \bigcup_{e' \in E'_i} \{ e \in e' + K e_i \mid h(e, v_i) = 1 \} とおきます。
E''_i の元の中から e \in \{ e \in e' + K e_i \mid h(e, v_i) = 1 \} で e \ne 0 であるものを一つずつ集めた集合を E_i とおきます。

\mathcal{R}^*_i = \{ r \in \mathcal{E} \mid h(r, v_i) = 1 \}、 \displaystyle \mathcal{R}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{R}^*_j とおきます。

(2) S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i)

[証明] e' \in E'_i をとると(1)より (e' + K e_i) \cap \bar{\mathcal{R}}_i = K e となる e \in \mathcal{E} が存在します。 a e = e' + c e_i となる a, c \in K が存在します。
h(e', v) = h(e_i, v) = 1 \iff h(e' + c e_i, v) = h(e_i, v) = 1 \iff h(ae, v) = h(e_i, v) = 1
より S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i) となります。[証明終わり]

(3) S(E_i) = S(E_{i+1}) \cap S(e_{i+1})

[証明] (2)より S(E_i) = S(E'_{i+1}) \cap S(e_{i+1}) = S(E_{i+1}) \cap S(e_{i+1}) となります。[証明終わり]

(4) E_{i} \subseteq \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_i

[証明] E_{i} の定義より E_{i} \subseteq \mathcal{R}^*_i となって E_{i}, E_{i+1}, \cdots \subseteq \mathcal{R}^*_i となるので成り立ちます。[証明終わり]

(5) E_{n-1} \subseteq \mathcal{R}

[証明] (4) り E_{n-1} \subseteq \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} となるので成り立ちます。[証明終わり]

(6) E_{i+1} \twoheadrightarrow R_{i+1}、 R_{i+1} = \{ r_{i+2}, \cdots, r_n \} ならば E_{i} \twoheadrightarrow R_{i}、 R_{i} = R_{i+1} + \{ r_{i+1} \} となる R_{i} が存在します。

[証明] S(E_{i+1}) = S(R_{i+1}) かつ R_{i+1} \subseteq \mathcal{R} とします。 E_i = E_{i+1} + \{ e_{i+1} \} であり、 r_{i+1} \in (e_{i+1} + V_{i+1}) \cap \mathcal{R}^*_{i+1} \cap \cdots \cap \mathcal{R}^*_{n-1} かつ r_{i+1} \ne 0 となる r_{i+1} が存在します。 R_i = R_{i+1} + \{ r_{i+1} \} とおくと S(E_{i}) = S(R_{i}) かつ R_{i} \subseteq \mathcal{R} となります。[証明終わり]

(7) E_{0} \twoheadrightarrow R_0 となる R_0 が存在します。

[証明] (6)より
\begin{eqnarray*} & & E_0 \twoheadrightarrow R_0 \mathop{となる} R_0 \mathop{が存在する} \\ & \Longleftarrow & E_1 \twoheadrightarrow R_1 \mathop{となる} R_1 \mathop{が存在する} \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & E_{n-1} \twoheadrightarrow R_{n-1} \mathop{となる} R_{n-1} \mathop{が存在する} \\ \end{eqnarray*}
となります。最後の項は(5)より R_{n-1} = E_{n-1} とおけば成り立ちます。[証明終わり]

エレファントな線形代数(1)

連立一次方程式

拡大された掃き出し法の記法

連立一次方程式
(*) \left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ e_2(x_1, x_2, \cdots, x_n) & \iff & a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \vdots & & \vdots \\ e_m(x_1, x_2, \cdots, x_n) & \iff & a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m \\ \end{matrix} \right.
を、 a_{11}, \cdots, a_{1n}, \cdots, a_{m1}, \cdots, a_{mn}, b_1, \cdots, b_m を文字と考えて、有理数全体の体 \mathbb{Q} に付け加えて拡大した体 K で考えます。「現代数学のエレファント」の記事でこの連立一次方程式を掃き出し法で解く方法を書こうとしましたが、記述が複雑になりすぎたため中断していました。ここではこの掃き出し法について、記述を簡単にすることを考えていきます。逆行列を行列式で表すことができることから、連立一次方程式の解は K の元で表すことができます。以下ではまず m = n の場合を考えます。

e'_i(x_1, x_2, \cdots, x_n) \iff e_i(x_1, x_2, \cdots, x_n) - \cfrac{a_{i1}}{a_{11}} e_1(x_1, x_2, \cdots, x_n) ( e_i(x_1, x_2, \cdots, x_n) の各項から e_1(x_1, x_2, \cdots, x_n) の各項の \cfrac{a_{i1}}{a_{11}} 倍を引いた方程式)とおくと
\left\{ \begin{matrix} e_1(x_1, x_2, \cdots, x_n) & \iff & a_{11} x_1 & + & a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ e'_2(x_1, x_2, \cdots, x_n) & \iff & & & a'_{22} x_2 + \cdots + a'_{2n} x_n = b'_2 \\ \vdots & & & & \vdots \\ e'_n(x_1, x_2, \cdots, x_n) & \iff & & & a'_{n2} x_2 + \cdots + a'_{nn} x_n = b'_n \\ \end{matrix} \right.
となります( a'_{ij} = a_{ij} - \cfrac{a_{i1}}{a_{11}} a_{1j}、 b'_{i} = b_{i} - \cfrac{a_{i1}}{a_{11}} b_{1})。

\left\{ \begin{matrix} e'_2(x_1, x_2, \cdots, x_n) & \iff & a'_{22} x_2 + \cdots + a'_{2n} x_n = b'_2 \\ \vdots & & \vdots \\ e'_n(x_1, x_2, \cdots, x_n) & \iff & a'_{n2} x_2 + \cdots + a'_{nn} x_n = b'_n \\ \end{matrix} \right.
を満たす (x_2, \cdots, x_n) と、 f_i: V_i \to K、 f_i(x_{i+1}, \cdots, x_n) = x_i が存在すると仮定します (i = 2, \cdots, n)。 n = 1 のときは成り立っています。

f_1: V_1 \to K を、 x_1 = f_1(x_{2}, \cdots, x_n) のとき a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 を満たすもの、
x_1 = f_1(x_{2}, \cdots, x_n) = - \left( \cfrac{a_{12}}{a_{11}} x_2 + \cdots + \cfrac{a_{1n}}{a_{11}} x_n \right) + \cfrac{b_{1}}{a_{11}}
とおくと、 (x_1, x_2, \cdots, x_n) は e_1(x_1, x_2, \cdots, x_n) を満たします。

また (x_1, x_2, \cdots, x_n) は e'_i(x_1, x_2, \cdots, x_n) を満たす (i = 2, \cdots, n)ので、
e_i(x_1, x_2, \cdots, x_n) \iff e'_i(x_1, x_2, \cdots, x_n) + \cfrac{a_{i1}}{a_{11}} e_1(x_1, x_2, \cdots, x_n)
を満たします (i = 2, \cdots, n)。

よって任意の i = 1, 2, \cdots, n に対して e_i(x_1, x_2, \cdots, x_n) となります。これは (x_1, x_2, \cdots, x_n) が連立一次方程式 (*) の解であることを表します。

掃き出し法の順序に依存しない記法

上記の手順を i = 1, 2, \cdots, n の順序に依存しない手順にすることを考えます。

V = K^n、 U = \{u_1, u_2, \cdots, u_n\} を V の基底とします。

一次方程式 e: V \times K \to \{0, 1\} ( 1 は「真」を、 0 は「偽」を表すとします)を、ある a_1, a_2, \cdots, a_n, b \in K に対して x_1 u_1 + x_2 u_2 + \cdots + x_n u_n \in V、 b \in K に a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b を対応させる写像とします。

一次方程式 e の解を S(e) = \{ v \in V \mid e(v) \}、一次方程式の有限集合 E の解を \displaystyle S(E) = \bigcap_{e \in E} S(e) とします。 S(e)、 S(E) は V の部分空間となります。

E = E_1 + \{e_1\} ( + は集合の直和)、 U = U_1 + \{v_1\} とします。 \displaystyle V_1 = \sum_{u \in U_1} K u とおくと V = V_1 \oplus K v_1 ( \oplus はベクトル空間の直和)となります。

任意の e \in E_1 に対して
e'(v) \iff e(v) + e_1(c_1v) \iff e'(v + K v_1)
となる c_1 \in K が存在します。ここで e(v) + e'(v') は e(v) の各項と e'(v') の各項を足した方程式、 V の部分集合 X に対して e(X) は任意の v \in X に対して e(v) であることを表すとします。 E'_1 を e' 全体の集合とします。

S(E_1) \cap S(e_1) = S(E'_1) \cap S(e_1)

[証明]
e(v) \land e_1(v) \iff ( e(v) + e_1(cv) ) \land e_1(v) \iff e'(v) \land e_1(v)
より成り立ちます。[証明終わり]

S(E'_1) = S(E'_1) + K v_1

[証明] 任意の e \in E_1 に対して e' \in e + Ke_1 が存在して任意の v \in V に対して
v \in S(e') \iff v + K v_1 \subseteq S(e') \iff v \in S(e') + K v_1
となります。よって
\displaystyle S(E'_1) = \bigcap_{e' \in E'_1} S(e') = \bigcap_{e' \in E'_1} (S(e') + K v_1) \supseteq S(E'_1) + K v_1
となって S(E'_1) = S(E'_1) + K v_1 となります。[証明終わり]

S(E'_1) \cap V_1 \ne \varnothing \implies (S(E'_1) + K v_1) \cap S(e_1) \ne \varnothing

[証明] U_1 = \{ v_2, \cdots, v_n \} とします。 i = 1, 2, \cdots, n に対して、 f_i: V \to K を f_i(v_i) =1、 i \ne j のとき f_i(v_j) =0 とします。任意の v \in V に対して v = f_1(v) v_1 + f_2(v) v_2 + \cdots + f_n(v) v_n となります。

e_1(v) を a_1 f_1(v) + a_2 f_2(v) + \cdots + a_n f_n(v) = b とします。 v' \in S(E'_1) \cap V_1 とし、 c = \cfrac{-(a_2 f_2(v') + \cdots + a_n f_n(v')) + b}{a_1}、 v = c v_1 + f_2(v') v_2 + \cdots + f_n(v') v_n とおきます。 a_1 f_1(v) = a_1 c = -(a_2 f_2(v') + \cdots + a_n f_n(v')) + b、 i = 2, \cdots, n に対して a_i f_i(v) = a_i f_i(v') となるので a_1 f_1(v) + a_2 f_2(v) + \cdots + a_n f_n(v) = b となり e_1(v) が成り立ちます。[証明終わり]

よって S(E'_1) \cap V_1 \ne \varnothing と仮定すると( n = 1 のときは成り立ちます)、
S(E) = S(E_1) \cap S(e_1) = S(E'_1) \cap S(e_1) = (S(E'_1) + K v_1) \cap S(e_1) \ne \varnothing
となります。

これは v \in S(E) に対して f_1(v), f_2(v), \cdots, f_n(v) が連立一次方程式 E の解となることを表します。

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

最後の式の書き方を少し変更します。

(8) \mathcal{P}, \mathcal{Q} を0個以上の有限個の正の素数からなる多重集合とするとき、 \prod \mathcal{P} = \prod \mathcal{Q} ならば \mathcal{P} = \mathcal{Q} となります。

[証明] \{| p |\} \le \mathcal{P} となる p が存在しないとすると \prod \mathcal{P} = 1 となります。 \prod \mathcal{P} = \prod \mathcal{Q} ならば \prod \mathcal{Q} = 1 となって \# \mathcal{Q} = 0 となるので \mathcal{P} = \mathcal{Q} となります。

\{| p |\} \le \mathcal{P} となる p が存在するならば、(7) より \{| p |\} \le \mathcal{Q} となります。 \mathcal{P}' = \mathcal{P} - \{| p |\}、 \mathcal{Q}' = \mathcal{Q} - \{| p |\} とおくと \prod \mathcal{P} = \prod \mathcal{Q} より \prod \mathcal{P}' = \prod \mathcal{Q}' となります。このとき \mathcal{P}' = \mathcal{Q}' と仮定すると、 \mathcal{P} = \mathcal{P}' + \{| p |\} = \mathcal{Q}' + \{| p |\} = \mathcal{Q} となります。

よって \mathcal{P} = \{| p_1, p_2, \cdots , p_m |\} とすると
\begin{eqnarray*} & & \left[ \ \prod \mathcal{P} = \prod \mathcal{Q} \implies \mathcal{P} = \mathcal{Q} \ \right] \\ & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \left[ \ \mathcal{P} =_\exists \mathcal{P}_1 + \{| p_1 |\} \land \prod \mathcal{P}_1 = \prod \mathcal{Q}_1 \implies \mathcal{P} = \mathcal{Q} \ \right] \\ & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \ \\ & & \mathcal{P}_1 \ne_\exists \mathcal{P}_2 + \{| p_2 |\} \lor \left[ \ \mathcal{P}_1 =_\exists \mathcal{P}_2 + \{| p_2 |\} \land \prod \mathcal{P}_2 = \prod \mathcal{Q}_2 \implies \mathcal{P}_1 = \mathcal{Q}_1 \ \right] \\ & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \mathcal{P}_1 \ne_\exists \mathcal{P}_2 + \{| p_2 |\} \lor \ \\ & & \mathcal{P}_2 \ne_\exists \mathcal{P}_3 + \{| p_3 |\} \lor \left[ \ \mathcal{P}_2 =_\exists \mathcal{P}_3 + \{| p_3 |\} \land \prod \mathcal{P}_3 = \prod \mathcal{Q}_3 \implies \mathcal{P}_2 = \mathcal{Q}_2 \ \right] \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & \mathcal{P} \ne_\exists \mathcal{P}_1 + \{| p_1 |\} \lor \cdots \lor \mathcal{P}_m \ne_\exists \mathcal{P}_{m+1} + \{| p_{m+1} |\} \end{eqnarray*}
となります。ここで \mathcal{X} \ne_\exists \mathcal{Y} + \{| x |\} は \mathcal{X} = \mathcal{Y} + \{| x |\} となる \mathcal{Y} と x が存在しないこと、 \mathcal{X} =_\exists \mathcal{Y} + \{| x |\} は \mathcal{X} = \mathcal{Y} + \{| x |\} となる \mathcal{Y} と x が存在することを表すとします。最後の項は \{| p |\} \le \mathcal{P}_m となる p が存在しない場合( \# \mathcal{P}_m = 0 の場合)なので成り立ちます。よって \prod \mathcal{P} = \prod \mathcal{Q} ならば \mathcal{P} = \mathcal{Q} となります。[証明終わり]

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

整数の素因数分解

整数 a \notin I = \{0, 1, -1\} が素数であることは

  • (1) a = bc ならば b = \pm 1 または c = \pm 1

であることと同値となります。

素数全体の集合を P とし、 f(a) を a の絶対値とします。

X_n = \{ a \in \mathbb{Z} \setminus I \mid f(a) \le n \} とおくと \displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n となります。

X, Y \subseteq \mathbb{Z} に対して XY = \{ xy \mid x \in X, y \in Y \}、 X^* = X \cup XX \cup XXX \cup \cdots と書くことにします。

(2) a \notin I ならば a は素数の積で表すことができます。

[証明] (1)より X_n \subseteq P \cup X_{n-1}^* となります。よって
\begin{eqnarray*} X_n & \subseteq & P^* \cup P^* X_{n-1}^* \cup X_{n-1}^* \\ & \subseteq & P^* \cup P^*(P^* \cup X_{n-2}^* )^* \cup (P^* \cup X_{n-2}^* )^* \\ & \subseteq & P^* \cup P^* X_{n-2}^* \cup X_{n-2}^* \\ \end{eqnarray*}
となって、これを繰り返して X_n \subseteq P^* \cup P^* X_{1}^* \cup X_{1}^* \subseteq P^* となります。

よって \displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n = I \cup P^* となります。よって a \notin I ならば a は素数の積で表すことができます。[証明終わり]

整数の素因数分解の多重集合としての一意性

重複度を含めた集合を多重集合*1と呼びます。多重集合 \{| x_1, x_2, \cdots , x_m |\} とは、通常の集合とは異なり、 x_1, x_2, \cdots , x_m の中に重複するものがあったとき、その出現する回数が異なれば多重集合としては異なるものとするものです。

多重集合 \{| x_1, x_2, \cdots , x_m |\} と \{| y_1, y_2, \cdots , y_n |\} は全単射 g: \{1, 2, \cdots, m\} \to \{1, 2, \cdots, n\} が存在して任意の i \in \{1, 2, \cdots, m\} に対して x_i = y_{g(i)} であるとき \{| x_1, x_2, \cdots , x_m |\} = \{| y_1, y_2, \cdots , y_n |\} とします。

整数 a の倍数全体の集合を (a) とします。

  • (3) (a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p)

を満たす整数 p で p \notin \{0, 1, -1\} であるもの全体の集合を Q とします。

(4) Q \subseteq P

[証明]
\begin{eqnarray*} p \in Q & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ ab = p \implies a \in (ab) \lor b \in (ab) \ \bigr] \\ & \iff & \bigl[ \ ab = p \implies (b) = (1) \lor (a) = (1) \ \bigr] \\ & \iff & p \in P \end{eqnarray*}
[証明終わり]

(5) \mathbb{Z} = I \cup Q^*

[証明] (4) より Q に対しても (2) が成り立ちます。[証明終わり]

(6) P = Q

[証明] (5) より P = P \cap Q^* \subseteq Q となります。 [証明終わり]

(7) 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 ならば任意の i に対して j が存在して p_i = q_j となります。

[証明] (q_1 q_2 \cdots q_n) \subseteq (p_i) であり (6) より p_i \in Q なので (q_j) \subseteq (p_i) となる j が存在します。(1)より p_i = \pm q_j となります。[証明終わり]

多重集合 \mathcal{X} = \{| x_1, x_2, \cdots , x_m |\} と \mathcal{Y} = \{| y_1, y_2, \cdots , y_n |\} に対して

  • \{| x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n |\} を \mathcal{X} + \mathcal{Y} と書くことにします。
  • \mathcal{X} + \mathcal{Z} = \mathcal{Y} となる多重集合 \mathcal{Z} が存在するとき \mathcal{X} \le \mathcal{Y}、 \mathcal{Z} = \mathcal{Y} - \mathcal{X} と書くことにします。
  • m を \# \mathcal{X}と書くことにします。
  • \displaystyle \prod_{i=1}^m x_i を \displaystyle \prod \mathcal{X} と書くことにします。 \# \mathcal{X} = 0 のときは \displaystyle \prod \mathcal{X} = 1 とします。

\mathcal{Y} \le \mathcal{X} のとき (\mathcal{X} - \mathcal{Y}) + \mathcal{Y} = \mathcal{X} となります。

(8) \mathcal{P}, \mathcal{Q} を0個以上の有限個の正の素数からなる多重集合とするとき、 \prod \mathcal{P} = \prod \mathcal{Q} ならば \mathcal{P} = \mathcal{Q} となります。

[証明] \# \mathcal{P} = 0 とすると \prod \mathcal{P} = 1 となります。 \prod \mathcal{P} = \prod \mathcal{Q} ならば \prod \mathcal{Q} = 1 となって \# \mathcal{Q} = 0 となるので \mathcal{P} = \mathcal{Q} となります。

\# \mathcal{P} \ne 0 とすると \{| p |\} \le \mathcal{P} となる p が存在します。(7) より \{| p |\} \le \mathcal{Q} となります。 \mathcal{P}' = \mathcal{P} - \{| p |\}、 \mathcal{Q}' = \mathcal{Q} - \{| p |\} とおくと \prod \mathcal{P} = \prod \mathcal{Q} より \prod \mathcal{P}' = \prod \mathcal{Q}' となります。このとき \mathcal{P}' = \mathcal{Q}' と仮定すると、 \mathcal{P} = \mathcal{P}' + \{| p |\} = \mathcal{Q}' + \{| p |\} = \mathcal{Q} となります。

よって \mathcal{P} = \{| p_1, p_2, \cdots , p_m |\} とすると
\begin{eqnarray*} & & \left[ \ \prod \mathcal{P} = \prod \mathcal{Q} \implies \mathcal{P} = \mathcal{Q} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1 |\}) = \prod (\mathcal{Q} - \{| p_1 |\}) \implies \mathcal{P} - \{| p_1 |\} = \mathcal{Q} - \{| p_1 |\} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1, p_2 |\}) = \prod (\mathcal{Q} - \{| p_1, p_2 |\}) \implies \mathcal{P} - \{| p_1, p_2 |\} = \mathcal{Q} - \{| p_1, p_2 |\} \ \right] \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \mathcal{P}) = \prod (\mathcal{Q} - \mathcal{P}) \implies \mathcal{P} - \mathcal{P} = \mathcal{Q} - \mathcal{P} \ \right] \\ \end{eqnarray*}
となって、最後の項は \# \mathcal{P} = 0 の場合なので成り立ちます。よって \prod \mathcal{P} = \prod \mathcal{Q} ならば \mathcal{P} = \mathcal{Q} となります。[証明終わり]

*1:Wikipediaの多重集合の項を参考にします。多重集合の書き方はいろいろあるようですがここでは \{| \cdots |\} を採用します。 X の生成する自由可換モノイドとの関連についてリンクがありますが、リンク先は自由加群となっていてモノイドの場合については書かれていないようです。アーベル群の場合と同様の議論ができると考えられます。

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

整数の素数の積への分解

R を整域、 \langle R \rangle を R の単項イデアル全体の集合とします。 a \in R で生成された単項イデアルを (a) と書きます。 0 だけからなるイデアルを (0) と書き、イデアル (0) だけからなる集合を \langle 0 \rangle と書くことにします。

  • (E2) (a), (b) \in \langle R \rangle、 (a) \ne (0)、 (b) \ne (0) ならば f( (a) ) < f( (a)(b) )

(ユークリッド関数の条件(2)*1と同様の条件)を満たす f: \langle R \rangle \setminus \langle 0 \rangle \to \mathbb{N} が存在するとします*2。

R の素元全体の集合を X とします。 X によって( R の乗法によって)生成されたモノイドを P とおきます。 P の元で生成された単項イデアル全体の集合を \langle P \rangle とします。

このとき \langle R \rangle = \langle P \rangle \cup \langle 0 \rangle が成り立ちます。

[証明] \langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle) \ne \varnothing と仮定します。 m = \min \{ f( (a) ) \mid (a) \in \langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle) \} とし、 f( (a) ) = m となる (a) \in \langle R \rangle \setminus (\langle P \rangle \cup \langle 0 \rangle) をとります。

(a) \notin \langle P \rangle \cup \langle 0 \rangle なので (a) = (b)(c)、 (b) \ne (1)、 (c) \ne (1) となる (b), (c) \in \langle R \rangle が存在します*3。

(E2)より f( (b) ) < m、 f( (c) ) < m となります。 (b), (c) \in \langle P \rangle \cup \langle 0 \rangle となって、 (a) \ne (0) より (b) \ne (0)、 (c) \ne (0) なので (b), (c) \in \langle P \rangle となります。よって (a) = (b)(c) \in \langle P \rangle となって矛盾。

よって \langle R \rangle = \langle P \rangle \cup \langle 0 \rangle となります。[証明終わり]

R が整数全体の集合のとき、 f( (a) ) を a の絶対値とすると、(E2)を満たします。よって \langle R \rangle = \langle P \rangle \cup \langle 0 \rangle となります。すなわち任意の整数 a は a = p_1 p_2 \cdots p_n という素数の積で表すことができます。

整数全体の集合はユークリッド整域であることから単項イデアル整域となるので、単項イデアル整域の議論からも上記の結論が成り立ちます*4。

*1:「エレファントな整数論(9) - エレファント・コンピューティング調査報告」を参照

*2:Wikipediaによると条件(1)を満たす関数が存在すれば条件(1)と(2)を満たす関数が存在します

*3:「エレファントな整数論(15) - エレファント・コンピューティング調査報告」を参照

*4:「エレファントな整数論(13) - エレファント・コンピューティング調査報告」を参照

エレファントな整数論(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)] となります。

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

整域の元の素元への分解の一意性

(1) 整域 R の素元 p に対して、 (p) = (a_1 a_2 \cdots a_n) ならば、 (p) = (a_i) となる a_i が存在します。

[証明]
\begin{eqnarray*} p \ は素元 & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \ または \ (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ (a)(b) = (p) \implies (a) \subseteq (a)(b) \ または \ (b) \subseteq (a)(b) \ \bigr] \\ & \iff & \bigl[ \ (a)(b) = (p) \implies (b) = (1) \ または \ (a) = (1) \ \bigr] \\ \end{eqnarray*}
となるので、これを繰り返すとある a_i が存在して a_i 以外のすべての a_j に対して (a_j) = (1) となるので主張が成り立ちます。[証明終わり]

(2) 整域 R の素元 p に対して、 (p) \subseteq (a) ならば、 (p) = (a) または (a) = (1)

[証明] p = ab と書けるので、 (a) \ne (1) とすると(1)より (p) = (a) となります。[証明終わり]

(3) m, n \ge 1 とし、 p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n を整域 R の素元とします。 (p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n) ならば任意の i に対して j が存在して (p_i) = (q_j) となります。

[証明] (q_1 q_2 \cdots q_n) \subseteq (p_i) であり (p_i) は素イデアルなので (q_j) \subseteq (p_i) となる j が存在します。(2)より (p_i) = (q_j) となります。[証明終わり]

(4) m, n \ge 1 とし、 p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n を整域 R の素元とします。 (p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n) ならば、任意の i に対して p_1, p_2, \cdots , p_m の中から p_i を除いた p'_1, p'_2, \cdots , p'_{m-1} と q_1, q_2, \cdots , q_n の中の q'_1, q'_2, \cdots , q'_{n-1} が存在して (p'_1 p'_2 \cdots p'_{m-1}) = (q'_1 q'_2 \cdots q'_{n-1}) となります。

[証明] (3)より任意の i に対して j が存在して (p_i) = (q_j) となります。 q_1, q_2, \cdots , q_n から q_j を除いたものを q'_1, q'_2, \cdots , q'_{n-1} とします。 (p_i)(p'_1 p'_2 \cdots p'_{m-1}) = (q_j)(q'_1 q'_2 \cdots q'_{n-1}) となり、 R は整域なので (p'_1 p'_2 \cdots p'_{m-1}) = (q'_1 q'_2 \cdots q'_{n-1}) となります。[証明終わり]

(5) m, n \ge 1 とし、 p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n を整域 R の素元とします。 (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_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n は R の素元で、 (p_1 p_2 \cdots p_m) = (q_1 q_2 \cdots q_n) とします。

m = 1 のときは (p_1) = (q_1 q_2 \cdots q_n) となります。(1) より (p_1) = (q_i) となる i が存在して、その他の q_j はすべて (q_j) = (1) となりますが、 q_j は素元なので (q_j) = (1) となることはありません。よって n = 1 であり (p_1) = (q_1) となります。

m \gt 1 として、 m より小さい場合は主張が成り立っているとします。(3) より (q_i) = (p_1) となる i が存在します。番号を付け替えてこの q_i を q_1 とします。

(4)より (p_2 \cdots p_m) = (q_2 \cdots q_n) となります。帰納法の仮定より m = n であり、適当に並べ替えると任意の 2 \le i \le m に対して (p_i) = (q_i) となります。したがって主張が成り立ちます。[証明終わり]

整域 R の単項イデアル全体の集合はイデアルの乗法に関して可換モノイドとなります。