集合.19　集合の濃度.4　対角線論法と連続体濃度を持つ集合

ホーム
大学数学, 集合と位相
集合.19　集合の濃度.4　対角線論法と連続体濃度を持つ集合

大学数学

2018.06.29

集合.19　集合の濃度.4　対角線論法と連続体濃度を持つ集合

対角線論法

集合 $X$ のべき集合は $2^{X}$ と表されるので、その濃度を $2^{ \mathbf{card}(X) }$ と表します。

べき集合はイメージ的には元の集合よりも非常に大きいです。

実際、有限集合の場合には、集合 $X$ の濃度が $n$ のとき、集合 $2^{X}$ の濃度は $2^n$ になります。

実は無限集合の場合でもイメージ通りのことが言えます。一般に、次の事実が成り立ちます。証明には対角線論法というものを使います。

◆Prop.SetTop.2.18.1.

$X$ を集合とすると、 $\mathbf{card}(X) < 2^{\mathbf{card}(X)$

■Prf.

まず、 $X$ から $2^{X}$ への単射 $f$ を $f \colon X \rightarrow 2^{X}, f(x) = \{x \},x \in X$ によって構成することができるので、

$\mathbf{card}(X) \leq 2^{\mathbf{card}(X)$

次に、等号が成立しないことを示す。すなわち、 $X$ から $2^{X}$ への全射は存在しないことを示す。

$g \colon X \rightarrow 2^{X}$ を任意の写像とし、 $X$ の部分集合 $Y$ を

$Y = \{ x \in X \mid x \notin g(x) \}$
（ここで、 $g(x)$ は $2^{X}$ の元であるから、 $X$ の部分集合である）

によって定めると、 $g(x) = Y$ となる $x \in X$ は存在しないこと、したがって $g$ は全射とはならないことを示す。

もし $g(x) = Y$ となる $x$ が存在したとすると、 $x \in Y=g(x)$ のとき、 $Y$ の定義より $x \notin Y=g(x)$ となるから矛盾。 $x \notin Y=g(x)$ のとき、 $Y$ の定義より $x \in Y=g(x)$ となるから矛盾。

したがって、 $g(x)=Y$ となる $x \in X$ は存在しないため、 $g$ は全射ではない。よって、示された。 □

Rem.1. 対角線論法という理由ですが、 $\Delta_{X} = \{ (x,y) \in X \times X \mid x=y \}$ を対角線集合と言います。あたかも $X^2$ を $xy$ 平面のようなものだと思うと、直線 $y=x$ を引いたように見えることからこのように言います。

また、 $G = \{ (x,y) \in X \times X \mid y \in g(x) \}$ とすると、 $G \cap \Delta_{X} = \{ (x,x) \in X \times X \mid x \in g(x) \}$ となります。

さらに、射影 $p_1 \colon X \times X \rightarrow X$ を $p_1( (x,y) ) = x, (x,y) \in X \times X$ で定めると、

$\begin{align*} p_1( G \cap \Delta_{X}) &= \{ z \in X \mid \exists (x,y) \in G \cap \Delta_{X},p((x, y))=z \} \\ &= \{ x \in X \mid x \in g(x) \} \end{align*}$

となるため、 $Y = X \verb|\| p_1( G \cap \Delta_{X})$ と対角線集合を用いて表すことができます。これが対角線論法と言われる由縁です。

可算濃度と連続体濃度の関係

連続体濃度が可算濃度よりも真に大きいこと、したがって連続体濃度を持つ集合の元をすべて具体的に書き表すことはできないことを示します。

実は、連続体濃度は、可算濃度を持つ集合のべき集合の濃度と等しくなります。

◆Prop.SetTop.2.18.2.

$\aleph = 2^{ \aleph_0 }$
すなわち、 $\mathbf{card}( \mathbb{R}) = 2^{ \mathbf{card}( \mathbb{N})} > \mathbf{card}( \mathbb{N})$

■Prf.

まず、 $\mathbf{card}( \mathbb{N}) = \mathbf{card}( \mathbb{Q})$ であるから、 $2^{ \mathbf{card}( \mathbb{N})} = 2^{ \mathbf{card}( \mathbb{Q})}$ である。
（全単射 $h \colon \mathbb{N} \rightarrow \mathbb{Q}$ が存在するので、全単射 $h' \colon 2^{\mathbb{N}} \rightarrow 2^{\mathbb{Q}}$ を $h'(V) = h(V) = \{ h(x) \in \mathbb{Q} \mid x \in V \},V \subset \mathbb{N}$ で定めればよい）

写像 $f \colon \mathbb{R} \rightarrow 2^{\mathbb{Q}}$ を

$f(x) = \{ r \in \mathbb{Q} \mid r<x \}$

で定めると、 $f$ は単射となる。したがって、 $\mathbf{card}( \mathbb{R}) \leq 2^{ \mathbf{card}( \mathbb{Q})}= 2^{ \mathbf{card}( \mathbb{N})}$

一方で、写像 $g \colon 2^{\mathbb{N}} \rightarrow \mathbb{R}$ を

$g(V)= \sum_{n=0}^{\infty} \frac{v_n}{3^n}, v_n= \begin{cases} 1 & ( n \in V) \\ 0 & ( n \notin V) \end{cases}, V \subset N$

で定めると、 $g$ は単射となる。したがって、 $\mathbf{card}( \mathbb{R}) \geq 2^{ \mathbf{card}( \mathbb{N})}$

よって、 $\mathbf{card}( \mathbb{R}) = 2^{ \mathbf{card}( \mathbb{N})}$ が示された。 □

連続体濃度を持つ集合

可算濃度を持つ集合に関する結果を用いて、連続体濃度を持つ集合についても、次のような一般的事実が成り立ちます。

◆Prop.SetTop.2.18.3.

(ⅰ) $A_1,A_2, \dots , A_n$ を高々連続体濃度を持つ集合とするとき、 $A_1 \times A_2 \times \dots \times A_n$ は高々連続体濃度を持つ集合である。
(ⅱ） $I$ を高々連続体濃度を持つ集合とし、 $(A_i)_{i \in I}$ を高々連続体濃度を持つ集合の族とすると、 $\bigcup_{ i \in I} A_i$ は高々連続体濃度を持つ集合である。

この命題は「高々連続体濃度を持つ集合」を「連続体濃度を持つ集合」に言い換えても成立する。

■Prf.

「連続体濃度を持つ集合」の場合もまったく同様に示せるので、ここでは「高々連続体濃度を持つ集合」の場合を示す。

(ⅰ)

数学的帰納法より、 $n=2$ の場合に示せば十分である。
（一般の場合は、 $A_1 \times A_2 \times \dots \times A_n = (A_1 \times A_2 \times \dots A_{n-1}) \times A_n$ と見て、 $n=2$ の場合の結果を適用すれば示せる）

高々連続体濃度を持つ集合の定義より、 $A_1, A_2$ から $\mathbb{R}$ への単射 $f_i \colon A_i \rightarrow \mathbb{R},i=1,2$ が存在する。
そこで、次の写像

$f_1 \times f_2 \colon A_1 \times A_2 \rightarrow \mathbb{R}^2$
$f_1 \times f_2 (( a_1,a_2))=( f_1(a_1),f_2(a_2))$
$a_i \in A_i, i=1,2$

は単射である。

したがって、 $\mathbf{card}( A_1 \times A_2) \leq \mathbf{card}(\mathbb{R}^{2})$ であるから、 $\mathbb{R}^2$ が連続体濃度を持つ集合であることを示せばよい。

ここで、

$\mathbf{card}(\mathbb{R}^2)=(2^{ \mathbf{card}(\mathbb{N})})^2$

かつ、 $\mathbf{card}(\mathbb{N}^2)= \mathbf{card}(\mathbb{N})$ より、

$2^{\mathbf{card}(\mathbb{N}^2)}=2^{\mathbf{card}(\mathbb{N})}=\mathbf{card}(\mathbb{R})$

であるから、

$(2^{ \mathbf{card}(\mathbb{N})})^2=2^{\mathbf{card}(\mathbb{N}^2)}$ を示せばよい。

さらに、べき集合と写像の集合の同一視により、

$Map( 2, Map( \mathbb{N},2))$ と $Map( \mathbb{N}^2,2)$ との間に全単射が存在することを示せばよい。

ここでは、一般の集合 $X,Y,Z$ について、

$Map( Z, Map( Y,X))$ と $Map( Y \times Z ,X)$ との間に全単射が存在することを示すことで、上を示そう。

$f \in Map( Y \times Z ,X)$ とする。ここで、 $z \in Z$ を一つ固定して、

$F_z \in Map( Y,X)$ を

$F_z(y)= f(y,z), y \in Y$

で定める。各 $z \in Z$ に対して $F_z$ は一つ定まるから、写像

$f_{\varphi} \colon Z \rightarrow Map( Y,X), f_{\varphi}(z) = F_z,z \in Z$ を定めることができる。

$f_{\varphi}$ は各 $f$ について一つ定まるものであるため、写像

$\varphi \colon Map( Y \times Z ,X) \rightarrow Map( Z, Map( Y,X))$
$\varphi(f)=f_{\varphi},f \in Map( Y \times Z ,X)$

が定まる。

$\varphi$ が全単射であることを示す。

$\varphi$ が全射であることから示す。任意の $g \in Map( Z, Map( Y,X))$ をとる。 $g(z) \in Map( Y,X)$ であることに注意して、写像 $G \colon Y \times Z \rightarrow X$ を

$G(y,z) = g(z)(y),(y,z) \in Y \times Z$

によって定める。 $\varphi(G) = g$ であることを示し、 $\varphi$ の全射性を示そう。

$\varphi(G) = G_{\varphi} \in Map( Z, Map( Y,X))$ であり、 $G_{\varphi}$ とは $G_{\varphi}(z)=G_z \in Map( Y,X)$ を満たす写像であり、 $G_z$ とは $G_z(y)=G(y,z) \in X$ を満たす写像である。

ここで、 $G(y,z) = g(z)(y)$ より、 $G_z(y) = g(z) (y)$ となり、写像の相等の定義から $G_{\varphi}(z)=G_z=g(z)$ である。

再び、写像の相等の定義より、 $\varphi(G)=G_{\varphi}=g$ が成り立つ。よって、全射性は示された。

$\varphi$ の単射性を示す。すなわち、 $\varphi(f) = \varphi(f')$ のとき、 $f=f'$ を示す。

$\varphi(f) = \varphi(f')$ より、 $f_{\varphi}=f'_{\varphi}$

ここで、 $f_{\varphi}$ とは $f_{\varphi}(z) = F_z,F_z(y)=f(y,z)$ を満たす写像であり、 $f'_{\varphi}$ とは $f'_{\varphi}(z) = F'_z,F'_z(y)=f'(y,z)$ を満たす写像である。

$f_{\varphi}=f'_{\varphi}$ より、任意の $z \in Z$ に対して $F_z=F'_z$
$F_z=F'_z$ より、任意の $y \in Y$ に対して $f(y,z) = f'(y,z)$

したがって、任意の $(y,z) \in Y \times Z$ に対して $f(y,z) = f'(y,z)$ であるから、 $f=f'$ が成り立つ。よって、 $\varphi$ の単射性も示され、 $\varphi$ は全単射である。

以上から、一般的結果の帰結として $(2^{ \mathbf{card}(\mathbb{N})})^2=2^{\mathbf{card}(\mathbb{N}^2)}$ が成り立ち、ゆえに $\mathbf{card}(\mathbb{R}^2) = \mathbf{card}(\mathbb{R})$ が成り立つ。

よって、（ⅰ）が示された。

(ⅱ)

(ⅰ) の結果より、 $I \times \mathbb{R}$ は高々連続体濃度を持つ集合である。ここで、各 $A_i$ は高々連続体濃度を持つ集合であるから、全射 $f_i \colon \mathbb{R} \rightarrow A_i$ が存在する。

写像 $h \colon I \times \mathbb{R} \rightarrow \bigcup_{ i \in I } A_i$ を $h(i,r) = f_i(r), i \in I,r \in \mathbb{R}$ と定めると、各 $f_i$ が全射であることから、 $h$ は全射である。

したがって、 $\mathbf{card}( I \times \mathbb{R}) \geq \mathbf{card}(\bigcup_{ i \in I } A_i)$ となるから、示された。 □

◆Prop.SetTop.2.18.3.(ⅰ) からの直接の帰結として、特に次が成り立ちます。

◆Cor.SetTop.2.18.4.

$n$ を正の自然数とするとき、 $\mathbf{card}(\mathbb{R}^n) = \mathbf{card}(\mathbb{R}) = \aleph$

特に、 $\mathbf{card}(\mathbb{C})=\mathbf{card}(\mathbb{R}^2) = \mathbf{card}(\mathbb{R}) = \aleph$

すなわち、単純に集合として考えるならば、濃度という面で見て、平面や空間、 $n$ 次元空間と直線を区別することはできないということです。同じくらい点の数が多いというような意味合いになります。

この事実はカントールという数学者によって初めて見い出され、素朴な直観に反する事実に当初は驚きをもって迎えられました。

また、次の事実も成り立ちます。

◆Prop.SetTop.2.18.5.

$X,Y$ は集合とする。
$\mathbf{card}(X)= \aleph$ かつ $\mathbf{card}(Y)= \aleph_0$ ならば、 $\mathbf{card}(X \verb|\| Y) = \aleph$

■Prf.

$X = \mathbb{R},Y=\mathbb{N}$ としても一般性を失わない。

$\mathbb{R}=\( (\mathbb{R} \verb|\| \mathbb{Z}) \cup \mathbb{Z}$
$\mathbb{R} \verb|\| \mathbb{N} = (\mathbb{R} \verb|\| \mathbb{Z}) \cup (\mathbb{Z} \verb|\| \mathbb{N})$

であり、 $(\mathbb{R} \verb|\| \mathbb{Z}) \cap \mathbb{Z} = \emptyset$ および $(\mathbb{R} \verb|\| \mathbb{Z}) \cap (\mathbb{Z} \verb|\| \mathbb{N}) = \emptyset$ が成り立っている。