まあいっか
まあ(台風)一過です。
台風で今週の勉強会軒並み中止になっているので書くことありませんが、ちょっといま勉強中の本職のことについて。
次の定理の証明を読みました：
ZFCで非可算個の可測基数が存在すると仮定する。このとき、
において、選択公理の否定が成り立つ。
まあ、不思議な話です。
選択公理が成り立たないモデルの構成に関しては、別に巨大基数を仮定しなくても作れて、実際に、ある強制拡大したモデルで内部モデルをとればよい、という話があります。
先ほどの定理は、そういう強制拡大の操作を取り除いた上でカノニカルなモデルで"not AC"が成り立つというものです(但し、巨大基数公理を仮定)。
（なんで巨大基数公理を仮定すると取り除けるか、みたいな話は、何でしょう、後々Woodin基数を使った強制絶対性が成り立つからみたいなこともあるんでしょうか…？
今回のケースでは巨大基数の仮定はWoodin基数を使わない十分弱いものですが。）
これに続く話として、Woodin基数がたくさんある仮定すると、とか特に
で任意の実数の部分集合がルベーグ可測になったり、完全集合の性質をもったり、ベール集合になったりするわけです。
（そのようなモデルで選択公理が成立していないのは明らかで、選択公理を成り立つと思うと有名なVitaliの非可測集合の構成法が適用できる。）
証明の中身についてはここで述べることはできませんし、何よりちゃんとフォローしていないのでだめだめなのですが、感じとしては、可測基数から誘導される初等埋め込みを考えて、ある順序数について
に可算順序数列をパラメーターとして定義可能な整列順序がのらないことを示すというもので、ポイントとしては、十分多くの順序数とパラメーターを動かさないような初等埋め込みがうまいこと取れて、一方、
の元をそれが埋め込みの臨界点を含むようにすると、その元と写った先の元で順序型が同じになってしまって矛盾しますねというものです（うっ全然説明になっていないなあ…）（テクニカルな詳細議論完全無視（このへんがだめだめ））。
もちろん、そこでは実数の集合がどうのという話は出てこないという点では、なんだか不思議だけどそうですね、みたいなことになる。
まあここら辺の話は記述集合論とか内部モデル論とかジェネリック埋め込みの話とかがオーバーラップしてくるところで、かなり難しいわけです。
大丈夫かなあ、とは思いつつ、少なくともジェネリック埋め込みの構成とかはフォローしたいなぁとか考えながらテキストを読みすすめているわけで…。
いや、こう随分偉そうですね、すみません、挫折しない程度に這いつくばって頑張ります。
うー！にゃーーー！！！
台風「なごやこわ、近寄らんとこ」
ということになってほしい。
お
でもまあ考えてみれば、がsupercompactなら
とかのサイズは(
が正則基数なら)丁度
になるわけで、べつにココらへんの計算にGCHはいらない。
(Solovayの結果を参照しなさい。あるいは、スパコンのもつ強いstatoinary reflectionによる影響を考えなさい。)
てことを考えると、やはりgroundでのGCHってこの場合どの程度本質的なのかわからんなー、とかまあ多分は最低必要なのはわかるが。
あ、Silverの可測基数でGCHが破れているモデルの作り方の話であ。。。
ここらへんのconsistency strengthの話はまあ気になるところではあるな。
なんでかというと、可測基数でGCHが壊れてると、Prikry強制を使って、基数を壊さずに目的の可測基数を可算共終にできるので、特に、SCHが壊れているモデルが作れる。
SCHって奇妙なんですよねぇ。
なんというか、V=L combinatricsとlarge cardinal combinatricsと共存しているという点で。ここらへんの謎を解いてみたいなあ、と思いつつも例あって知識も能力もないという、ぐぬぬ。
特異基数組合せ論というと、やはり最近はpcf理論が強力で、個人的に気になっているのが、Shelahのrevised GCHのはなし。
これについては、HandbookのAbrahamの記事にも解説が載っているけど、底辺理解力でうーんという。
ここ重要だと思うんですよね、こういう特異基数aboveで起こる現象！
supercompact基数(strongly compactでもいいけど)でもそうであった、上へのreflectionという一見矛盾したlarge cardinal propertyが、それを弱めると、特異基数上で実現しているという不思議！
誰か研究してくださいな。
ふえぇわからないよ
なんかTLでHaskellでフィボナッチ数列の40項の単純再帰の計算が40秒かかる、とかなんとか話題になっていたので、最近の式の評価戦略のこともあるのでなんか書く。
えーと、普通にフィボナッチ数列のn項"fib n"を求める式を書こうとすると、以下のようになると思います。
fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
これを普通に計算すると、確かに時間がかかる。
これは、計算された式の再利用をしないからで、再帰段階のfib (n-1)とかfib (n-2)を別個に計算するから、その度に同じfibが多重に呼び出しされて計算量が膨大になるからといえる。
丁度SICPの1.2.2節にfibの計算の木が載っているので、これを見ればいかに計算量が増えていくかがよく想像できると思う。
じゃあ、どうするか、という話だが。
SICP1.2節には、recursive processとiterative processの2つの計算の戦略を挙げている。前者は、いまやったような式で定義される再帰で、fibのようなのもだと木状の計算構造になる。
一方で、フィボナッチ数列を2変数(x, y)から(y, x+y)への変換のくり返し(iteration)とで生成する列と考える事ができる。
このアルゴリズムはHaskellだと次のように実装することができる：
fibgen :: [Int] -> [Int] fibgen xs = (xs !! 0) + (xs !! 1) : xs iterate :: Int -> (a -> a) -> (a -> a) iterate 0 f = \x -> x iterate n f = f . iterate (n-1) f fib' :: Int -> Int fib' n = head $ (iterate (n-1) fibgen) [1,0]
説明すると、fibgenで数列を膨らませる1ステップを表現して、それをiterateで何度も繰り返して、fib'でそのhead(途中まで作ったフィボナッチ数列の末尾項)を取る。
こうすると、ちゃんとfast(processが線形なので)に計算してくれてめでたしめでたし♪
でも実際haskellには正格な評価という概念があるし、正格版の再帰的定義が出来るようになっているし、わざわざこんなことしなくてもいいんですけどねえ。
(すいません、Haskellのことはあまり知らないのです＞＜)
まあ、SICPの話も出ましたし、おぼえがきということで。
ニャンニャン
なんだか
勉強不足てのはつらいものです。
ああああ、ちょっと昔の記事直しましたはい。
SICPですが1回1subsectionのペースで読み進めることにしました。
ということで、Section1.1をよみました。
内容は基本的なLisp表現についてです。
割と気になった点として、1.1.3-4のdefineとかについてです。
defineとはなんぞやと。
本文中ではspecial formの一つとか言ってますけど、単なる名前の付け替えの手続きとしか見なしていないのか（まあprocedureって言ってますし）、まあいまのところわかりません。
なんといいますか、高階関数とか弄りたいなーとか思うけど、どうやるんですか、とかモニョモニョする感じです。（後でλちゃん使うんですね、わかります。）
あとは評価戦略の話でしょうか。
本文中のExercise1.5にもなっていますが、Lispはnormal-order評価でなくapplicative評価を採用しているため、イレギュラーな計算に対応しない場合があると。
演習の例を引用します：
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1))))) (define (test x y) (if (= x 0) 0 y)) (test 0 (fact 999999))
とかをgoshに食わせます。factは階乗関数です。
すると、止まってくれません。
test関数自体は非常に簡単なもので、(test 0 x)の形は、数学的にはxが何であろうと問答無用で0を返すものになっているのに、です。
これは、applicative評価だと、最終式を評価する際、test関数のargumentのfactから先に計算しようとするからです。
因みに、C言語で同じ計算をすると、ちゃんと0を返してくれましたー。(∩´∀｀)∩ﾜｰｲ
とまあこんな感じでしょうか
もうちょっと頑張ります。。。
うにゃ
