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

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

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

「不等式の方法」で証明を書いていこうと思いますが、その前に必要なことを「集合と位相」に従って書いておきます。

集合と写像

 f: C \to Z A, B \subseteq C X, Y \subseteq Z とします。 f(A) f^{-1}(X) を以下のように定義します。

  •  x \in f(A) \iff \exists a \in A ( x = f(a) )
  •  a \in f^{-1}(X) \iff f(a) \in X

以下のことが成り立ちます。(「集合と位相」定理5.2 を参照)

(1-1)  f(A \cup B) = f(A) \cup f(B)

[証明]
 \begin{eqnarray*}
x \in f(A \cup B) & \iff & \exists a \in A \cup B ( x = f(a) ) \\
 & \iff & \exists a \in C (a \in A \cup B \land  x = f(a) ) \\
 & \iff & \exists a \in C ( (a \in A \lor a \in B) \land  x = f(a) ) \\
 & \iff & \exists a \in C ( (a \in A \land  x = f(a) ) \lor ( a \in B \land  x = f(a) ) \\
 & \iff & \exists a \in C ( a \in A \land  x = f(a) ) \lor \exists a \in C ( a \in B \land  x = f(a) ) \\
 & \iff & x \in f(A) \lor x \in f(B) \\
 & \iff & x \in f(A) \cup f(B) \\
\end{eqnarray*}
[証明終わり]

(1-2)  f(A \cap B) \subseteq f(A) \cap f(B)

[証明]
 \begin{eqnarray*}
x \in f(A \cap B) & \iff & \exists a \in A \cap B ( x = f(a) ) \\
 & \iff & \exists a \in C (a \in A \cap B \land  x = f(a) ) \\
 & \iff & \exists a \in C ( (a \in A \land a \in B) \land  x = f(a) ) \\
 & \iff & \exists a \in C ( (a \in A \land  x = f(a) ) \land ( a \in B \land  x = f(a) ) \\
 & \implies & \exists a \in C ( a \in A \land  x = f(a) ) \land \exists a \in C ( a \in B \land  x = f(a) ) \\
 & \iff & x \in f(A) \land x \in f(B) \\
 & \iff & x \in f(A) \cap f(B) \\
\end{eqnarray*}
[証明終わり]

(1-3)  f^{-1}(X \cup Y) = f^{-1}(X) \cup f^{-1}(Y)

[証明]
 \begin{eqnarray*}
a \in f^{-1}(X \cup Y) & \iff & f(a) \in X \cup Y \\
 & \iff & f(a) \in X \lor f(a) \in Y \\
 & \iff & a \in f^{-1}(X) \lor a \in f^{-1}(Y) \\
 & \iff & a \in f^{-1}(X) \cup f^{-1}(Y) \\
\end{eqnarray*}
[証明終わり]

(1-4)  f^{-1}(X \cap Y) = f^{-1}(X) \cap f^{-1}(Y)

[証明]
 \begin{eqnarray*}
a \in f^{-1}(X \cap Y) & \iff & f(a) \in X \cap Y \\
 & \iff & f(a) \in X \land f(a) \in Y \\
 & \iff & a \in f^{-1}(X) \land a \in f^{-1}(Y) \\
 & \iff & a \in f^{-1}(X) \cap f^{-1}(Y) \\
\end{eqnarray*}
[証明終わり]

(1-5)  A \subseteq f^{-1}(f(A))

[証明]
 \begin{eqnarray*}
a \in A & \implies & f(a) \in f(A) \\
 & \iff & a \in f^{-1}(f(A)) \\
\end{eqnarray*}
[証明終わり]

(1-6)  f(f^{-1}(X)) \subseteq X

[証明]
 \begin{eqnarray*}
x \in f(f^{-1}(X)) & \iff & \exists a \in f^{-1}(X) ( x = f(a) ) \\
 & \iff & \exists a \in C ( f(a) \in X \land x = f(a) ) \\
 & \iff & x \in X \land \exists a \in C ( x = f(a) ) \\
 & \iff & x \in X \land x \in f(C) \\
\end{eqnarray*}
[証明終わり]

(1-7)  f(A) \setminus f(B) \subseteq f(A \setminus B)

[証明]
 \begin{eqnarray*}
x \in f(A \setminus B) & \iff & \exists a \in A \setminus B ( x = f(a) ) \\
 & \iff & \exists a \in C (a \in A \setminus B \land  x = f(a) ) \\
 & \iff & \exists a \in C ( a \in A \land a \notin B \land  x = f(a) ) \\
 & \Longleftarrow & \exists a \in C ( a \in A \land  x = f(a) ) \land \forall a \in C ( a \in B \implies x \ne f(a) ) \\
 & \iff & x \in f(A) \land x \notin f(B) \\
 & \iff & x \in f(A) \setminus f(B) \\
\end{eqnarray*}
[証明終わり]

(1-8)  f^{-1}(X) \setminus f^{-1}(Y) = f^{-1}(X \setminus Y)

[証明]
 \begin{eqnarray*}
a \in f^{-1}(X \setminus Y) & \iff & f(a) \in X \setminus Y \\
 & \iff & f(a) \in X \land f(a) \notin Y \\
 & \iff & a \in f^{-1}(X) \land a \notin f^{-1}(Y) \\
 & \iff & a \in f^{-1}(X) \setminus f^{-1}(Y) \\
\end{eqnarray*}
[証明終わり]

集合系と写像の関係

 f: X \to Y X の部分集合系  (A_\lambda \mid \lambda \in \Lambda) Y の部分集合系  (B_\mu \mid \mu \in M) に対して以下が成り立ちます。(「集合と位相」問5.4 を参照)

(2-1)  \displaystyle f(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} f(A_\lambda)

[証明]
 \begin{eqnarray*}
y \in f(\bigcup_{\lambda \in \Lambda} A_\lambda)
 & \iff & \exists x \in X (x \in \bigcup_{\lambda \in \Lambda} A_\lambda \land  y = f(x) ) \\
 & \iff & \exists x \in X ( \exists \lambda \in \Lambda (x \in A_\lambda) \land  y = f(x) ) \\
 & \iff & \exists x \in X ( \exists \lambda \in \Lambda (x \in A_\lambda \land  y = f(x))) \\
 & \iff & \exists \lambda \in \Lambda (\exists x \in X (x \in A_\lambda \land y = f(x))) \\
 & \iff & \exists \lambda \in \Lambda (y \in f(A_\lambda)) \\
 & \iff & y \in \bigcup_{\lambda \in \Lambda} f(A_\lambda) \\
\end{eqnarray*}
[証明終わり]

(2-2)  \displaystyle f(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} f(A_\lambda)

[証明]
 \begin{eqnarray*}
y \in f(\bigcap_{\lambda \in \Lambda} A_\lambda)
 & \iff & \exists x \in X (x \in \bigcap_{\lambda \in \Lambda} A_\lambda \land  y = f(x) ) \\
 & \iff & \exists x \in X ( \forall \lambda \in \Lambda (x \in A_\lambda) \land  y = f(x) ) \\
 & \iff & \exists x \in X ( \forall \lambda \in \Lambda (x \in A_\lambda \land  y = f(x))) \\
 & \implies & \forall \lambda \in \Lambda (\exists x \in X (x \in A_\lambda \land y = f(x))) \\
 & \iff & \forall \lambda \in \Lambda (y \in f(A_\lambda)) \\
 & \iff & y \in \bigcap_{\lambda \in \Lambda} f(A_\lambda) \\
\end{eqnarray*}
[証明終わり]

(2-3)  \displaystyle f^{-1}(\bigcup_{\mu \in M} B_\mu) = \bigcup_{\mu \in M} f^{-1}(B_\mu)

[証明]
 \begin{eqnarray*}
x \in f^{-1}(\bigcup_{\mu \in M} B_\mu)
 & \iff & f(x) \in \bigcup_{\mu \in M} B_\mu \\
 & \iff & \exists \mu \in M (f(x) \in B_\mu) \\
 & \iff & \exists \mu \in M (x \in f^{-1}(B_\mu)) \\
 & \iff & x \in \bigcup_{\mu \in M} f^{-1}(B_\mu) \\
\end{eqnarray*}
[証明終わり]

(2-4)  \displaystyle f^{-1}(\bigcap_{\mu \in M} B_\mu) = \bigcap_{\mu \in M} f^{-1}(B_\mu)

[証明]
 \begin{eqnarray*}
x \in f^{-1}(\bigcap_{\mu \in M} B_\mu)
 & \iff & f(x) \in \bigcap_{\mu \in M} B_\mu \\
 & \iff & \forall \mu \in M (f(x) \in B_\mu) \\
 & \iff & \forall \mu \in M (x \in f^{-1}(B_\mu)) \\
 & \iff & x \in \bigcap_{\mu \in M} f^{-1}(B_\mu) \\
\end{eqnarray*}
[証明終わり]

上極限集合・下極限集合

集合系  (E_n \mid n \in \mathbb{N}) に対して

  • 上極限集合  \displaystyle \limsup_{n \to \infty} E_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n
  • 下極限集合  \displaystyle \liminf_{n \to \infty} E_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n

を定義します。上極限集合、下極限集合について以下が成り立ちます。(「集合と位相」問5.6 を参照)

(3-1)  \displaystyle \liminf_{n \to \infty} E_n \subseteq \limsup_{n \to \infty} E_n

[証明] 任意の  n \in \mathbb{N} に対して  n \ge k_0 ならば  x \in E_n となる  k_0 \in \mathbb{N} が存在するとします。任意の  k \in \mathbb{N} に対して  m = \max(k_0, k) とおくと  m \ge k_0 なので  x \in E_m となります。よって
 \begin{eqnarray*}
x \in \liminf_{n \to \infty} E_n
 & \iff & x \in \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n \\
 & \iff & \exists k \in \mathbb{N} ( \forall n \in \mathbb{N} (n \ge k \implies x \in E_n)) \\
 & \implies & \forall k \in \mathbb{N} ( \exists n \in \mathbb{N} (n \ge k \land x \in E_n)) \\
 & \iff & x \in \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \\
 & \iff & x \in \limsup_{n \to \infty} E_n \\
\end{eqnarray*}
[証明終わり]

(3-2) 「すべての  n \in \mathbb{N} に対して  A_n \subseteq B_n」が成り立つとき  \displaystyle \limsup_{n \to \infty} A_n \subseteq \limsup_{n \to \infty} B_n \displaystyle \liminf_{n \to \infty} A_n \subseteq \liminf_{n \to \infty} B_n

[証明] 定義より
 \displaystyle \limsup_{n \to \infty} A_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} A_n \subseteq \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} B_n = \limsup_{n \to \infty} B_n
 \displaystyle \liminf_{n \to \infty} A_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} A_n \subseteq \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} B_n = \liminf_{n \to \infty} B_n
