@koboldpupil これが weak randomより強くなるかはちょっと微妙かなあと思ってます。零集合と強零集合には大幅な差があって、一般には、零Π^0_1 （Kurtz test） を強零Π^0_2で被覆できないので……。

posted at 01:08:21

@koboldpupil これで何らかの自然なランダムネスが定義できていたら面白いんですが、今の所未解決です。論文に書いてある通り、eff.強零Π^0_1集合に属すならばnon-complexということは分かっています（逆は不明）が、Π^0_2にするとまた様子が変わりそうです。

posted at 01:01:39

強零集合とは：「いかなる正実数列が与えられても、その長さの開区間の和で被覆できる」という実数の集合であり、1919年にボレルによって導入された。「強零ならば可算」というボレル予想は、連続体仮説の下で偽であるが、Laver強制法によって真となるZFCのモデルの存在を示せる。

posted at 19:25:21

CiEに投稿した論文+αはリサーチマップの方にうｐしました。強零集合をランダムネス研究に使えるんじゃないかなーとはしばらく前から漠然と思ってたけど、強零集合を扱うにはLaver強制法とかちゃんと勉強しないとダメかなー面倒だなーと後回しにしていたのを、ようやく手を出したという内容。

posted at 19:18:25

@kagami_hr こんばんわん

posted at 19:15:56

ひさしぶりに復活。ここしばらく、うちの研究室では、7人が修論・1人がD論を書いているところに、CiEの締め切りが重なってCiEに少なくとも6人が投稿しようとしていたというカオスな状況だったけれど、ようやく一段落。

posted at 19:13:14

うぬぬ、なんか気になる論文が ArXiV に上がってたのでメモ： Basic Subtoposes of the Effective Topos http://t.co/lRSjappO

posted at 01:10:27

@patho_logic あんまり役に立つ定理ではありませんが、Slaman-Woodinのダブルジャンプ定義可能性定理とか。 http://t.co/UAi84jAk

posted at 16:03:05

@cosmic_music 言われて見れば、うまい命名ですねー。こういう集合に名前を付けろと言われたら、「格子」とか「網目」みたいな名称をぱっと思いついてしまいそうですが、でも、これは格子や網目なんかじゃなくて、タータンの方が遥かにしっくりきますね。

posted at 01:49:17

@tenapi DM送りました。ちなみに実は以前言ってたショケショケは、別にショケらなくても証明できるんじゃないかという微妙な結論に至ってしまったのですが、最近、実解析や関数の微分可能点（とランダムネスの関連）を調べているので、その道のプロである殿下の意見を伺えればなあと思います

posted at 01:25:58

ところでチューリング生誕100周年記念研究集会CiE2012の投稿締め切りは十日後の1/20なので、注意しましょう。 http://t.co/gs5gqjU0

posted at 00:28:35

カントールのタータンは、我々の分野では、二次元連結選択の問題で現れるのです。というか、二次元連結選択の問題を解決したくて、連続体論（連結コンパクト空間の一般論）とかシェイプ理論とか粗い幾何とか手当たり次第に手を伸ばしていたけど、フラクタル幾何に向かうのが正解なのかもしれない。

posted at 00:22:22

カントール空間を二つ直角にクロスした空間は、フラクタル幾何の方では「カントールのタータン」と呼ばれていることを始めて知った。タータンってなんだよ、と調べたところ、なんかの民族衣装の柄っぽいものらしい。

posted at 00:19:29

Kechris-Louveau "A classification of Baire class 1 functions" の発展系みたいな話題のまとまった本が欲しいー。実解析のBaire classとかBorel可測関数の細かい階層に関するまとまった文献はどこにあるのか……。

posted at 01:12:30

Set Theory for the Working Mathematicianの実解析っぽい反例が書いてある章は好きなんだけど、あれは実数を整列させて超限帰納法というやや反則技なので、もっと構成的に実解析の反例を作る感じの記述集合論まとめ本が欲しいです。

posted at 01:04:17

