MarriageTheoremのこと

_ 2週間ほど前にTwitterで、「実数の加法群 \(\mathbb{R}\) を有理数全体からなる部分群 \(\mathbb{Q}\) で割った剰余群の濃度は \(\mathbb{R}\) の濃度より真に大きい（つまり \(|\mathbb{R}/\mathbb{Q}| > |\mathbb{R}|\) ）」…（＊１）、という不可思議な命題が ZF+DC （DCは従属選択公理）と矛盾しない（by @tenapiさん）、という驚愕の事実を教わった。より詳しい話はこのまとめの前半の最後の方を参照。

上の話の何が驚きかというと、ある集合の要素をいくつかの要素ごとに組分けした上で各組の要素をギュッと一かたまりに潰してしまうと、全体の個数が減りこそすれ個数が増えるなんてまぁあり得ないと感じるわけだが、直感的には命題（＊１）はそのような操作で全体の個数が増える場合があると主張しているわけである。そしてその主張を ZF+DC という数学の（かなり真っ当な）公理系では否定できないというのである。（ちなみに DC だけでなく選択公理 AC まで仮定すれば命題（＊１）は否定される。）

この話に触発されて、「任意の集合 \(X\) を同値関係 \(\sim\) で割った集合の濃度は \(X\) の濃度以下（つまり \(|X/{\sim}| \leq |X|\) ）」…（＊２）、という命題は（ ZFC で証明できるものの、一方で） AC とどのくらい近い強さを持っているんだろうと考えた。直感的にはこの命題（＊２）は、集合の要素をさっきみたいに組分けして各々一かたまりに潰すと全体の個数がちゃんと元々の個数以下になる、という至極尤もな性質を意味している。なので、もしこの命題を示すのに AC もしくは AC にかなり近い強さの公理が必要になるのであれば、そのことは AC の「自然さ」を示す一つの強力な状況証拠になるんじゃないかなと思ったのである。AC の「不自然さ」の象徴としてよく挙げられる命題に所謂「バナッハ=タルスキの逆理」があるが、上の事実はバナッハ=タルスキの定理が醸し出す「不自然さ」とがっぷり四つに組み合えるぐらいに強力なんじゃないかなと思っている。

少し考えたところ、ZF 上で件の命題（＊２）から「集合 \(X\) から集合 \(Y\) への単射と全射がともに存在すれば、 \(X\) から \(Y\) への全単射も存在する」という命題を導くことができ（後述）、一方で後者の命題（Weak Partition Principle, WPP と呼ばれているらしい）は任意の順序数 \(\alpha\) に対する \(\aleph_\alpha\mbox{-AC}\) （集合族の濃度を \(\aleph_\alpha\) 以下に制限した選択公理、のはず）よりも真に強いとのこと（by @ta_shim_at_nhnさん）なので、（＊２）も少なくともそれぐらいの強さは持っているということになる。これって、かなり AC に近い強さを持っていると言えるんじゃないかなぁと個人的には思っている。ちなみに、 AC → 命題（＊２） → WPP という導出関係が存在することになるけれども、二つの「→」の部分が同値なのかどうかについて私にはよくわからない。

なお、 ZF 上で命題（＊２）から WPP が導かれることの証明を記しておくと、まず、 \(X\) から \(Y\) への全射について、 \(X\) の元たちに対して「この写像での値が同じ」という同値関係 \(\sim\) を作ると、もとの写像から自然に誘導される写像 \(X/{\sim} \to Y\) は全単射である。つまり \(|Y| = |X/{\sim}|\) となり、また（＊２）より \(|X/{\sim}| \leq |X|\) なので、\(|Y| \leq |X|\) が成り立つ。一方 WPP の前提から \(|X| \leq |Y|\) でもあるので、シュレーダー=ベルンシュタインの定理より \(|X| = |Y|\) 、つまり \(X\) から \(Y\) への全単射が存在する。よって（＊２）から WPP が導かれる。

↑これを書いた直後ぐらいに、命題（＊２）は「集合 \(X\) から集合 \(Y\) への全射が存在すれば \(Y\) から \(X\) への単射が存在する」（PP と呼ばれているらしい、恐らく Partition Principle の略）の同値な別表現に他ならないという指摘（by @ta_shim_at_nhnさん）を受けていたことを発見した。ご指摘に感謝、というか上の証明を書いておきながら何故 PP との同値性に気付かないんだと自分を小一時間問い詰めたい気分である。なお、PP が AC より真に弱いのかどうかは少なくとも20年前には有名な未解決問題扱いだったらしく（参考資料）、その筋の方々が何人もおられるTwitterのTL上で指摘がないということは現在でも未解決のままなのだろうと推測される。

それにしても、上述のような基本的と思われる問題すら未解決のまま（推測）ということは、まだまだ宝の山が眠っているのだなぁと考えさせられた次第である。