[証明終わり]

(3-3)  \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) = \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n

[証明]  \displaystyle x \in \limsup_{n \to \infty} (A_n \cup B_n) \setminus \limsup_{n \to \infty} A_n =
\left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} (A_n \cup B_n) \right) \setminus \left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} A_n \right) とすると  \displaystyle x \notin \bigcup_{n=k_0}^{\infty} A_n となる  k_0 \in \mathbb{N} が存在します。

 k \ge k_0 ならば  \displaystyle x \notin \bigcup_{n=k}^{\infty} A_n であり、 \displaystyle x \in \bigcup_{n=k}^{\infty} (A_n \cup B_n) = \left( \bigcup_{n=k}^{\infty} A_n \right) \cup \left( \bigcup_{n=k}^{\infty} B_n \right) より  \displaystyle x \in \bigcup_{n=k}^{\infty} B_n となります(*1)。

また、 \displaystyle x \in \bigcup_{n=k_0}^{\infty} B_n より  k \le k_0 ならば  \displaystyle x \in \bigcup_{n=k}^{\infty} B_n となります(*2)。

(*1)、(*2)より  \displaystyle x \in \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} B_n = \limsup_{n \to \infty} B_n となります。よって  \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) \subseteq \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立ちます。

(3-2)より  \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) \supseteq \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立つので  \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) = \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立ちます。[証明終わり]

