えっ、別に集合論の勉強なんてしなくてもどんどん質問してくださっていいんですよ。例えばスクールデイズで一番好きなのはどのキャラですかとか。

ask.fmに書いた回答が見られなくなっているので、こちらにサルベージしておきます。ネタバレ注意。

 

Q. 集合論を勉強したら質問しに来ますね。

A.  えっ、別に集合論の勉強なんてしなくてもどんどん質問してくださっていいんですよ。例えばスクールデイズで一番好きなのはどのキャラですかとか。
【以降、ネタバレ注意】
もうここは桂言葉で譲れないですね。ああ、アニメしか観ていないことは断っておきますが、厨二病なのでできるだけ主人公を推しキャラにしたくないという気持ちがはいってしまうんですが、あんなに素晴らしいヤンデレに脳がやられない方がおかしいです。
いや、本当は途中まで刹那がいいかなとか思ってたんですよ。見た目はともかく立ち位置みたいなのが。でも、戦略家ぶっている割には、世界と誠をくっつける作戦も絶望的に全て失敗しているし、身体を差し出してまで乙女を切り離そうとして、でも結局は誠の自堕落を加速させることにしかなっていなかった気がする。
ここがよくわかってなくて、フランスに出発するまでずっと世界のことを思って行動していたようなのに、最終回で突然(世界の妄想の中とはいえ)世界を偽善者と責めたてたのはどういうことなんですかね。ちょっとこのあたりの刹那の気持ちが把握できない。いや、矛盾した感情が錯綜しているのだろうけど。
そもそも、なんで誠は刹那を追って空港まで来たのだろう。もうあの時点では誠は「面倒くさい」ばかり言っていたのに、その彼を突き動かしたのはなんだったんだろう。うーん、エンディングテーマスキップしたりするときになんか見逃してるのかなぁ。
ああ、でもともかく刹那はどうでもいいよ。偽善者いうんだったら、結果的にあんなにひどい状況しか残せなかった彼女の方だろうに。
とにかく言葉ですよ。あの濁った目で歩道橋の上に立っているのを見た時点ですでにノックアウトですね。ところで、あのときに持っていた大きなバッグの中身は何なんでしょう？
やっぱりゲームやってさまざまな可能性を見ないことには理解できないことがたくさんあるな。ああ、私の知らない桂言葉がこの世に存在していることが悔しい。
そしてブランコの上で繋がっていない携帯に話し続ける。内容はといえば「また西園寺さんも誘って一緒に屋上で食べましょう」。ああ、素晴らしい。素晴らし過ぎる。ナタ持って振り回すなんざ誰でもやるでしょう？そうじゃなくて、こうやって静かに狂う、その狂気が愛おしいじゃないですか。
そして、充電の切れた携帯にクリスマスツリーの下で待ちあわせと言い、頭に雪が積もるまで待ち続ける。もうダメ。あのシーン好き過ぎる。
愛の深さが違いすぎるんですよ。誠の彼女でない自分というものを全く想像できない。「好きじゃない」と言われた後にですよ？世界が妊娠したと聞いて離れていく他の女の子とは違うんです。「そんなことをいう奴じゃなかったよね」なんて軟弱なことをいう乙女とは違うんです。そして、誠が思い通りにならなかったからといって怒り出す世界とは違うんです。
っていうか、世界は弱すぎるでしょ。言葉と比べると。言葉は、誠と世界の関係を知っても、彼らがフォークダンスを踊ってキスまでしているのを見ても、自分が誠の恋人であることを疑わなかったんですよ。たった一回の浮気を見ただけで寝込む世界とは格が違いますよ。
第一、誠を殺したあと逃げるとか最低だろ。刃物を持ってヤンデレぶったところで、やっぱり覚悟の違いはでるよな。屋上でバッグの中に入っている首をみて吐くし。
それと比べて、「やっと二人きりですね、誠くん」と言える言葉の愛情の深さ。もうなるへくしてなった必然の結末ですな。
というわけで、皆さんコトノハサマを崇めましょう。
…なんの話だっけ。

 

ask.fmに来た、凸n角形を作れる点集合についての問題を解いた

久しぶりにask.fmの字数制限にひっかかったので。ろくにチェックしてないけどもう投げる。問題は

「平面上にn>3個の点があるとする。それを結んで凸n角形を作ることができるための必要十分条件は、"そのn個の点からどのように3つの点を選んでもその3つの点を結んでできる3角形の内部（境界含む）に他の点が入らないこと"である」を証明または反証してください。

曲がりなりにも数学者にただで問題を解けとはふてえやろうだと思いつつ、門前払いするのも逃げたような気がするので考えてしまった。

まず、必要条件であることは簡単で、三角形ABCの内部にDがあると、どんなふうに凸n角形を作ろうがA, B, Cが頂点にある限りDはその内部に入ってしまうので凸n角形の頂点にならない。

というわけで十分条件になることを証明する。わりと図を描くと明らかなんだよね。凸n角形があったとき、もう一点Eをとってくると、その凸n角形上の連続した点A, B, C, Dで、Fを直線ABと直線CDの交点としたときに、Eが三角形BCFの内部に入るようなものが存在する。ここで、EをBとCの間に入れてやると凸(n+1)角形が作れる。
でも、図を描いて証明とするのが、図に騙されそうで嫌なのと、基本的にスマホで書いているのでお絵かきしにくいという事情で、代数的な証明を書くぞと思ったらとんでもなく時間がかかってしまった。

