大学数学

集合.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 が成り立っている。

ここで、写像 f \colon \mathbb{Z} \verb|\| \mathbb{N} \rightarrow \mathbb{Z} を

f(-2m+1)=-(m-1),f(-2m)=m,m=1,2, \dots

で定めると、f は全単射である。

そこで、写像 g \colon \mathbb{R} \verb|\| \mathbb{N} \rightarrow \mathbb{R} を

g(x)= \begin{cases} x & ( x \in \mathbb{R} \verb|\| \mathbb{Z}) \\ f(x) & ( x \in \mathbb{Z} \verb|\| \mathbb{N}) \end{cases}

で定めると、g は全単射となる。

よって、\mathbf{card}(\mathbb{R} \verb|\| \mathbb{N})=\mathbf{card}(\mathbb{R})= \aleph である。 □

特に、有理数全体の集合および代数的数全体の集合は可算集合でしたので、次の系が導かれます。

◆Cor.SetTop.2.18.6.

無理数全体の集合および超越数全体の集合は連続体濃度を持つ。

 

関連記事

  1. 大学数学

    集合.20　選択公理

    選択公理実は今までも暗に使っていたのですが、次のことは公理とみ…

  2. 大学数学

    集合.16　集合の濃度.1　濃度の定義と比較方法

    有限集合と無限集合、濃度直観的に意味がわかると思うのでここまで…

  3. 大学数学

    集合.23　ツォルンの補題

    ツォルンの補題代数学などにおいてよく用いられる選択公理と同値な…

  4. 大学数学

    集合.15　集合の演算

    集合の演算ここまで、べき集合、和集合、補集合、差集合、共通集合…

  5. 大学数学

    写像.9　圏、特別な射と記号、可換図式

    圏、特別な射ここで、あまり深入りはしませんが、圏論的な全射、単…

  6. 大学数学

    集合.3　補集合、差集合

    補集合集合 \( A \) は全体集合 \( X \) の部分…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    論理記号.4　～がただ一つ存在する、定義

  2. 大学数学

    写像.13　集合の準同型定理、引き起こされる写像

  3. 大学数学

    集合.5　添字集合と集合族

  4. 大学数学

    写像.12　商集合の普遍性

  5. 大学数学

    集合.9　積集合（一般の場合）
PAGE TOP
error: Content is protected !!