(3-4)  \displaystyle \liminf_{n \to \infty} (A_n \cap B_n) = \liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n

[証明] ド・モルガンの法則より  \displaystyle \left( \limsup_{n \to \infty} E_n \right)^c = \left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \right)^c = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n^c = \liminf_{n \to \infty} E_n^c
が成り立ちます。(3-3)より
 \begin{eqnarray*}
\liminf_{n \to \infty} (A_n \cap B_n) & = & \left( \limsup_{n \to \infty} (A_n \cap B_n)^c \right)^c \\
 & = & \left( \limsup_{n \to \infty} (A_n^c \cup B_n^c) \right)^c \\
 & = & \left( \limsup_{n \to \infty} A_n^c \cup \limsup_{n \to \infty} B_n^c \right)^c \\
 & = & \left( \limsup_{n \to \infty} A_n^c \right)^c \cap \left( \limsup_{n \to \infty} B_n^c \right)^c \\
 & = & \liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n
\end{eqnarray*}
となります。[証明終わり]

極限集合

集合系  (E_n \mid n \in \mathbb{N}) に対して上極限集合と下極限集合が一致するとき、これを極限集合といい  \displaystyle \lim_{n \to \infty} E_n = \limsup_{n \to \infty} E_n = \liminf_{n \to \infty} E_n で表します。極限集合について以下が成り立ちます。(「集合と位相」問5.7 を参照)

