エレファントな整数論(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 を参照)

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

作者:内田伏一
発売日: 2020/03/14
メディア: 単行本

新版集合と位相そのまま使える答えの書き方 (KS理工学専門書)

発売日: 2016/05/24
メディア: 単行本

集合と写像

(1-1)

(1-2)

(1-3)

(1-4)

(1-5)

(1-6)

(1-7)

(1-8)

集合系と写像の関係

(2-1)

(2-2)

(2-3)

(2-4)