@kagami_hr あけましておめでとうございます。今年もよろしくお願いいたします。

posted at 01:01:22

まあ、CiEからも「今日からチューリング生誕100周年の年がスタートだよ！」というメールが日本時間では1月2日に送られてきたので、世界的にあけましておめでとうが遅れているということにしよう。というわけで今年はチューリング生誕100周年の年だそうです。

posted at 01:00:27

最近、定期的に失踪するのは、なんか論文書いていると他に文章を書くのが億劫になってtwitterで呟く気力も失う的現象によるもので、それはさておき、遅ればせながらあけましておめでとうございます。

posted at 00:58:24

ALC2011・4日目9 Turetsky『計算可能範疇的構造』 与えられた構造の計算可能範疇性の決定問題はΠ^0_4～Π^1_1であることが知られているが、ここのギャップを埋めるために相対的Δ^0_α-範疇性の概念を導入して、細かい所を調べて行こう！という話。

posted at 19:15:17

他の同時講演のため聴き損ねたメモ：ただき こうたろう『アルゴリズム情報理論の統計力学的解釈の堅牢性』きっと聞く機会は近いうちにあるはず…（たぶん） アントニー・モルフェット『迅速性、ランダム、カップ、キャップ』c.e.次数構造の∪/∩-性とランダムの低性との関連の話だったらしい

posted at 19:06:08

@zhanpon Cooperはロジックの知識の無い初学者向けの教科書という感じなので、人によっては内容が浅すぎると感じるかもしれません。以前書いたオススメリストがあるので、自分に合ってそうなのを選んでみてください～ http://t.co/dsr12F5x

posted at 18:59:36

@zhanpon 単に僕がALC2011の再帰理論の講演を中心に見て回っている（複数の分野の講演が同時に行われている）せいでそう見えるだけで、違う分野の人がALC2011の様子を呟いていたら、また印象が変わるのではないかと！

posted at 18:47:45

（つづき）まず、分解/局所モジュラー/体ライク（Zilberの三者択一）な理論で実現可能なスペクトルには限りがあり、フルショフスキ構成が必要であることを述べ、これを用いて、目的のスペクトルに対応するモデルの列を構成するという、今、計算可能モデル理論で最も熱い（たぶん）トピックの話

posted at 18:45:38

ALC2011・4日目7 ユーリ・アンドリューズ『強極小群の計算可能性』 モデル理論におけるBaldwin-Lachlanの定理は、任意のアレフ1-範疇的な理論に対し、素モデルから飽和モデルへの長さω+1の初等鎖が存在することを主張するけれど、これに対するスペクトル問題がある（続

posted at 18:38:57

ALC2011・4日目6 ジェニファー・レイマン『グラフ上の距離と他の近似函数』 以前会ったときと苗字が変わっている。計算可能連結グラフの距離函数を、エルショフ階層の函数版のようなもので特徴付けられるという話。

posted at 18:33:24

ALC2011四日目4:みやべ けんし 『ルベーグ微分定理によるカーツ・ランダムネスの特徴付け』 最近、ランダムネスと微分可能点との関係が次々に示されているけれど、それを積分テストを介してルベーグ微分定理を用いた統一的な特徴付けを与えようという話。これはすっきりして超面白い。

posted at 18:24:34

というわけでアジア論理学会議まとめ4日目：クリスチャン・カルード "How random is quantum randomness?" マルティン=レフ・ランダムネスと量子的ランダムネスの関連性は気になるけれど、もうちょい物理の知識を身につけないと理解した気になれないなあ。

posted at 18:13:05

@keno1728 えっ、僕そんな発言しましたっけ……と思って過去ログを検索したら一年半前にしてました http://t.co/FlgVXGYG 文脈を見るにただのネタ呟きのつもりだったと思われるので、現在の大学教育に持ち込んでも問題が出る可能性が高いという点は同意です。

posted at 18:03:00

@salmonsnare やあやあ。

posted at 17:39:41

