読者です 読者をやめる 読者になる 読者になる

Corollaryは必然に。

数学ブログを開設して10カ月。まだ7記事。全部オススメ!

「逆は必ずしも真ならず」どころではなかった件

ZFC - Math tastes great!
※この画像は私のものではありませんのでシェアする際はご注意ください。


集合論の基礎しか知らない私にとってかなり不思議に思った「集合の濃度」に関するお話です。

Notationと前提知識

  • \#X(あるいは|X|)で集合Xの濃度(集合の元の個数を無限集合にも意味をもたせたもの)を表します。例えば、X=\{\text{坂崎}, \text{桜井}, \text{高見沢}\}のときは\#X=3です。
  • \mathcal{P}(X)(あるいは2^X)でXの部分集合全体の集合を表します。すなわち、\[\mathcal{P}(X)\overset{def.}{=}\{A \mid A\subset X\}.\]
  • \aleph_0\overset{def.}{=}\#\mathbb{N}自然数全体の集合の濃度を可算濃度、アレフ・ヌルなどと呼びます。)
  • \aleph\overset{def.}{=}\#\mathbb{R}(実数全体の集合の濃度を連続濃度、アレフなどと言います。)
  • ZFC公理系: 全部書くと長いので、とりあえずこの記事内では“普段あたりまえに使っている公理系”という認識で大丈夫です*1

