集合論の基礎しか知らない私にとってかなり不思議に思った「集合の濃度」に関するお話です。
Notationと必要な知識
- (あるいは)で集合の濃度(集合の元の個数を無限集合にも意味をもたせたもの)を表します。例えば、のときはです。
- (あるいは)での部分集合全体の集合を表します。すなわち、\begin{equation*}\mathcal{P}(X)\overset{def.}{=}\{A \mid A\subset X\}.\end{equation*}
- (自然数全体の集合の濃度を可算濃度、アレフ・ヌルなどと呼びます。)
- (実数全体の集合の濃度を連続濃度、アレフなどと言います。)
- ZFC公理系: 全部書くと長いので、とりあえずこの記事内では“普段あたりまえに使っている公理系”という認識で大丈夫です*1。
最後に、この記事は
\begin{equation*}
\#X<\#\mathcal{P}(X),\quad\aleph_0<\aleph,\quad\#\mathcal{P}(\mathbb{N})=\#\mathbb{R}
\end{equation*}を理解している程度の知識がある方を想定して書いています*2。
まずはこの問題
まずは集合論の演習問題にありそうな問から考えます:
これは、全単射をすぐ構成できるので比較的かんたんです。
証明 を全単射とする. 写像を
\begin{equation*}
F(A):=f(A)
\end{equation*}と定義すれば, は全単射である. ■
※が全単射であることの確認は読者に任せたいところですが、念のため記事の最後に載せておきます。必要な方はご参照ください。
本題
本日のメインは先ほど考えた問の逆の命題です。
まずは定義に戻って考えてみましょう。まず、を全単射とします。このを上手く使って、からへの全単射を構成できればよいのですが、意外にも困難であることに気づきます。私は1つの元から成る集合を使って、
\begin{equation*}
F(\{x\})
\end{equation*}が使えそうかなぁと思いましたが、これはの部分集合(つまり、)なので一点とは限りません*3。ぐぬぬ。
証明の方針を変えます。対偶をとってみましょう。
これは
を証明できれば十分です。対称性から、逆向きの不等号の証明も同様です。この問題を考えていると、周知の事実である
\begin{equation*}
\#X<\#\mathcal{P}(X)
\end{equation*}が使えそうな気がしませんか。お、なんか証明できそう。
証明(?)
のとき
\begin{equation*}\#\mathcal{P}(X)\le\#Y<\#\mathcal{P}(Y)\end{equation*}となりますが、よく見るとが得られています。
のとき
仮定と合わせて
\begin{equation}
\#X<\#Y<\#\mathcal{P}(X)\tag{1}\label{gch}
\end{equation}の場合を考える訳ですが、アレ?これ何か見たことあるぞ…。
そうです、私は気づいてしまったのです…。
「一般連続体仮説」を使えば、このような状況は起こり得ないということを。以上より証明完了。■
…ん? こ れ で い い の か ?
連続体仮説および一般連続体仮説とは?
\aleph_0<\#X<\aleph\tag{CH}\label{ch}
\end{equation}を満たす集合は存在しない.
無限集合の濃度で最も小さいのが、可算濃度で、それよりも真に大きいのが連続濃度でした。「その間の濃度はあるの?」という問に対して、「無いよ!」と述べたのを連続体仮説と呼びます。
「仮説」と呼んでいるので未解決問題という印象を持つかもしれませんが、そうではないです。「連続体仮説は、ZFC公理系において証明も反証もできない主張であること」が証明されているのです。いいですか、「証明」も「反証」もできないのです(大事なことなので2回言いました)。それを証明できるってのが不思議ですね。もうちょっと述べると、ZFCに連続体仮説を加えた公理系も無矛盾であり、連続体仮説の否定を加えた公理系でも無矛盾なのです。要するに、真でも偽でもどっちでもいいんです。このことから、連続体仮説で分岐する数学体系のパラレルワールドを作れると言っても過言ではないでしょう。すごくワクワクします!
ところで、であることを思い出すと、\eqref{ch} は\begin{equation*}\#\mathbb{N}<\#X<\#\mathcal{P}(\mathbb{N})\end{equation*}と表せますね。この「」の部分を一般の無限集合に置き換えた主張は一般連続体仮説と呼ばれています。
\begin{equation*}
\#X<\#Y<\#\mathcal{P}(X)
\end{equation*}を満たす集合は存在しない.
これもZFCでは証明も反証もできません。
そして、この一般連続体仮説はまさに\eqref{gch}そのものですね。私は証明も反証もできない主張を使って、あの問題を証明したのです。先ほど「こ れ で い い の か ?」と書いた理由がこれです。
GCHを使わなかったら?
やはり気がかりのは、「一般連続体仮説を使わなくても証明できるのか?」ということですね。ん~難しい。
長いこと考えましたが分かりませんでした。ということで、調べた結果を書きます。
あの問題、ZFCでは証明も反証もできないらしいです!
何だとォォ!面白いなぁ!
日本語Wikiの
ZFCから独立な命題の一覧 - Wikipedia
というページを調べたらありました。
英語Wikiの
List of statements independent of ZFC - Wikipedia
の方にも、いくつかZFCから独立な命題が並べられている中に
Another statement that is independent of ZFC is:
If the set S has fewer elements than T (in the sense of cardinality), then S also has fewer subsets than T.
という記述があるので私の認識は間違っていないと思います。
また、「『証明も反証もできないこと』を証明できること」をちゃんと理解するには、どうやら「強制法」という手法を理解する必要がありそうです(?)。公理的集合論はしっかり勉強したことがないので、詳細は全然分からないです。
あともう一つ分からない点は、「ZFC+¬GCHの公理系では、あの問題は反証できるのか?」ということです。もし反証できたら、GCHとあの問題が同値になるってこと?う~ん、あくまで予想ですが、これは違うような気はします。
感想とか
「PならばQ」という命題が真のとき、その逆「QならばP」は真とは限らないことを標語的に「逆は必ずしも真ならず」なんて言ったりしますが、今回扱った問題で、「逆は必ずしも証明や反証ができるとは限らない」ことがわかりました。こんなこともあるんですねー。無限集合こわっ!!
thank Q for rEaDing.φ(・▽・ )
補足(が全単射であることの証明)
「を全単射とし、写像をと定義すればは全単射であること」の証明です。
まず、これを知っていると話が早いです:
・単射ならば
は明らかなのでを示す.とするとであり,の定義よりあるがあって,.は単射なので.よって.
・ならば単射.
とする.であるから.仮定より特にとして考えれば.よって.
が全単射であることの証明
・の単射性
とする.となるので両辺にを作用させると\begin{equation*}f^{-1}(f(A))=f^{-1}(f(B))\end{equation*}となるが,は単射なので.よっては単射である.
・の全射性
を任意にとる.とおくと、は全射なので\begin{equation*}F(A)=f(f^{-1}(B))=B.\end{equation*}よっては全射である.■