夕飯食べに行ったら半袖短パンで歩いているAndre Niesに遭遇した。ニュージーランドは初夏とはいえかなり寒いのになー…と思ったけど仙台の冬でも半袖短パンで生活していた某サムさん（ベルギー人）を長く見てきたので、まあ、これが平常なのだと思うことにする。ちなみに僕はジャケットです

posted at 17:37:22

ALC2011・3日目8 すずき としお『資源限定ランダムネスと計算可能ダウド型ジェネリックオラクル』 位相的なもの（痩性）ではなく強制定理をベースにしたジェネリック概念があるのだけど、ランダムネスがそのジェネリック性を保証するのに十分な原始再帰的資源が存在することの証明。

posted at 20:02:08

ALC2011・3日目7 ジェームズ・デント『構成的逆数学入門』 ビショップ流構成的数学の上での逆数学。ブラウワーのファン定理と反スペッカー原理の色々な変種を導入して強さの比較をしましょーという話。

posted at 19:58:17

ALC2011・3日目6 さかい ひろし『Chang予想とweak square』 Chang予想が￢□(ω1)を導くことはよく知られているらしい。一方、Chang予想がよわ□(ω1,2)と無矛盾なことが証明できるそうな。

posted at 19:54:09

ALC2011・3日目4 ローラン・ビアンベニュ『フォン・ノイマンの偏ったコイン再訪』 "偏ったコイン"を用いて完全なランダムネスを生み出せるか？与えられた確率測度におけるランダムネスを元にして、マーティン-レフ・ランダムネスを生成する話。学習可能性概念を用いている部分が気になる

posted at 19:48:59

アンドレ・ニース講演は3日目3でした。内容：『王の税法』に従う者としてK-トリビアルであり、不完全なランダムΔ_2騎士の従者は皆貧乏であり、王の税法は慈悲深く、慈悲深き税法に従うものは強ジャンプ追跡可能である。

posted at 19:39:37

ALC2011・2日目9 アンドレ・ニース『Δ_2集合の複雑性をその変心で測る』 アーサー王伝説になぞらえたランダムネス物語。Ω王と円卓のランダムΔ_2騎士。Ω王はともかく、騎士は無限人くらいいそうなので、円卓を準備するのが大変ですね。

posted at 19:38:24

ALC2011・2日目8 ミンゾン・カイ『有限極大鎖性を持つ一般ハイ次数』 極小次数は必ず一般ロー2であることが知られているが、2-極小（極小次数の極小被覆）ではどうなるか？というと実は一般ハイまで持ち上げることが出来るという。何はともあれこの人の使う算術的強制法は面白いよ！

posted at 19:29:53

ALC2011・2日目7 アレクサンダー・メルニコフ『計算可能性と実効群論の交流』 群論における計算可能性の研究の萌芽とも言えるものは実は1910年代からなされていて、結構長い歴史を持つ研究分野だそうな。その流れの中で、ある種の群の非範疇性の次数に関する研究結果など。

posted at 19:20:54

（つづき）ADS（無限全順序から無限上昇列または無限下降列を抽出する）とCAC（無限半順序から無限鎖または無限反鎖を抽出する）自体シンプルで興味深い対象なので、ADS≠CACも解決したい。部分的結果として、ADSとCACのc.e.やco-c.e.版なら、≠を示せたよ、という話

posted at 19:12:14

ALC2011・2日目6 ダミール・ジャファロフ『c.e.半順序』 逆数学におけるいわゆる2-2ラムゼー問題解決のため2007年頃からADSやCACなどの順序構造に関わる逆数学的原理が次々に導入されたが、そもそもADSとCACの違いは謎である（つづく）

posted at 19:08:14

ALC2011・2日目5 セルウィン『超免疫不在次数の計算的側面』実数の計算的強さを測る指標の一つとして、超免疫不在性があるけど、この超免疫不在性の性質（ジャンプ逆転・Π^0_1クラスの基底定理・K-トリビアル性・ランダム性など）について、もっと深く調べてみよう！的な話。

posted at 19:01:22