最後に、この記事は\[\#X<\#\mathcal{P}(X),\quad\aleph_0<\aleph,\quad\#\mathcal{P}(\mathbb{N})=\#\mathbb{R}\]を理解している程度の知識がある方を想定して書いています*2


まずはこの問題

まずは集合論の演習問題にありそうな問から考えます:

\#X=\#Y ならば \#\mathcal{P}(X)=\#\mathcal{P}(Y)を証明しなさい.

これは、全単射をすぐ構成できるので比較的かんたんです。


証明. f:X\to Y全単射とする. 写像F:\mathcal{P}(X)\to\mathcal{P}(Y)
\[
F(A):=f(A)
\]と定義すれば, F全単射である. ■


F全単射であることの確認は読者に任せたいところですが、念のため記事の最後に載せておきます。必要な方はご参照ください。


本題

本日のメインは先ほど考えた問の逆の命題です。

問題
\#\mathcal{P}(X)=\#\mathcal{P}(Y)ならば\#X=\#Yか?

まずは定義に戻って考えてみましょう。まず、F:\mathcal{P}(X)\to\mathcal{P}(Y)全単射とします。このFを上手く使って、XからYへの全単射を構成できればよいのですが、意外にも困難であることに気づきます。私は1つの元から成る集合\{x\}を使って、
\[
F(\{x\})
\]が使えそうかなぁと思いましたが、これはYの部分集合(つまり、F(\{x\})\subset Y)なので一点とは限りません*3ぐぬぬ


証明の方針を変えます。対偶をとってみましょう。

問題(対偶)
\#X\neq\#Yならば\#\mathcal{P}(X)\neq\#\mathcal{P}(Y)か?


これは

\#X<\#Yならば\#\mathcal{P}(X)<\#\mathcal{P}(Y)

を証明できれば十分です。対称性から、逆向きの不等号の証明も同様です。この問題を考えていると、周知の事実である
\[\#X<\#\mathcal{P}(X)\]が使えそうな気がしませんか。お、なんか証明できそう。


証明.(?)
{\rm (i)}\;\#\mathcal{P}(X)\le\#Yのとき
\[\#X<\#\mathcal{P}(X)\le\#Y<\#\mathcal{P}(Y)\]となりますが、よく見ると\#\mathcal{P}(X)<\#\mathcal{P}(Y)が得られています。


{\rm (ii)}\;\#Y<\#\mathcal{P}(X)のとき
仮定と合わせて
\begin{equation}\label{gch}
\#X<\#Y<\#\mathcal{P}(X)
\end{equation}の場合を考える訳ですが、アレ?これ何か見たことあるぞ…。

そうです、私は気づいてしまったのです…。
一般連続体仮説を使えば、このような状況は起こり得ないということを。以上より証明完了。■


…ん? こ れ で い い の か ?


連続体仮説および一般連続体仮説とは?

連続体仮説ステートメントは次の通りです:

\begin{equation}\label{ch}
\aleph_0<\#X<\aleph
\end{equation}を満たす集合Xは存在しない.

無限集合の濃度で最も小さいのが、可算濃度\aleph_0で、それよりも真に大きいのが連続濃度\alephでした。「その間の濃度はあるの?」という問に対して、「無いよ!」と述べたのを連続体仮説と呼びます。

「仮説」と呼んでいるので未解決問題という印象を持つかもしれませんが、そうではないです。連続体仮説は、ZFC公理系において証明も反証もできない主張であること」が証明されているのです。いいですか、「証明」も「反証」もできないのです(大事なことなので2回言いました)。それを証明できるってのが不思議ですね。もうちょっと述べると、ZFCに連続体仮説を加えた公理系も無矛盾であり、連続体仮説の否定を加えた公理系でも無矛盾なのです。要するに、真でも偽でもどっちでもいいんです。このことから、連続体仮説で分岐する数学体系のパラレルワールドを作れると言っても過言ではないでしょう。すごくワクワクします!

ところで、\#\mathcal{P}(\mathbb{N})=\alephであることを思い出すと、\eqref{ch} は\[\#\mathbb{N}<\#X<\#\mathcal{P}(\mathbb{N})\]と表せますね。この「\mathbb{N}」の部分を一般の無限集合に置き換えた主張は一般連続体仮説と呼ばれています。

任意の無限集合Xに対して,\[\#X<\#Y<\#\mathcal{P}(X)\]を満たす集合Yは存在しない.

これもZFCでは証明も反証もできません。

そして、この一般連続体仮説はまさに\eqref{gch}そのものですね。私は証明も反証もできない主張を使って、あの問題を証明したのです。先ほど「こ れ で い い の か ?」と書いた理由がこれです。


GCHを使わなかったら?

やはり気がかりのは、「一般連続体仮説を使わなくても証明できるのか?」ということですね。ん~難しい。

長いこと考えましたが分かりませんでした。ということで、調べた結果を書きます。


あの問題、ZFCでは証明も反証もできないらしいです!

何だとォォ!面白いなぁ!


日本語Wiki
ZFCから独立な命題の一覧 - Wikipedia
というページを調べたらありました。
f:id:corollary2525:20170412051542p:plain

英語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.φ(・▽・ )



補足(F全単射であることの証明)

f:X\to Y全単射としたとき、写像F:\mathcal{P}(X)\to\mathcal{P}(Y)F(A):=f(A)と定義すればF全単射であること」の証明です。

まず、これを知っていると話が早いです:

写像f:X\to Yに対して次が成り立つ:

証明の概略
単射ならばf^{-1}(f(A))=A.
f^{-1}(f(A))\supset Aは明らかなのでf^{-1}(f(A))\subset Aを示す.x\in f^{-1}(f(A))とするとf(x)\in f(A)であり,f(A)の定義よりあるa\in Aがあって,f(x)=f(a)f単射なのでx=a.よってx\in A

f^{-1}(f(A))=Aならば単射.
f(x_1)=f(x_2)とする.f(x_1)=f(x_2)\in f(\{x_2\})であるからx_1\in f^{-1}(f(\{x_2\})).仮定より特にA=\{x_2\}として考えればx_1\in f^{-1}(f(\{x_2\}))=\{x_2\}.よってx_1=x_2

全射ならばf(f^{-1}(B))=B.
f(f^{-1}(B))\subset Bは明らかなのでf(f^{-1}(B))\supset Bを示す.y\in Bとするとf全射なのであるx\in Xがあってf(x)=y\in B.よってx\in f^{-1}(B)なのでf(x)\in f(f^{-1}(B)),すなわちy\in f(f^{-1}(B))

f(f^{-1}(B))=Bならば全射.
X=f^{-1}(Y)であることと,仮定より特にB=Yとして考えれば,f(X)=f(f^{-1}(Y))=Yが得られるが,これはf全射であることを示している.■

F全単射であることの証明
F単射
F(A)=F(B)とする.f(A)=f(B)となるので両辺にf^{-1}を作用させると\[f^{-1}(f(A))=f^{-1}(f(B))\]となるが,f単射なのでA=B.よってF単射である.

F全射
B\subset Yを任意にとる.A:=f^{-1}(B)とおくと、f全射なので\[F(A)=f(f^{-1}(B))=B.\]よってF全射である.■

*1:選択公理はあたりまえじゃないぞ!」という方には配慮のない表現ですがお許しください。

*2:THE ALFEEのメンバーを知っているとなおよいです。

*3:力技で、集合Yに整列順序を与え、XからYへの写像f(x):=\min F(\{x\})を定義できますが、全射とも単射とも言えないですね。ぐぬぬ