(4-1) 「(条件*)すべての  n \in \mathbb{N} に対して  E_n \subseteq E_{n+1}」が成り立つとき  \displaystyle \lim_{n \to \infty} E_n = \bigcup_{n=0}^{\infty} E_n

[証明] (条件*)より  \displaystyle \bigcap_{n=k}^{\infty} E_n = E_k となるので  \displaystyle \liminf_{n \to \infty} E_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n = \bigcup_{k=0}^{\infty} E_k となり、 \displaystyle \limsup_{n \to \infty} E_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \subseteq \bigcup_{n=0}^{\infty} E_n = \liminf_{n \to \infty} E_n が成り立ちます。

また (3-1)より  \displaystyle \liminf_{n \to \infty} E_n \subseteq \limsup_{n \to \infty} E_n となるので、 \displaystyle \limsup_{n \to \infty} E_n = \liminf_{n \to \infty} E_n = \bigcup_{n=0}^{\infty} E_n が成り立ちます。[証明終わり]

(4-2) 「(条件*)すべての  n \in \mathbb{N} に対して  E_n \supseteq E_{n+1}」が成り立つとき  \displaystyle \lim_{n \to \infty} E_n = \bigcap_{n=0}^{\infty} E_n

[証明] (条件*)より任意の  n \in \mathbb{N} に対して  E_n^c \subseteq E_{n+1}^c となるので、
(4-1)より  \displaystyle \limsup_{n \to \infty} E_n^c = \liminf_{n \to \infty} E_n^c = \bigcup_{n=0}^{\infty} E_n^c が成り立ちます。各項の補集合をとるとド・モルガンの法則より  \displaystyle \liminf_{n \to \infty} E_n = \limsup_{n \to \infty} E_n = \bigcap_{n=0}^{\infty} E_n が成り立ちます。[証明終わり]

 \displaystyle \lim_{n \to \infty} A_n \displaystyle \lim_{n \to \infty} B_n がともに存在すれば以下が成り立ちます。(「集合と位相」問5.8 を参照)