多分、ほとんど車輪の再発明なんだろうなぁ。もうこれ誰も読まないだろうけど、一応置いとく。「vの(特定の)法線とwの内積」とかの記号を準備して、projectionとか使っていったほうがはるかに簡単に書けた気がする。

A, B∈R^2に対して、v(A, B)でAからBへのベクトルを表すことにする。

とりあえず、全ての点が一直線に並んでいるケースは除外。その端の点から端の点までの線分はある意味凸n角形にも見えるけど、すごく特殊だ。

A, B, C, D∈R^2に対して、A, B, Cが同一線上にないとき、実数r1(D, A, B, C)とr2(D, A, B, C)をv(A, D)=r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)となるようなものとしてとる。要するにv(A, D)を基底{v(A, B), v(A, C)}について表現したもの。r2(D, A, B, C)=r1(D, A, C, B)なんだけど、気分がでないので両方定義しておく。

(補題1)R^2の有限部分集合Xが"そのn個の点からどのように3つの点を選んでもその3つの点を結んでできる3角形の内部（境界含む）に他の点が入らないこと"を満たすことと、任意のA, B, C, D∈Xに対して、
(i)r1(D, A, B, C)≠0かつr2(D, A, B, C)≠0
(ii)r1(D, A, B, C)<0ならば、r2(D, A, B, C)>0
が成り立つことは同値。

(証明) (⇒)まず、三点が一直線上にならばないことを証明する。A, B, C∈Xが一直線上にこの順番で並んでいたとする。このとき、この直線上にない一点D∈Xをとると、三角形ACD内にBがあるので条件に反する。

さて、任意のA, B, C, D∈Xをとって、b=r1(D, A, B, C), d=r2(D, A, B, C)とする。Xに属する三点が同一線上に並ばないことからb≠0かつc≠0。b<0を仮定し、c>0を導くためにc<0を仮定する。このとき、(-b)v(A, B)+(-c)v(A, C)+v(A, D)=0(ベクトル)か言える。よって、明らかにAは三角形BCDの内部にある。これは矛盾。

いや明らかにって書いたし絵を描くと明らかっぽく見えるけど、どうきっちり書けばよいのだろう。三角形は凸だから、三角形BCDの境界を含む内部はv(A, E)=b' v(A, B)+c' v(A, C)+d' v(A, D)かつb', c', d'>0かつb'+c'+d'=1をみたすようなE全体の集合になる。というわけで、Aが三角形BCDの境界を含む内部に属するためにはb' v(A, B)+c' v(A, C)+d' v(A, D)=0かつb', c', d'>0かつb'+c'+d'=1をみたすようなb', c', d'があればよい。のだけど、b'+c'+d'=1以外の条件はb', c', d'を同時に定数倍してもみたされ続けるので、b'+c'+d'=1をみたすように変更することは容易。ってことで、大丈夫かな。

(⇐)任意のA, B, C, D∈Xに対して、Dが三角形ABCの内部に属さないことを示す。背理法のため、Dが三角形ABCの内部に属していると仮定する。b=r1(D, A, B, C), d=r2(D, A, B, C)とする。このとき、条件によりb≠0かつc≠0。また、Dが三角形ABCの内部に属していることよりb>0かつc>0かつb+c≦1となる。
すると、v(A, C)=(-b/c) v(A, B)+(1/c) v(A, D)。ここで、v(D, A)=-v(A, D)かつv(A, B)=-v(D, A)+v(D, B)であることを使うと、v(A, C)=(-b/c) (-v(D, A)+v(D, B) )+(-1/c) v(D, A)=(-b/c) v(D, B)+( (b-1)/c) v(D, A)。すると、b+c≦1であることから、b-1≦-c<0。よって、(-b/c) <0かつ(b-1)/c<0。これは条件に矛盾する。
(補題証明了)

この条件を(*)とでも書こうか。

(補題2) 任意の点A, B, C, Dに対して、
(i) r1(D, B, A, C)=r1(D, C, A, B)=1-r1(D, A, B, C)-r2(D, A, B, C)、
(ii) r2(D, B, A, C)=r2(D, A, B, C)
(iii) r2(D, C, A, B)=r1(D, A, B, C)、
(証明)
v(B, D)=v(B, A)+v(A, D)=v(B, A)+r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)=v(B, A)-r1(D, A, B, C) v(B, A)+r2(D, A, B, C) (v(A, B)+v(B, C))=v(B, A)-r1(D, A, B, C) v(A, B)-r2(D, A, B, C) v(B, A)+r2(D, A, B, C) v(B, C)=(1-r1(D, A, B, C)-r2(D, A, B, C)) v(B, A)+r2(D, A, B, C) v(B, C)。よって, r1(D, B, A, C)=1-r1(D, A, B, C)-r2(D, A, B, C)かつr2(D, B, A, C)=r2(D, A, B, C)。

前段の結果を使うと、r1(D, C, A, B)=1-r1(D, A, C, C)-r2(D, A, B, C)
(証明了)

もう一つ補題。
(補題3){A, B, C, D}が(*)をみたすとする。もし、r1(D, A, B, C)<0ならば、
(i) r2(D, A, B, C)<1-r1(D, A, B, C)
(ii) r1(D, C, A, B)>0かつr2(D, C, A, B)<0
(iii) r1(D, B, A, C)>0かつr2(D, B, A, C)>0。

