コラム 集合の対等性
ここでは集合の「大きさ」について説明します。集合が他の集合と同じくらいの大きさであるということは、直感的には「同じくらい元をたくさん持つ」ということです。集合が他の集合より大きいということは、直感的には「元をよりたくさん持つ」ということです。しかしながら、元が有限個でないような集合同士の大きさの比較をするためには、このように直感的な言い回しではなく、もう少し正確な定式化が必要になります。
例えば、２つの集合\( S \)と\( T \)の間に全単射であるような写像\( f \colon S \to T \)が存在する場合は、\( S \)の元と\( T \)の元が１つずつ対応し合うので、同じくらいの大きさであると考えたいところです。というわけで、集合が同じような大きさであるという曖昧な概念の代わりに、全単射の存在という性質を考えることにしましょう。
| 定義1（対等性の定義） |
| ２つのクラス\( A \)と\( B \)が対等であるとは、全単射であるようなクラス関数\( f \colon A \to B \)が存在するということである、また「\( A \)と\( B \)が対等である」という文をここでは\( A \approx B \)と略記する。 |
逆写像の存在性に関する演習により、\( A \approx B \)と\( B \approx A \)が同値であることが分かります。この対等という概念は、「濃度」という更に扱いやすい同値な概念に置き換えることが出来るのですが、そのためには補遺１で導入する選択公理という公理が必要になるので*1、ここでは割愛します。
また、直感的には集合の部分集合は元の集合より大きくはない集合であると考えることが自然でしょう。この考え方に基づきますと、２つの集合\( S \)と\( T \)の間に単射\( f \colon S \to T \)が存在するならば、\( S \)は\( T \)より大きくはないと考えることが自然となります。実際、\( f \)の像への制限\( f |^{f(S)} \)は全単射であるので\( S \)と\( f(S) \)は同じくらいの大きさであると考えたく、また\( f(S) \)は\( T \)の部分集合なので\( T \)より大きくはないと考えるのが自然です。以上の観察を合わせると、直感的には\( S \)は\( f(S) \)と同じくらいの大きさでかつ\( f(S) \)は\( T \)より大きくはないので、\( S \)は\( T \)より大きくはないと考えるのが自然です。
これはあくまで直感的な話であり数学的な議論ではありませんが、「\( S \)が\( T \)より大きい」という言葉の意味を数学的に定義するためには１つの指標として役に立ちます。以上の考え方の対偶を取ると、\( S \)が\( T \)より大きいならば\( S \)から\( T \)に単射が存在しない、ということが従います。このことを踏まえ、意味が未定義である「\( S \)が\( T \)より大きい」という文の代わりに、「\( S \)から\( T \)に単射が存在しない」という数学的に意味を持つ条件を考えることにしましょう。
| 定義2（\( \ll \)の定義） |
| ２つのクラス\( A \)と\( B \)に対し、「単射であるようなクラス関数\( f \colon B \to A \)が存在しない」という文をここでは\( A \ll B \)や\( B \gg A \)と略記する。 |
以上で、集合の大きさの比較に相当する概念として３つの記号\( \approx \)と\( \ll \)と\( \gg \)を、直感的で曖昧な方法でなく数学的に厳密な方法で定式化出来ました。それではこれらの記号の関係性を紹介します。
| 定理3（カントール・ベルンシュタインの定理） |
| ２つの任意の集合\( S \)と\( T \)に対し、以下は同値である： |
| (1) \( S \approx T \) |
| (2) 「\( S \ll T \)でない」かつ「\( S \gg T \)でない」 |
カントール・ベルンシュタインの定理の証明は「漸化式」を用いると見通しが良くなるので、ここでは証明を後回しにする*2ことにし、その事実は使わないことにします。さて、カントール・ベルンシュタインの定理では\( A \ll B \)も\( A \gg B \)が成り立たない状況について考えたので、今度はどのような時に\( A \ll B \)や\( A \gg B \)が成り立つかを考えましょう。その準備として、「カントールの定理」を紹介します。
| 定理4（カントールの定理） |
| 任意の集合\( S \)と任意の写像\( f \colon \mathscr{P}(S) \to S \)に対して、\( f \)は全射でない。 |
証明
\( R := \{ x \in S \mid x \notin f(x) \} \)と置く。\( R \notin \textrm{im}(f) \)を背理法で示す。\( R \in \textrm{im}(f) \)と仮定する。\( f(x) = R \)を満たす\( x \in S \)が存在する。\( x \in R \)とすると、\( R \)の定義から\( x \notin f(x) = R \)であり、\( x \in R \)かつ\( x \notin R \)となるので矛盾する。\( x \notin R \)とすると、\( R \)の定義から\( x \in f(x) = R \)であり、\( x \in R \)かつ\( x \notin R \)となるので矛盾する。以上より、\( f(x) = R \)を満たす\( x \in S \)は存在しない。\( S \)が集合であることから\( R \)も集合であり、従って\( R \in \mathscr{P}(S) \setminus \textrm{im}(f) \)となる。特に\( f \)は全射でない。
ラッセルの背理やカントールの定理の証明は対角線論法と呼ばれており、特別な性質を満たさないクラスの例やとても特殊な性質を持つ写像を具体的に構成する上で強力な方法です。さて、カントールの定理から、次の系を得ます。
| 系5（カントールの定理の系） |
| 任意の集合\( S \)に対して、\( S \ll \mathscr{P}(S) \)である。 |
証明
背理法により\( S \ll \mathscr{P}(S) \)を示す。単射\( f \colon \mathscr{P}(S) \to S \)が存在すると仮定する。\( f \)は単射なので像への制限\( f |^{f(\mathscr{P}(S) )} \colon \mathscr{P}(S) \to f(\mathscr{P}(S) ) \)は全単射であり、逆写像の存在性に関する演習より逆写像\( (f |^{f(\mathscr{P}(S) )})^{-1} \colon f(\mathscr{P}(S) ) \to \mathscr{P}(S) \)がただ１つ存在する。\( \emptyset \in \mathscr{P}(S) \)に注意し、写像\( g \colon S \to \mathscr{P}(S) \)を
と定める。すなわち\( g \)は３つ組\( \mathscr{P}(S),S,\{ (T,s) \in \mathscr{P}(S) \times S \mid ( (s \in f(\mathscr{P}(S) ) ) \wedge ( (s,T) \in f) ) \vee ( (s \in S \setminus f(\mathscr{P}(S) ) ) \wedge (T = \emptyset) ) \} \)である。ここで、\( g \)は全射である。実際、任意の\( T \in \mathscr{P}(S) \)に対し、\( f(T) \in f(\mathscr{P}(S) ) \)より\( T = (f |^{f(\mathscr{P}(S) )})^{-1} ( (f |^{f(\mathscr{P}(S) )})(T) ) = (f |^{f(\mathscr{P}(S) )})^{-1}(f(T) ) = g(f(T) ) \)である。従ってカントールの定理により矛盾する。以上より、単射\( f \colon \mathscr{P}(S) \to S \)は存在しない。
カントールの定理やカントールの定理の系は集合に対する命題であり、集合とは限らないようなクラスに対しては必ずしも成り立たないことに注意して下さい。実際、集合全体のなすクラスを\( V \)と置くと\( \mathscr{P}(V) \subset V \)となることから、単射であるクラス関数として包含写像\( \mathscr{P}(V) \hookrightarrow V \)が得られます。従って、\( V \ll \mathscr{P}(V) \)でないということが分かります。特にカントールの定理の系として、集合全体が集合でないことの別証明が得られました。
実際にカントールの定理の証明を集合とは限らないクラスに適用しようとすると、どの議論で破綻するかを考えてみましょう。そうすることで、集合と集合でないクラスの違いが分かりやすくなります。
それでは対等性の概念を用いて、集合の「有限性」を定義します。
- 写像の定義へ戻る。
- コラム 集合の有限性
*1 選択公理を課さなくても「スコットのトリック（Scott's trick）」という手法を使うことで、濃度の類似物である「階数」という概念を定式化することが出来ます。
*2 cf. コラム カントール・ベルンシュタインの定理