(5-1)  \displaystyle \lim_{n \to \infty} (A_n \cup B_n) = \lim_{n \to \infty} A_n \cup \lim_{n \to \infty} B_n

[証明] (3-2)、(3-1)、(3-3)より
 \begin{eqnarray*}
\liminf_{n \to \infty} A_n \cup \liminf_{n \to \infty} B_n & \subseteq & \liminf_{n \to \infty} (A_n \cup B_n) \\
 & \subseteq  & \limsup_{n \to \infty} (A_n \cup B_n) \\
 & = & \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n \\
\end{eqnarray*}
となります。 \displaystyle \liminf_{n \to \infty} A_n = \limsup_{n \to \infty} A_n \displaystyle \liminf_{n \to \infty} B_n = \limsup_{n \to \infty} B_n ならば上記の式の項はすべて等しくなります。[証明終わり]

(5-2)  \displaystyle \lim_{n \to \infty} (A_n \cap B_n) = \lim_{n \to \infty} A_n \cap \lim_{n \to \infty} B_n

[証明] (3-4)、(3-1)、(3-2)より
 \begin{eqnarray*}
\liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n & = & \liminf_{n \to \infty} (A_n \cap B_n) \\
 & \subseteq  & \limsup_{n \to \infty} (A_n \cap B_n) \\
 & \subseteq  & \limsup_{n \to \infty} A_n \cap \limsup_{n \to \infty} B_n \\
\end{eqnarray*}
となります。 \displaystyle \liminf_{n \to \infty} A_n = \limsup_{n \to \infty} A_n \displaystyle \liminf_{n \to \infty} B_n = \limsup_{n \to \infty} B_n ならば上記の式の項はすべて等しくなります。[証明終わり]

順序関係

集合  X 上の二項関係  \le

  • 反射律: 任意の  x \in X に対して  x \le x
  • 推移律: 任意の  x , y, z \in X に対して  x \le y \le z ならば  x \le z
  • 反対称律: 任意の  x , y \in X に対して  x \le y かつ  y \le x ならば  x = y

を満たすとき半順序と呼びます。単に順序(順序関係)という場合は半順序のことを表すとします。さらに

  • 任意の  x , y \in X に対して  x \le y または  y \le x

を満たすとき全順序と呼びます。

集合  X の部分集合の全体を  X の冪集合と呼び  \mathfrak{P}(X) で表します。 A \subseteq B で決まる  \mathfrak{P}(X) 上の二項関係  \subseteq は順序関係となります。これを  \mathfrak{P}(X) 上の包含関係と呼びます。(「集合と位相」例8.1 を参照)

同値関係

集合  X 上の二項関係  \cong

  • 反射律: 任意の  x \in X に対して  x \cong x
  • 推移律: 任意の  x , y, z \in X に対して  x \cong y \cong z ならば  x \cong z
  • 対称律: 任意の  x , y \in X に対して  x \cong y ならば  y \cong x

を満たすとき同値関係と呼びます。

集合  X 上の同値関係  \cong が与えられたとき、 x \in X に対して  X の部分集合  C(x) = \{ y \in X \mid x \cong y \} x の同値類と呼びます。同値類全体の集合を集合  X の同値関係  \cong による商集合と呼び、 X/\cong と書きます。 x \in X C(x) \in X/\cong に対応させる全射  f X から  X/\cong への自然な射影と呼びます。 \cong が同値関係であることから、同値類の全体は、集合  X を互いに交わらない部分集合に分割します。

 f: X \to Y に対して、 x \cong y \iff f(x) = f(y) で定義される  X 上の関係  \cong は同値関係となります。 \cong f に付随する同値関係と呼びます。 C(x) = C(y) \iff f(x) = f(y) となるので、同値類  C(x) f(x) を対応させる写像  g: {X/\cong} \to f(Y) を定義することができます。 g全単射となります。(「集合と位相」問8.3 を参照)

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)