ぞみさんが Kunen の『集合論-独立性証明への案内』をおすすめしていたので

ぞみさんが本についてツイートしていたので.

『集合論-独立性証明への案内』 http://www.amazon.co.jp/dp/4535783829 これ, 引っかかりそうな落とし穴を丁寧にフォローしてて捗るんだよなあ… (捗るという単語が試験期間には悪い方に作用する珍しい例だ).

Kunen の本だった. 覚えておこう.

松崎拓也, 岩根秀直, 穴井宏和, 相澤彰子, 新井紀子諸氏による論文『深い言語理解と数式処理の接合による入試数学問題解答システム』

松崎拓也, 岩根秀直, 穴井宏和, 相澤彰子, 新井紀子の諸氏による『深い言語理解と数式処理の接合による入試数学問題解答システム』 という論文が出たとのこと. 冒頭部を引用してみよう.

あらゆる数学のオブジェクトは Zermelo-Fraenkel の公理的集合論 (ZF) の (保存拡大の) 項だと考えることだできるので, ここでいう「計算」とは ZF の項の書き換えだと見做せよう. では, その計算をどこえめるべきか. 即ち, 問題文の直訳である項を, それと同等であるような無数の項のうちから, どのようなものに書き換えれば問題が「解けた」ことになるのだろうか. それを考えるヒントは, 解答群の中に見いだすことができる. 大学入試を例にとると, 証明問題以外では, 解答に現れるのは, \(y = 2ax - a2,(x < 0 \to a = 3) \wedge (x ≥ 0 \to a = 5)\), \(a_1 + · · · + a_n > 0\) のような限量記号をひとつも含まないような式である. しかも, その式は, 実閉体の理論に三角関数や指数関数などの超越関数をシンボリックにしか利用しないような拡張を行った実閉体の体系 (拡張 RCF) に弱いペアノ算術の体系を加えた体系 (\(\mathrm{RCF}^{+ }+\mathrm{PA}\)) で表現されるようなものにほぼ限られる. また, 模範解答に現れる式も, 実は \(\mathrm{RCF}^{+ }+\mathrm{PA}\) で記述可能な式が圧倒的に多いことに気づく. となれば, 問題文を同等の \(\mathrm{RCF}^{+ }+\mathrm{PA}\) の式に変換し, その式から限量記号を消去することが, 大学入試の数学問題を「解く」ことだと考えてもよいだろう.

この先の細かい部分はほぼ何を言っているのか分からないが, 試み自体がとても面白い. こんなこともやっている人がいるのか. 楽しい.

Turing 次数理論の Martin 予想をめぐる対話

ゼルプスト殿下による Turing 次数理論の Martin 予想をめぐる対話 という Togetter があった. さっぱり分からないが, 興味を持つ向きがいる可能性があるのでとりあえずリンクだけつけておきたい.

またまた, 集合論家 DIke さんと計算論家トリイロさんの対話です. 往年のヴィクトリア・デルフィノ問題について. S.Jackson による Projective Ordinals の計算の話題から, Turing Degrees のグローバルな構造に関する Martin 予想の話へと進みます.

集合論界隈, 本当に魔境という感ある.

覚書：Cantor 集合が連続体濃度である証明

色々あって, この間 Cantor 集合が話題になった. 連続体濃度を持つというのは知っていたし 3 進展開を使うとうまくいく, 的なことも知ってはいたが, 証明をきちんと追ったことがなかった. いい機会なので証明を記録しておきたい. 参考 PDF をもとに証明を書いておこう.

まず Cantor 集合を定義しておく. \(I = [0, 1]\) としよう. ここから開区間 \(I_n\) をがんがん抜いていって作る集合が Cantor 集合だ. この \(I_n\) を定義していく.

\(I_1\) は \(I\) を 3 等分したときの真ん中の (開) 区間 \(I_1 = (1/3, 2/3)\) だ. \(I_2\) は \(I \setminus I_1\) の 2 つの区間をそれぞれ 3 等分した集合の真ん中の区間の合併となる. つまり \(I_2 = (1/3^2, 2/3^2) \cup (7/3^2, 8/3^2)\) だ. これを無限回繰り返すと Cantor 集合 \(C\) になる. つまり \(C = I - \cup_n I_n\) だ.

性質のその 1: \(C\) の Lebesgue 測度は \(0\) になる.

\([0, 1] \setminus C = \cup_n I_n\) の測度が 1 であることを示せばいい. \(\left| I_n \right| = (1/3) (2/3)^n\) で \(I_n\) が互いに素なので, これを素直に足し上げて \(\left| I_n \right| = 1\) で終わり.

性質その 2: Cantor 集合は閉で nowhere dense.

nowhere dense の定義は \(\mathrm{Int} \, \overline(C) = \emptyset\). では証明.
\(C\) が閉なのは自明. \(C\) が Lebesgue 測度 0 なので, \(C\) は測度正の (開) 区間を含まない. したがって \(C\) は nowhere dense.

性質その 3: Cantor 集合は非可算集合.

全射 \(f \colon C \to [0, 1]\) を作る. \(x \in [0, 1]\) を 3 進展開する. これに合わせて \(1/3 = 0.1\), \(2/3 = 0.2\) と書く. 最初に除いた集合 \(I_1\) は \(0.1\) と \(0.2\) の間にある. これを繰り返すと, \(C\) に現れる数を 3 進展開したときに 1 は決して出てこないことが分かる.

全射を実際に構成しよう. \(x \in C\) とし, これを 3 進展開したときの 2 を全て \(1\) に変え, それを 2 進展開に読み替える写像を \(f\) とすればいい. 全射性は自明.