Section 7 Case study: canonical equations

論理 勉強 メモ

7.1 Introduction

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

7.2 Canonical extensions of Boolean algebras

canonical extension は既に前の節で定義されましたが、その抽象的な定義と、それを満たすものが同型を除いて一意であることの証明など。このあたりは Gehrke さんとかの論文を見ていても似たような議論が出てくるので、押さえとくとよいのかもしれません。

最初に大量の定義。

  • ブール代数の埋め込み B -> C があって C が完備なとき、C を B の completion という
  • completion B -> C は existing meet, join を保存するとき regular であるという

以下 B -> C は completion として、

  • c = \sup \{b \in B | b \leq c \} のとき c は closed であるという
  • closed element 全体の集合を K_C(B) と書く
  • c = \inf \{b \in B | b \geq c \} のとき c は open であるという
  • open element 全体の集合を O_C(B) と書く
  • B is dense in C iff K_C(O_C(B)) = O_C(K_C(B)) = C
    • つまり、C の任意の元は適当に closed elements の join でも open elements の meet でも表せる
  • B is compact in C iff if X \subset K_C(B), Y \subset O_C(B), \inf X \leq \sup Y then \inf X_0 \leq \sup Y_0 for some finite X_0 \subset X, Y_0 \subset Y
  • C is a canonical extension of B iff C is a completion and B is compact and dense

そうすると、任意のブール代数は同型を除いて一意な canonical extension をもつことがいえる。ちなみにブール代数の場合は ultrafilter を使ってできる B -> P(Uf(B)) が canonical extension になる。

証明はそんなに簡単でもないが K_C(B) と B のフィルターのなす束の双対が順序同型、O_C(B) と B のイデアルのなす束が順序同型でなければならないことを使うとできる。

それから canonical extension の性質。B -> C が canonical extension のとき

  • K_C(B) \cap O_C(B) = B
  • K_C(B) は C の sublattice で meet-complete
  • C は atomic で、atom はすべて closed

7.3 Extending maps to the canonical extension

代数の完備化を定義したら、次はそれを関手にしたいと思うのは自然なこと。実は準同型でなくても拡張できるよという内容。

f: A \rightarrow B を考える。

一般に completion の元 x は

x = \bigvee_{x \geq p \in K} \bigwedge_{p \geq a \in B} a = \bigwedge_{x \leq u \in O} \bigvee_{u \geq a \in B} a

と二通りに表示できるので、f の拡張の仕方にも二通り考えられる。

  • f^\sigma (x) = \bigvee_{x \geq p \in K} \bigwedge_{p \leq a \in A} f(a)
  • f^\pi (x) = \bigwedge_{x \leq u \in O} \bigvee_{u \geq a \in A} f(a)

この二つは必ずしも一致しないが、f が単調であればこれらは K∪O 上で一致する。また同じ条件の下で f^\sigma \leq f^\pi が成立する。

これら二つの拡張が一致するような f を smooth であるという。

  • global modality ◇x = (if x = 0 then 0 else 1) は smooth
  • meet, join は smooth で、 extension は拡大した先での meet, join
  • ◇ を global modality とするとき f(x, y) = ◇(A∧B) は smooth ではない

という三つの例があって、それから定理。

  • if f is monotone, then so is its extension
  • if f is an operator, then its extension is a complete operator
  • if f is additive or multiplicative, then f is smooth

証明はわかったようなわからないような……*1

あと最後にもう一つ命題が。BAO のブール代数としての canonical extension をとって、operator をその上へ extend すると ultrafilter extension に同型になる。

*1:「わからない」の別表現