アブストラクトによれば、位相力学・ラムゼー理論・モデル理論のアイデアを用いて、可算集合の対称群の閉従順部分群に関連するuniversal minimal flow上の G-不変測度に関してマーティン-レフ・ランダムネスによる特徴付けなどなどの話をしていたらしい。

posted at 18:48:35

ALC2011・2日目4 ウィレム・フーシェ『マーティン-レフ・ランダム性、不変測度、計算可能等質構造』 自分の発表と時間が被ってて聴きにいけなかったけど気になるのでメモ。

posted at 18:46:26

ALC2011・2日目4 Libor Behounek『論理IMTL上の素朴集合論』 無限値ウカシェビッチ論理上の素朴集合論のお話。専門外なので細かいことはさっぱり分かりませんが、 @ytb_at_twt さんに関する話をしているということは分かりました。

posted at 18:34:07

たぶん、実効L^1可積分関数は、殆ど至る所で、実効(F_σ,F_σ)-可測だけど、逆は言えない。と思う。

posted at 18:29:01

ALC2011・2日目3 @tri_iro『Π^0_1クラスの難易度のトポロジー的側面』稠密性と次数の関係から始まり、ボレル可測関数の実効階層の話をした所、ジェイソン・ルートから「お前の実効(F_σ,F_σ)-可測関数と、実効L^1可積分関数とはどういう関係がある？」と質問される

posted at 18:28:02

ALC2011・2日目2 ノーム・グリーンバーグ(2)『強ジャンプ追跡可能性』（全体講演）強ジャンプ追跡可能性の歴史から始まり、ランダムネス・K-トリビアルなどとの関連性、ランダムネスによる特徴付け、強ジャンプ追跡可能性の次数構造などのサーヴェイ的な話。

posted at 18:23:29

ALC2011・初日8 ジェイソン・ルート『任意の測度空間における計算可能ランダム性』　計算可能ランダム性の概念を一般の測度空間に拡張。あとendomorphismランダムなる概念を導入。MLランダムあるいはKLランダムと同値になるかどうかは未解決問題（ML=KL?も長い問題）。

posted at 18:17:42

ALC2011・初日7 キャメロン・フリーア『解析学・グラフ理論・確率論におけるランダムネスの諸相』グリーンバーグと同時講演だったので聴きに行けなかったけど、気になったのでメモメモ。詳細な内容は知りません。

posted at 18:09:33

ALC2011・初日7 ノーム・グリーンバーグ『非可算構造の実効的性質』計算可能モデル理論を非可算に拡張したらどうなるか？非可算順序構造（たとえば濃度アレフ1の全順序）の次数的およびモデル理論的性質を認容再帰理論を用いて分析。まだ発展途上だけど先が気になる話題。

posted at 18:05:13

ALC2011・初日6 デヴィッド・ダイアモンドストーン『強ジャンプ追跡可能性の内在的枚挙可能性』強ジャンプ追跡可能実数はあるc.e.強ジャンプ追跡可能実数の下にあるという定理。系として、強ジャンプ追跡可能性とスーパーローであることが一致するとか。

posted at 18:00:55

アジア論理学会議・初日5:Hoelzl 『計算可能関数のDenjoy alternative』任意の実関数は、殆ど至る点で微分可能であるor可能な限り微分不能であるけれど、デムースがその二者択一が成立する点を現在デムース・ランダムと呼ばれる概念で十分条件を与えた話の更なる発展形。

posted at 17:53:51

今回のアジア論理学会議2011は、超ランダムネス推しにつき、ほぼ全ての時間帯にランダムネス講演があるというアジアランダムネス会議の様相を呈してきている感じがしてますが、そのおかげで、結構、解析学・確率論・エルゴード理論っぽい話が聴けて楽しいです。

posted at 17:46:44

アジア論理学会議2011@ニュージーランド http://t.co/KOUlKVDx の三日目が終了して一段落着いたので、ここらでここまでのアジア論理学会議まとめでもつぶやこう。

posted at 17:34:48