細かいところはだんだん書くのが面倒になってきたので気になった部分だけ informal に。わりと技術的なところからくる動機づけがあって、実はそれが counterpart theory という古くから考えられてきた話と関係がありそうだという展開。*1 代入の問題 前節で…

この間読んでよくわからなかったところを再読。 10.2 The need for the continuity axiom geometric morphism が適当な条件を満たすと epi-mono factorization を使って past modality も定義できる。そのように定義された様相 は (continuity) は満たすが、…

このあたりから数学的にハードに感じるようになってきました。基礎体力が足りませんね。しかしここで頑張らなければいつまで経っても成長しないことがこれまでの幾多の経験から実証されているので頑張る。 10.1 Geometric morphisms and modal logic とりあ…

少し時間ができたので "Handbook of Modal Logic" 再開。9.1 は言葉の準備。なんか de Bruijn level っぽい表記を導入している様子。で自由変数が高々 n 個の term/formula を n-term/n-formula と呼ぶ、と。簡単に言ってしまうとそれだけのことのような。 9…

間がちょっと飛んで part 2 の途中、Section 8 から。Section 5 は参考文献リストがメインだし 6 は Part 2 への導入なので飛ばしたのは 7 だけですが。この節は first-order modal logic の Kripke-completeness について……なのですが、どうやら constant d…

連分数展開についてよく知らなかったのですが、最近気になり始めたので河田敬義『数論―古典数論から類体論へ』の最初のほうを読んで勉強中です。第一部は近代的な代数を使う手法ではなくて、もっと古い時代の話。たぶん必要な知識は漸化式と平面ベクトル高校…

この節は hybrid logic を first-order にする話。特別興味があるわけではなかったので軽く流し読みして済ませてしまいました。hybrid logic というのは様相論理に特定の世界でだけ真になる命題変数を付け加えた論理です。この命題変数を nominal と呼びます…

個体の解釈が可能世界ごとに違う意味論。単に object の解釈を世界に依存するように変えるだけかと思ったら、そうではなくて object と intention の二種類の sort を用意してます。 syntax intention variable (i, j, ...) が新たに term として加わります…

なんか Section 15 を読んでみたときのまとめが下書きに残っていたので公開しときましょう。余代数は代数の双対なのだけど、単純に双対をとるだけで対応するわけではない。実際これまでに扱ったような話では、必ずしもすべてが双対で対応付けられているわけ…

"Handbook of Modal Logic" の Chapter 9, First-order Modal Logic 読んでみようかなと思いました。Section 2 からが技術的な話。 意味論の定義 この節では、簡単な axiomatization をもつ三種類の意味論を与えています。 constant domain semantics: indiv…

ようやく論理の話が出てくる節なのですが、何というか、どこに感動すればいいのかよくわかりません。確かに coalgebra を使うことでそれらしい一般化はできているようなのですが、そんなに自然なやり方にも見えないし見通しがよくなった気もあまりしないし。…

24 あたりから最後まで。結局あんまり細かいところまで読み込んでないんですが、とりあえず。 計算量クラスの話。問題を他の問題に帰着するということ。 ハミルトン閉路と巡回セールスマン問題。TSP は NP なので最適解を見つけるのは非常に難しい。 そこで…

代数の variety に対応する、余代数の covariety の話。HSP theorem の余代数版をやります。ちなみに実際に本を読んでいるときは、図式を大量に描きながら計算しています。 homomorphic images 代数と同様に余代数にも準同型像というものが考えられる。定義…

昨日の続き。Ω は set functor で (や、その添え字のついたやつら) は Ω-coalgebra とします。 relation lifting ここからさらに圏論の香りが強くなります。嬉しい。関係 の relation lifting とは、図式 を Ω で写した から定まる の像のこと。これを と書…

代数の congruence に相当する bisimulation と behavioral equivalence について。圏論っぽい雰囲気が漂っていて楽しい節です。ほとんど set functor ですけど。*1以下、特に断らないかぎり Ω は set functor で は Ω-coalgebra とする。添え字や prime が…

終余代数 (final coalgebra) の基本的な話。終余代数とは、余代数の圏の終対象のこと。関手を fix するごとに定義される。理論はだいたい知ってるので例を中心に見ていく。 some examples black box machine . M が機械の内部状態で C が出力。状態遷移を起…

余代数の入門。基本的な定義と例だけです。代数が演算子を計算することで構造を簡単にする仕組みを持っている (e.g. 1+2+3 -> 6)のに対して、余代数は単純なものを分解して構造を作り出す仕組みを持つ対象である、というようなことが書かれています。こんな…

8.1 が tense logic で 8.2 が global modality & discriminator varieties というタイトル。詳細はフォローしないで軽く目を通しただけです。8.1 では、tense logic の future modality と past modality から adjoint が作れて、その結果これらの様相は必…

7.5 Canonical equations "Time to harvest."ようやく目的であった canonical equation の話になりました。でも細かいところはフォローしていない。等式を考えるので term が出てきます。代数を与えるときには term に現れる関数記号と代数の演算は一対一に…

真ん中あたりから読み始めて 23 章まで。Euler path/circuit の話が出てきて、それが存在するための必要十分条件とその証明。この部分は数学的帰納法の解説にページ数を割いてたりするので流し読み。次に、Euler circuit が存在しない場合に、複数回通る辺が…

7.4 Composite maps 今度は関数合成と canonical extension が可換になるかどうかという話。位相的な特徴づけをします。まず使う位相の定義。ブール代数の canonical extension の上で次の位相を考える。 : up-directed joins で閉じた down-set が閉集合 (S…

7.1 Introduction Section 7 は canonical equation の話。等式が canonical であるというのは、それがある BAO で成立するとき、その embedding algebra でも成立すること。論理の方では Kripke completeness に関係する。 7.2 Canonical extensions of Boo…

Section 6 Logics and varieties の続き。 6.3 Interpolation 基礎論サマースクールで聞いたような話。Craig interpolation proporty と superamalgamation property が対応する。superamalgamation から interpolation は Lindenbaum-Tarski algebra を考え…

Section 5 Frames and algebras の続きと Section 6 Logics and varieties の一部。 5.6 Class operations complex algebra をとる関手 と ultrafilter frame をとる関手 の関係について最初に触れられている。 これらの関手はいずれも全射を単射へ、単射を…

Section 5, Frames and Algebras. 途中 5.5 まで。 5.1 Introduction 有限な BAO に対し atom の集合の上にで関係を定義して frame を作ることができる。また、有限な frame が与えられたとき、その冪集合上に BAO の構造が自然に入る (complex algebra)。こ…

Handbook of modal logic の中にある "Algebra and Coalgebra" という章を読んでます。http://staff.science.uva.nl/~yde/papers/ac.pdf に、だいたい同じ内容のものが置いてあります。Section 4 は "Varieties of Expanded Boolean Algebras" というタイト…

一周目終わり。16章以降の内容は全域木、オイラー閉路、マッチング、ハミルトン閉路、巡回セールスマン問題、近似解と下限の評価など。終盤の話は初めて見る内容も多く、詳細はフォローできてないと思います。一周目なので、基本的なものの見方が掴めればい…

ページ数でいうともうすぐ折り返し。ここまでで、最短経路を求める Dijkstra のアルゴリズム、最小全域木を求める Prim, Kruskal のアルゴリズムと、聞き覚えのあるものが三つ出てきました。あとは枝刈りや近似解の話。それからマトロイドの定義が出てきまし…