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

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

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

エラトステネスのふるい(1)

一般の整域の場合

ここでは既約元の定義から「エラトステネスのふるい」を一般化したものを導くことを考えます。

 R を整域とします。

 a \in R ab = 1 となる  b \in R が存在するとき  R の単元と呼びます。 R の単元全体の集合を  R^\times と書きます。

 S = R \setminus ( R^\times \cup \{0\} ) とおきます。 a \in R は以下の条件を満たすとき  R の既約元と呼びます。

  • (1)  a \in S
  • (2) 任意の  b, c \in R に対して  a = bc ならば  b \in R^\times または  c \in R^\times

 R の部分集合  X Y に対して  \{ xy \mid x \in X, y \in Y \} XY と書くことにします。 XX X^2 と書くことにします。

 b \notin R^\times c \notin R^\times とすると  bc \in (S \cup \{0\})(S \cup \{0\}) = S^2 \cup \{0\} となります。よって条件(2)は  a \in R \setminus (S^2 \cup \{0\}) と同値となります。よって  a が既約元であることは  a \in S \setminus S^2 と同値となるので、 R の既約元全体を  P とすると  P = S \setminus S^2 となります。

 f: S \to \mathbb{N} を以下で述べるような条件(S2)、(S3)、(S4)を満たす写像とします。 S の部分集合の列  P_0, P_1, P_2, \cdots

  •  P_0 = \varnothing
  •  P_{n+1} = P_n \cup f^{-1}(\min f(S \setminus P_n R))

帰納的に定義します。このとき

  • (S1)  S \setminus P_n R \ne \varnothing

が成り立つとします( R = \mathbb{Z} のときは成り立ちます)。この条件(S1)により  P_0, P_1, P_2, \cdots を定義することができます。 m_{n} = \min f(S \setminus P_n R) とおきます。

 P_n \subseteq P_{n+1} より  P_n R \subseteq P_{n+1} R S \setminus P_n R \supseteq S \setminus P_{n+1} R f(S \setminus P_n R) \supseteq f(S \setminus P_{n+1} R) \min f(S \setminus P_n R) \le \min f(S \setminus P_{n+1}) R m_{n+1} \le m_{n+2} となります。

 m_{n+1} = m_{n+2} とすると  m_{n+1} = m_{n+2} \in f(S \setminus P_{n+1} R) なので  m_{n+1} = f(a) a \in S \setminus P_{n+1} R となる  a が存在します。 m_{n+1} = f(a) より  a \in f^{-1}(m_{n+1}) \subseteq P_{n+1} となりますが、 a \in S \setminus P_{n+1} R より  a \notin P_{n+1} R \supseteq P_{n+1} \{1\} = P_{n+1} となるので、このようは  a は存在しません。

よって  m_0 < m_1 < m_2 < \cdots となります。

 f

  • (S2)  f^{-1}( \min f(S \setminus P_n R) ) \subseteq P

を満たすとします( R = \mathbb{Z} のときは  f を絶対値をとる写像とすると成り立ちます)。この条件(S2)により  P_{n+1} = f^{-1}(m_0) \cup f^{-1}(m_1) \cup \cdots \cup f^{-1}(m_n) \subseteq P となって  P^* = P_1 \cup P_2 \cup P_3 \cup \cdots とおくと  P^* \subseteq P が成り立ちます。

 f

  • (S3)  a \in S, \ b \in R, \ f(a) \le f(b) \implies b \in S
  • (S4)   a \in R, \ m_n < f(a) \implies a \notin P_{n+1}

を満たすとします( R = \mathbb{Z} f を絶対値をとる写像とすると成り立ちます)。

 a \in R m_n < f(a) < m_{n+1} とすると  f(a) \notin f(S \setminus P_{n+1} R) となります。 a \notin S \setminus P_{n+1} R となり (S3)より  a \in S となるので  a \in P_{n+1} R \subseteq P_{n+1} \cup P_{n+1} S \subseteq P_{n+1} \cup S^2 となります。(S4)より  a \notin P_{n+1} となるので  a \in S^2 a \notin P となります。よって  f(P) \subseteq \{m_0, m_1, m_2, \cdots \} となって  P \subseteq f^{-1}(\{m_0, m_1, m_2, \cdots \}) =P^* となります。

よって  P = P^* = P_1 \cup P_2 \cup P_3 \cup \cdots となります。