(証明)
(i) 補題2により、r1(D, C, A, B)=1-r2(D, A, B, C)-r1(D, A, B, C)かつr2(D, C, A, B)=r1(D, A, B, C)。すると、r2(D, C, A, B)<0なので、r1(D, C, A, B)>0。補題2により、1-r2(D, A, B, C)-r1(D, A, B, C)=r1(D, C, A, B)。よって、1-r2(D, A, B, C)-r1(D, A, B, C)>0なので、r1(D, A, B, C)<1-r2(D, A, B, C)。

(ii) (i)の証明より。

(iii) v(B, D)=v(B, A)+v(A, D)=v(B, A)+r1(D, A, B, C) v(A, B)+r2(D, A, B, C) v(A, C)=(1-r1(D, A, B, C) ) v(B, A)+r2(D, A, B, C) (v(A, B)+v(B, C) )=(1-r1(D, A, B, C)-r2(D, A, B, C) ) v(B, A)+r2(D, A, B, C) v(B, C)。よって、(i)よりr1(D, B, A, C)=1-r1(D, A, B, C)-r2(D, A, B, C)>0 かつr2(D, B, A, C)=r2(D, A, B, C)>0。
(証明了)

(補題4)
A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してr1(A_k, A_i, A_{i-1}, A_{i+1})>0となることは同値。なお、Aの添字はmod nで考えてもらうことにして、例えばi=1のときは、r1(A_k, A_1, A_n, A_2)>0と解釈する。
(証明)
ここで、n(A_i, A_{i+1})を、A_i A_{i+1}の単位法線ベクトルで、v(A_i, A_{i-1})・n(A_i, A_{i+1})>0となるようなものとする。すると、A_iとA_{i+1}を通る直線を考えて平面をそれで2つの部分に分けたとき、任意のk≠i, i+1に対してA_{i-1}とA_kが同じ部分に入るということと、v(A_i, A_k)・n(A_i, A_{i+1})>0が同値になる。というわけで、まず、A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してv(A_i, A_k)・n(A_i, A_{i+1})>0が成り立つことが同値となる。

よって、任意のiとkに対して、v(A_i, A_k)・n(A_i, A_{i+1})とr1(A_k, A_i, A_{i-1}, A_{i+1})の符号が一致することをいえばよい。これは、v(A_i, A_k)・n(A_i, A_{i+1})=(r1(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i-1})+r2(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i+1}))・n(A_i, A_{i+1})=r1(A_k, A_i, A_{i-1}, A_{i+1}) v(A_i, A_{i-1})・n(A_i, A_{i+1})となるので、v(A_i, A_{i-1})・n(A_i, A_{i+1})>0となることからいえる。
(証明了)

(補題4')A_1, A_2, …, A_nが凸n角形になることと、任意のiとk≠i, i+1に対してr1(A_k, A_i, A_{i-1}, A_{i+1})>0かつr2(A_k, A_i, A_{i-1}, A_{i+1})>となることは同値。

ここまでくれば大丈夫。帰納法でやることにする。n≧3を自然数として、任意のR^2のn元部分集合Xに対して、(*)が成り立てばXの元を結んで凸n角形をつくることができることを仮定する。ここで、任意のR^2のn+1元部分集合Xに対して、(*)が成り立てばXの元を結んで凸(n+1)角形をつくることを示す。Xの元Dを任意に取り、X'=X\{D}とする。帰納法の仮定により、X'の元を結んだn凸角形A_1, …, A_nが存在する。

(補題5)r1(D, A_i, A_{i-1}, A_{i+1})<0となるようなiが一つだけ存在する。
(証明) さすがにめんどうになってきた。絵を描けばわかるでしょ。∠A_i A_1 A_2 < ∠D A_1 A_2 < A_{i+1} A_1 A_2となるようなiをとればよい。一意性もいいよね。
(証明了)

ここで、A_1, …, A_i, D, A_{i+1}, …, A_nが凸(n+1)角形となることを示す。
必要なら添字を振り直して、i=2を仮定してもよい。ここで、
(i) 任意のk≠1,2に対して、r1(A_k, A_2, A_1, D)>0
(ii) 任意のk≠3, 4に対して、r1(A_k, A_3, D, A_4)>0
(iii) 任意のk≠2, 3に対して、r1(A_k, D, A_2, A_3)>0
(iv) 任意のk≠2, 3に対してr1(D, A_k, A_{k-1}, A_k)>0
をいえばよい。b=r1(D, A_2, A_1, A_3), c=r2(D, A_2, A_1, A_3)とする。b<0かつc>0となることに注意。b'=r1(D, A_3, A_2, A_4), c'=r2(D, A_3, A_2, A_4)とする。

(Claim) b'>0かつc'<0
(証明)
v(A_3, D)=v(A_3, A_2)+v(A_2, D)=v(A_3, A_2)+b v(A_2, A_1)+c v(A_2, A_3)=(1-c) v(A_3, A_2)+b v(A_2, A_1)
=(1-c) v(A_3, A_2)+b (v(A_3, A_1)-v(A_3, A_2))=(1-c-b) v(A_3, A_2) +b (r1(A_1, A_3, A_2, A_4)v(A_3, A_2)+r2(A_1, A_3, A_2, A_4)v(A_3, A_4))=(1-c-b+b (r1(A_1, A_3, A_2, A_4)) v(A_3, A_2) +b r1(A_1, A_3, A_2, A_4) v(A_3, A_4)。よって、r2(D, A_3, A_2, A_4)=b r1(A_1, A_3, A_2, A_4)<0。よって、r1(D, A_3, A_2, A_4)>0。
(Claim証明了)

(i) 任意のkに対して、r1(A_k, A_2, A_1, D)>0

まず、v(A_2, D)=b v(A_2, A_1)+c v(A_2, A_3)なのでv(A_2, A_3)=(-b/c) v(A_2, A_1)+(1/c) v(A_2, D)。

よって、v(A_2, A_k)=r1(A_k, A_2, A_1, A_3) v(A_2, A_1)+r2(A_k, A_2, A_1, A_3) v(A_2, A_3)=r1(A_k, A_2, A_1, A_3) v(A_2, A_1)+r2(A_k, A_2, A_1, A_3) ( (-b/c) v(A_2, A_1)+(1/c) v(A_2, D) )=(r1(A_k, A_2, A_1, A_3)-r2(A_k, A_2, A_1, A_3) (b/c) ) v(A_2, A_1)+(r2(A_k, A_2, A_1, A_3)/c) v(A_2, D)。よって、r1(A_k, A_2, A_1, D)=r1(A_k, A_2, A_1, A_3)-r2(A_k, A_2, A_1, A_3) (b/c)>0。

(ii) 任意のkに対して、r1(A_k, A_3, D, A_4)>0

v(A_3, D)=b' v(A_3, A_2)+c' v(A_3, A_4)なので、
v(A_3, A_2)=(v(A_3, D)-c' v(A_3, A_4))/b'。よって、r1(A_2, A_3, D, A_4)>0かつr2(A_2, A_3, D, A_4)>0。
すると、v(A_3, A_k)=r1(A_k, A_3, A_2, A_4) v(A_3, A_2)+r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=r1(A_k, A_3, A_2, A_4) (r1(A_2, A_3, D, A_4) v(A_3, D)+r2(A_2, A_3, D, A_4) v(A_3, A_4))+r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=r1(A_k, A_3, A_2, A_4) r1(A_2, A_3, D, A_4) v(A_3, D)+(r1(A_k, A_3, A_2, A_4) r2(A_2, A_3, D, A_4)+r2(A_k, A_3, A_2, A_4))v(A_3, A_4)。これにより、r1(A_k, A_3, D, A_4)=r1(A_k, A_3, A_2, A_4) r1(A_2, A_3, D, A_4)>0。

(iii) 任意のkに対して、r1(A_k, D, A_2, A_3)>0

v(A_3, D)=b' v(A_3, A_2)+c' v(A_3, A_4)なので、v(A_3, A_4)=(1/c') v(A_3, D)-(b'/c') v(A_3, A_2)=(1/c') v(A_3, D)-(b'/c') (v(D, A_2)-v(D, A_3))=-(b'/c') v(D, A_2)+(-1/c'+b'/c') v(D, A_3)

v(D, A_k)=v(D, A_3)+r1(A_k, A_3, A_2, A_4) v(A_3, A_2) +r2(A_k, A_3, A_2, A_4) v(A_3, A_4)=v(D, A_3)+r1(A_k, A_3, A_2, A_4) (v(D, A_2)-v(D, A_3))+r2(A_k, A_3, A_2, A_4) (-(b'/c') v(D, A_2)+(-1/c'+b'/c') v(D, A_3))=(r1(A_k, A_3, A_2, A_4)-r2(A_k, A_3, A_2, A_4) (b'/c'))v(D, A_2)+(1-r1(A_k, A_3, A_2, A_4)+r2(A_k, A_3, A_2, A_4) (-1/c'+b'/c') )v(D, A_3))。よって、r1(A_k, D, A_2, A_3)=(r1(A_k, A_3, A_2, A_4)-r2(A_k, A_3, A_2, A_4) (b'/c'))>0

(iv) 任意のkに対してr1(D, A_k, A_{k-1}, A_k)>0

補題5による。

      • -

興味があるのは、これはより高い次元に拡張できるのかってことだけど、えーと、誰か教えて。

【club guessing sequenceの存在定理の、κが可算の場合の数学ガール風解説が読みたいです】を書いた

放課後、いつも通り図書室に来てみるとテトラちゃんがなにやら難しい顔をして本とにらめっこしていた。
僕「今度は何を読んでいるの？」
テトラ「あ、先輩。…この前、ミルカ先輩がclub guessing sequence(CG列)の存在証明を教えて下さいましたよね」
僕「ああ、随分と前だけどね。μとκが正則基数でμ^+<κをみたすようなものならば、κ∩Cof(μ)上にCG列が存在する」
テトラ「あの、Cof(μ)ってなんですか？」
僕「ああ、共終数がμになる順序数からなるクラスだよ。」
テトラ「あ、そうなんですか。この本では違う表記になっていて…」
と言われてみた本の表紙にはS.Shelah Cardinal Arithmetic！
僕「いや、その本は最初に学ぶためのものとしては勧められないよ。そういえば、数年前に『数学』にサーベイが…」
ミルカ「ふぅん、CG列の存在証明ね。」
僕「うわっ」
いつもながら唐突な登場だ。
ミルカ「それでテトラは何を知りたかったの？」
テトラ「はい、先輩が証明してくださったときはμが非可算なことを仮定したじゃないですか。」
僕「そうだったね。その方が簡単だからまずそうしようと言ってたね」
テトラ「でも、定理はμが可算でも成り立つんですよね。それが気になっちゃって。」
それを聞いたミルカさんは天井を見て少し考えると言った。
ミルカ「そこまでならそんなに難しくない。でも場所を変えようか」
ふと周囲を見渡すと、瑞谷女史をはじめとするみんなの冷たい視線を感じる。

近くの教室に移動するとミルカさんはチョークをとって話し始める。

      • -

まずそれぞれのβ∈κ∩Cof(ω)に対して、順序型ωなβの非有界部分集合C_βをとろうか。喜ぶ人もいるだろうから言っておくと、(C_β : β∈κ∩Cof(ω))を取る時点で選択公理が必要だ。
さて、κ∩Cof(ω)上にCG列がないと仮定しようか。すると、κのclub部分集合Dで、{β∈κ∩Cof(ω) : C_β⊆D}が非定常になるようなものが存在するわけだな。

      • -

テトラ「ここで、μが非可算のときはC_β∩Dを新しい列として、同じことを繰り返しました。でも、βが可算のときは、βがDの極限だったとしてもC_β∩Dがβ上非有界とは限りません。空集合にだってなります」
ミルカ「そう。だから、ここでShelahはglue functionと読んでいたもの使う。そのページのglだよ。いろんな状況に対処するためにそこの定義には細かい細工がしてあるけれども、私たちの目的にははるかに単純なもので良い。」

    • -

gl(C, D)を{sup(γ∩D) : min(D)<γ∈C}で定義しよう。意図としては、Dはκのclub部分集合、Cはκの部分集合で順序型はω。βをsup(C)としておこう。
この関数は下記の性質を持っている:
(i) gl(C, D)⊆D
(ii) βがDの極限点であるならば、gl(C, D)はΒの非有界部分集合。
(iii) gl(C, D)=CとC⊆Dは同値

このgl(C, D)をC∩Dの代わりに使うんだ。

    • -

テトラ「はわわわ」
大声をあげたテトラちゃんをみるミルカさんと僕。
テトラ「この子たちはパラシュートをつけてるんですよ」
そう言うと、テトラちゃんはノートに絵を描き始める。
テトラ「Cの元の子たちγは持ち場で待機してるんですよ。そこにDがくると、μが非可算のときはγ∈Dのときだけ合格で、γ∉Dだと失格しちゃうんです。」
ミルカ「続けて」
テトラ「でも今度はパラシュート付きだから、γちゃんはゆっくりおちながらDの元を探して最初に見つかったところで止まるんです。」
僕「min(D)<γだから見つからなかったら失格ってことかな。」
ミルカ「そういうこと。そうやって探しにいくから、(ii)が成り立つ。」

      • -

そして、全てのξ<ω_1に対して帰納的に(C^ξ_β : β∈κ∩Cof(ω))とD_ξを定義する。帰納法の仮定は、任意のβ∈κ∩Cof(ω)に対してC^ξ_βがβの非有界部分集合となっていることとD_ξはκのclub部分集合で、任意のη<ξに対してD_ξ⊆D_η。

まず、全てのβ∈κ∩Cof(ω)に対してC^0_β=C_βとし、またD_0をκより小さい極限順序数全体の集合とする。

帰納法の仮定を満たすようにD_ξと
(C^ξ_β : β∈κ∩Cof(ω))が定義されているとする。このとき、(C^ξ_β : β∈κ∩Cof(ω))はCG列ではないので、任意のβに対してC^ξ_β⊆D_{ξ+1}が成り立たないようなκのclub部分集合D_{ξ+1}が存在する。clubである限りD_{ξ+1}は小さくしても求められた性質を持ち続けるのでD_{ξ+1}⊆D_ξを仮定しても一般性を失わない。任意のβに対して、βがD_{ξ+1}の極限点であるときはC^{ξ+1}_β=C_β、そうでないときはC^{ξ+1}_β=gl(C_β, D_{ξ+1})とする。

ξが極限順序数だとするときは、D_ξ=∩_{η<ξ}D_ηとする。そして、任意のβに対して、βがD_ξの極限点ならばC^ξ_β=C_β、そうでないときはC^ξ_β=gl(C_β, D_ξ)とする。

      • -

僕「つまり、D_ξが定義されたらそこからC^ξ_βを定義する方法はξが後続順序数でも極限順序数でも同じなのか。」
ミルカ「そう。でもこの方がイメージしやすい。」

      • -

さて、ここでD=∩_{ξ<ω_1}D_ξとしよう。そしてβをDの極限点でありかつκ∩Cof(ω)の元となるようなものとする。ここで、示したいのはC^ξ_β=C^{ξ+1}_βとなるようなξ<ω_1が存在すること。

まず、これが示せたとして矛盾を出しておこうか。D⊆D_ξかつβはDの極限点なので、βはD_ξの極限点でもある。C^{ξ+1}_βの構成により、C^{ξ+1}_β=gl(C_β, D_{ξ+1})となる。glの性質からgl(C_β, D_{ξ+1})⊆D_{ξ+1}となり、C^ξ_β⊆D_{ξ+1}が言える。これはD_{ξ+1}の構成に矛盾する。

      • -

僕「えーと、D_{ξ+1}の構成っていうのは…」
一足先にノートを遡っていたテトラちゃんがこたえる。
テトラ「これですよ、先輩。【このとき、(C^ξ_β : β∈κ∩Cof(ω))はCG列ではないので、任意のβに対してC^ξ_β⊆D_{ξ+1}が成り立たないようなκのclub部分集合D_{ξ+1}が存在する。】まさにD_{ξ+1}の取り方に反しているんですね」
ミルカ「そう、反例のはずが反例でないことを示すわけだ。」

      • -

それじゃあC^ξ_β=C^{ξ+1}_βとなるようなξ<ω_1が存在することを証明しよう。
まず、最初に。(min(D_ξ) : ξ<ω_1)は非減少列で、βを上界にもつ。cf(β)=ωだからこの列は上昇し続けることはできずに途中でとまる。すなわち、ζ'<ω_1とδが存在して、任意のζ'≦ξ<ω_1にたいして、min(D_ξ)=δを満たす。

次に以下の補題を証明する。

補題: 任意のγ∈C_βに対して、以下を満たすようなζ_γ<ω_1が存在する:
任意のζ_γ≦ξ<ω_1に対して min(D_ξ)<γならば sup(γ∩D_ξ)=sup(γ∩D_{ζ_γ})

      • -

テトラ「えっとえっと」
僕「落ち着いて。ひとつひとつ読んでいこう。任意のζ_γ≦ξ<ω_1が満たさないといけないのは【min(D_ξ)<γ ならば sup(γ∩D_ξ)=sup(γ∩D_{ζ_γ})】という条件だ。まず、min(D_ξ)<γってどういうことだろう。」
テトラ「D_ξは帰納的に定義されたκのclub部分集合でした。」
僕「うん。min(D_ξ)<γが満たされると、γ∩D_ξという集合にはどういう影響があるだろう。」
テトラ「γ∩D_ξはγより小さいD_ξの元全体だから。あっ、わかりました。min(D_ξ)<γはγ∩D_ξ≠∅と同値です。つまりsup(γ∩D_ξ)が計算できるってことですね。」
僕「そういうこと。だから、sup(γ∩D_ξ)が計算できるならそれはsup(γ∩D_{ζ_γ})と等しいってことを言っているわけ。」
テトラ「でもsup(γ∩D_{ζ_γ})はどうして計算できるんですか？」
ミルカ「(D_ξ : ξ<ω_1)はどんな性質を持つか」
僕「そうか、(D_ξ : ξ<ω_1)は下降列なんだ」
テトラ「どういうことですか？」
僕「D_{ξ+1}をとるときにはD_ξの部分集合であることを条件に入れているし、ξが極限のときはD_ξ=∩_{η<ξ}D_ηとしている。だから、任意のη<ξ<ω_1に対してD_ξ⊆D_ηが言えるんだよ。だから、ζ_γ≦ξという仮定からD_ξ⊆D_{ζ_γ}がいえる。ということは、γ∩D_ξが空でないならγ∩D_{ζ_γ}だって空じゃないんだ」
ミルカ「じゃあ、(sup(γ∩D_ξ) : γ<ω_1)はどんな列？」
テトラ「わかりました。(D_ξ : ξ<ω_1)は下降列だから、(sup(γ∩D_ξ) : γ<ω_1)は減少列になります。」
ミルカ「正確にはnon-increasing。」
僕「そして、順序数の非上昇列はどこかで止まっているということか！」
ミルカ「そう。だからζ_γが存在する。」
テトラ「補題が証明できました。」

      • -

ここで、ζ=sup({ζ_γ : γ∈C_β}∪{ζ'})とする。すると、任意のζ≦ξ<ω_1に対してまずmin(C_ξ)=δが言える。だから、C^ξ_β=gl(C_β, D_ξ)={sup(γ∩D_ξ)}: min(D_ξ)<γ∈C_β}={sup(γ∩D_ξ)}: δ<γ∈C_β}。ところが、δ<γ∈C_βを満たす任意のγに対して、ξ≧ζ≧ζ_γから sup(γ∩D_ξ)=sup(γ∩D_ζ)が言える。すなわち、C^ξ_β={sup(γ∩D_ζ)}: δ<γ∈C_β}となる。
つまり、任意のζ≦ξ<ω_1に対してC^ξ_βをξに依存せずに記述できたことになる。だから、C^ξ_β=C^{ξ+1}_βも言える。

      • -

ミルカ「これで一仕事おしまい」
テトラ「えっ、補題が証明できただけじゃ…」
僕「ほら、ここで補題が言えたら定理が言えることを示しているよ」
ノートの該当部分を指差しながら言うとテトラちゃんはうなずきながら答える。
テトラ「ああっ、そうでした。ごめんなさい」
ミルカさんは僕らが納得したのを確認すると座ってチョコレートを食べ始めた。テトラちゃんはノートを最初から読み返している。
テトラ「なんか大変でした」
ミルカ「そう？cf(μ)が非可算のときとの本質的な違いは最初から把握していたようだけど」
僕「パラシュート？」
ミルカ「そういうこと。パラシュートって例えは思いつかなかったけど。そこさえわかればあとは一緒。細かい調整をするだけ。」
僕「順序数って単純そうに見えるのに、いろんなことができるんだね。」
ミルカ「無限下降列がないというのはとても重要な性質だ。そのことはこの証明だけではなく、例えばTodorcevicの最小歩行理論では縦横無尽に使われている」
テトラ「あの、CG列の存在を証明しているのに、CG列は構成しないんですね」
ミルカ「そう、そしてそれは本質的。一つ一つのCG列は強制法で壊せる。でも全部壊すと基数まで崩れる」
テトラ「不思議ですね。自然界が微妙なバランスを保っているのと似ているんでしょうか」
ミルカ「どうだろうね。まあ、ZFCのモデルというのも人工的で無味乾燥かとも思えるけれども、わりとそうでもないのかもしれない。」
僕「あれ、そういえば、証明を始める前に『そこまでならそんなに難しくない』と言っていたよね。その先っていうのは何？」
ミルカ「C_β⊆Cof(>ω)って条件を付け加えることができるんだ。そして、その条件がついたCG列を使って、κ上の非定常イデアルをCof(ω)に制限したものが飽和にならないことを示したのがGitik and Shelah。それは私の知る限りもう少し厄介な証明になる」
僕「そういえば、『数学』のサーベイにそんなことが…」
エィエィ「ミルカたん！」
突然ドアの方から声が。
エィエィ「みんなも。さすがにその辺にしとかんと怒られるで。こんな遅くまで。」
ミルカ「そうだな、違う意味でも怒られそうだ」
テトラ「帰りましょう！」

      • -

超力尽きた。いろいろ変だったり間違ってたりしてそうだけど、とりあえず晒す。

基数のべきについて答えてみた

[集合論] GCHが成り立たないときのべきの値

にゃー、みんなボクが『数学』に書いたサーベイ読んでにゃー。

正則基数のべき(Eastonの定理)

今更入手困難でしょうし書きますよ。まず、αを無限順序数とするとき、それの非有界部分集合の最小濃度をαの共終数(cofinality)といい、cf(α)で表す。そうそう、α={β: β<α}なので、αの部分集合というのは、αより小さい順序数からなる集合のこと。
κを基数とするとき、cf(κ)=κとなるときに、κは正則(regular)であるといい、そうでないときは特異(singular)であるという。ωは正則で、全ての後続基数は正則。 \aleph_\omegaは最小の特異基数。正則な極限基数は弱到達不可能基数と呼ばれていて、通常は最も小さい巨大基数とされる。特に、ZFCからはその存在を言うことはできない。つまり、特異でない極限基数は「特にでかい」のだ、あっはっはー。

(沈黙)

正則な基数は圧倒的に扱いやすく、Eastonによる以下の定理が強制法の開発後結構早い段階で証明されている。

−−−−
GCHを仮定する。Fを次の条件を満たすような、正則基数全体のクラスを定義域とするクラス関数とする。

(i) 任意のκ<λに対して、F(κ)≦F(λ)
(ii) cf(F(κ))>κ(ケーニッヒの補題)

このとき、共終性を保つような強制拡大で、任意の正則基数κに対して2^κ=F(κ)が成り立つようなものが存在する。
−−−−

いくつか補足しないとダメかな。まず、(i)と(ii)はF(κ)=2^κとするとZFCで証明できる性質。つまり、2^κ=F(κ)を満たすモデルが存在するための必要条件。
強制拡大というのは、強制法というテクニックで作られた、拡大されたZFCのモデル。元のモデルをVと書いて、Wをその拡大とする。
共終性を保つっていうのは、cf(α)の値がVで計算してもWで計算してもかわらないということ。このことから、基数を保つこと、すなわち任意のV上の基数κが、W上でも基数であることが導かれる。非可算な基数をぶっこわす強制法は簡単に作れるので、重要な性質。
えーと、すでにこんがらがっている人が多いと思うのでざっくりいくと、要するに正則基数に関しては(i)と(ii)という必要条件を満たすようにテンプレートを作ってやると、2^κをそれに従わせられるわけだ。だから正則基数についてはほぼやることはない。

非可算な共終数をもつ特異基数(Silverの定理)

じゃあ特異基数ではどうなるかというと、Jack Silverが下記の定理を証明して当時の研究者たちをびっくりさせた(と聞いている)。

−−−−
κをω<cf(κ)を満たすような特異基数とする。もし、任意のλ<κに対して2^λ=λ^+が成り立つならば、2^κ=κ^+が成り立つ。
−−−−

このことから、GCHを満たさない最小の基数は、共終数が非可算になるような特異基数ではないことが言える。この前ちょっと話題に出た整礎にならないVの超べきで最初の証明は与えられた(らしい)。もっとも今となってははるかにわかりやすい証明があるのだけど(忘れたけど)。
ダメぶりをいかんなく発揮してますな、前段落。

共終数が可算な特異基数(Magidorの定理)

じゃあ共終数が可算な特異基数、例えば \aleph_\omegaではどうかというと、Magidorが下記の定理で、Silverの定理は可算共終数のケースに拡張できないことを示した。

−−−−
ある巨大基数の無矛盾性を仮定すると、任意の自然数nに対して 2^{ℵ_n}=ℵ_{n+1}かつ2^{ℵ_ω}=ℵ_{ω+2}]
−−−−

つまり、 \aleph_\omegaはGCHを満たさない最小の基数になり得るわけ。これ、最初の証明で仮定してたのはalmost hugeだっけ？とても大きい巨大基数。最新の結果は忘れたけど、o(κ)が十分大きいやつがあれば、2^{ℵ_ω}=ℵ_{ω_1}とか言えるんだったよね。私への宿題か、これは。
ZFCのみの無矛盾性だけではダメで、巨大基数が必要なことは証明されている
証明は大技、少なくとも私には十分怖い。巨大基数κの下にある基数をω個残してバンバン潰しながら準備をして、その準備されたところを使って2^κを持ち上げる。

PCF理論とべきの上界

そんじゃあ、まだ出来てなくとも2^{ℵ_ω}はいくらでも大きくなるのかというと、そんなことはないことを示したのがShelahのPCF理論で、代表格は以下の定理。

−−−−
{ℵ_ω}^{ℵ_0}<max{ℵ_{ω_4}, (2^{ℵ_0})^+}]。
−−−−

これから、例えば任意の自然数nに対して任意の自然数nに対して2^{ℵ_n}<ℵ_ωが成り立つならば、2^{ℵ_ω}<ℵ_{ω_4}が成り立つことが言える。つまり、Magidorの定理の2^{ℵ_ω}の値にはℵ_{ω_4}という制限がかかる。この4が3に変えられるかは未解決。
「GCHを満たさない最小の基数とそのべき」の研究はこんな感じ。ここでは2^{ℵ_ω}のことしか書いてないけど、そうでない場合についても研究はある(というか、2^{ℵ_ω}は最も大変なケース)。

GCHが全ての基数で破れるモデル

別方向から。全ての基数κについてGCHが崩れるモデルを最初に作ったのはWoodinと私の師匠の共著で、そこでは任意の基数κに対して2^κ=κ^+が成り立っている。もちろん巨大基数が必要。この研究はGitikとかMerimovichとかに引き継がれて、2^κの値は色々コントロールできるようになっている(論文読もうとしたんだけど、ここがどの程度コントロールできるのかさえよくわからなかった)。

とりあえずこんな感じ。

â– 

前置き

Software Foundationちょっとずつ読んでいるわけなんだけど、数日ハマっちゃった問題が解けた上で、なんかすごくチープな解法が見つかったような気がするのでそのことも含めて書く。あ、できればこっちで勉強会とか開けるようになったらいいなという気持ちもあって英語の方を読んでいるので、翻訳ではすでに処理されていたならごめんなさい。

Basicsの方ですでにやってあるのがbinaryという練習問題で、これは、binという新しい型を全ての要素が

  • ゼロ
  • すでにあるbinの要素の2倍
  • すでにあるbinの要素の2倍足す1

になるように定義しなさいってことで、これは私でも簡単。

Inductive bin : Type := 
| bin_O : bin 
| bin_S0 : bin -> bin 
| bin_S1 : bin -> bin 
.

あー、コンストラクタの名前とかもっとスタンダートなやつがありそうですが。bin_とか最初につけているのは自分が混乱しないため。

お次は、bin型のインクリメント

Fixpoint bin_inc (a : bin) : bin :=
match a with 
| bin_O => (bin_S1 bin_O)
| bin_S0 p => (bin_S1 p)
| bin_S1 p => (bin_S0 (bin_inc p))
end.

次はbinからnatへの変換。

Fixpoint bin_to_nat (a : bin) : nat :=
match a with 
| bin_O => 0
| bin_S0 p => ((bin_to_nat p) + (bin_to_nat p))
| bin_S1 p => (S ((bin_to_nat p) + (bin_to_nat p)))
end.

この時点で全てのb:binに対してbin_to_nat (bin_inc b)=S (bin_to_nat b)を証明しようとしてinductionないとできないよ～とかつぶやいていたんですが、どうも著者はこの時点では具体的なものに関してチェックさせるだけのつもりだったようです。

そんで本題のInductionの章のbinary_inverse。まず、natからbinへの変換。bin_incがすでにあるから余裕。

Fixpoint nat_to_bin (n : nat) : bin :=
match n with 
| O => bin_O
| S p => (bin_inc (nat_to_bin p))
end.

そんで、bin_to_nat (nat_to_bin n)=nを全てのn:natに対して示せ、っていうんだけど、これも問題なし。

次はnat_to_bin (bin_to_nat b)=bは必ずしも成り立たないと考察せよ、っていうもの。いや、だって普通にbin_to_nat bin_O=0だけど、2*0=0だからbin_to_nat (bin_S0 bin_O)=0ともなるわけで無理でしょ。だから、こういう無駄なbin_S0を除かないといけない。

というわけで、次の問題はnormalizeというbinからbinへの関数を定義して、nat_to_bin (bin_to_nat b)=normalize bとなるものを書きましょう、っていうんだけど。

本題

ようやく本題。このnormalizeって、normalize b=nat_to_bin (bin_to_nat b)で定義しちゃっていいの？って話。すなわち

Definition normalize' (a : bin) : bin := nat_to_bin (bin_to_nat a).

特にこれを禁止するような文が見当たらないんですけど、どうなんでしょ。

まじめに書いたのが

Fixpoint normalize (a : bin) : bin :=
match a with 
| bin_O => bin_O
| bin_S1 b => bin_S1 (normalize b)
| bin_S0 b => 
    match (normalize b) with 
    | bin_O => bin_O
    | bin_S0 c => (bin_S0 (bin_S0 c))
    | bin_S1 c => (bin_S0 (bin_S1 c))
    end 
end.

ちょっと前まで、bin_S1 b => bin_S1 bと書いていたので証明が通るわけもなかった。この関数を使った証明もようやく通った。汚いけどねぇ。absurdとかdiscriminateとかなしでも出来るんだろうけど…。

後書き

この辺りはサクサク終えられると思っていたのに、ここで詰まっちゃってにゃーにゃーしているところ。

2013年01月18日のツイート

2013年01月17日のツイート