様相論理 is Fun

様相論理の学習ノートです

MENU

もっと頑張る

ちょっと弱ってる。

 

Correspondence Theoryを読もうと思って、読み始めて、”T+4+Mckinseyがvalid → 反射的+推移的+原始的”をチェックしようと思って、対偶?と思ったりしたけれども、結局、時間はともかく、精神的余裕がなくなって、呆けてしまって放置してる。初歩的なことが、今はできない。

 

数学は、老後の楽しみにとっておこうかな。

 

日々すべきことと反省がいっぱいで、キャパを超えてる感がある。当面、数学に気持ちが向くことはないような気がする。そんなんでいいのかなとも思うけれども、もっと頑張らなあかんことが、先にあるやろ、と思うので、とりあえず目の前のことを頑張る。

 

せめて、人に迷惑をかけないように。

 

そして、責任はきちんと果したい。

 

気力が戻ったら、今までの数倍頑張って、キャパがどうだとか言い訳しない。

 

戻ってほしいなぁ。

ちょっとした事実のちょっとした証明

$B$をBoolean Algebraとする. $P$を次の条件を満たすような空でない$B$の部分集合とする.

  1. $x\in P$かつ$x\leq y$ならば$y\in P$
  2. $x\cup y\in P$ならば$x\in P$または$y\in P$
  3. $0\not\in P$

(集合演算と同じ記号であるが, \veeを$\cup$で代用する.)

 

このとき, 次が成り立つ.

\[P=\bigcup_{U\subset P}U\]

ただし, $U$はultra filterである.

 

証明: $\subset$を証明すればよい. 任意の$x\in P$をとる. $Q=\{\neg y\mid y\not\in P\}$とする. このとき, $\{x\}\cup Q$がfipをもつことを示す.

 

まず, $Q$が$\cap$に関して閉じていることを示す. $\neg y_1$, $\neg y_2\in Q$ ($y_1, y_2\not\in P$)とする. $y_1\not\in P$, $y_2\not\in P$だから$P$の定義2.より, $y_1\cup y_2\not\in P$. よって, $\neg y_1\cap\neg y_2=\neg(y_1\cup y_2)$より, $\neg y_1\cap\neg y_2\in Q$. 

 

$Q$が$\cap$に関して閉じていることから, $\{x\}\cup Q$がfipをもつことを示すためには, (i) $x\neq0$, (ii) $\neg y\in Q$($y\not\in P$)に対して$\neg y\neq0$ (iii) $\neg y\in Q$($y\not\in P$)に対して$x\cap\neg y\neq0$を示せばよい.

 

(i)の場合: $P$の性質3.より, 主張は自明である.

 

(ii)の場合: $\neg y=0$ならば, $y\cup\neg y=1\in P$ ($P$の性質1.より$1\in P$)だから, $P$の性質2.より$y\in P$. これは, $y$の取り方に反する.

 

(iii)の場合: $x\cap\neg y=0$とする. $\neg(x\rightarrow y)=x\cap\neg y=0$より, $x\rightarrow y=1$. このとき, $x\leq y$であるから, $y\in P$. これは$y$の取り方に反する.

 

以上より, $\{x\}\cup Q$はfipをもつので, これはあるultra filter $U$に延長される.

 

$y\not\in P$とすると, $\neg y\in Q\subset U$であり, $U$はultra filterであるから, $y\not\in U$. よって, 対偶より, $U\subset P$.

 

$x$は任意だから, これで主張は証明された.

春を待つ

正しい方向性はcompletion。熟慮がない。反省。それにBoolはBoole。

 

訂正しなきゃ、と思っているが、季節柄か気力が湧いてこない。

 

読むべき本は、文字通り目の前にあって、計画は脳裏にあるが、いつになったらちゃんと読むことができるかわからない。

 

気分が晴れたら、心機一転して初歩からやり直そう。

 

とりあえず春を待つ。

principalization

"atomic"は, 任意の$x$に対して, $y\leq x$を満たすatom $y$が存在することを指し, これは任意のultra filterがprincipalであることの必要条件なので, 前回の

 umemura-wataru.hatenablog.com

 における言い回しを訂正する.

 

$B$を任意のBool代数とする. $S(B)$を$B$のすべてのultra filterからなる集合とし, $u:B\to\mathcal{P}(S(B))$をStone表現写像とする.

 

$\mathcal{P}(S(B))$において, $u(B)$とnon-principal ultra filterからなるすべてのsingletonで生成される部分代数を$B^\prime$とする. このとき, 次が成り立つ.

 

  1. 埋め込み$B\to B^\prime$が存在する.
  2. $B^\prime$における任意のultra filterはprincipalである.
  3. $F\to u^{-1}(F)$はultra filter間の全単射である.

atomicisation

$\mathbb{N}$の有限集合全体と余有限集合(補集合が有限)全体からなるBool代数を考える.

 

$B$の ultra filter は, 1元集合で生成される principal filter であるか, または, non-principal である, 余有限集合全体である.

 

次のようなBool代数$B^\prime$を構成しよう.

  1. 埋め込み$i:B\to B^\prime$が存在する.
  2. $B^\prime$は atomic である, つまり, $B^\prime$の ultra filter はすべてprincipal である.
  3. ultra filter の対応$i^{-1}:u\to i^{-1}(u)$は全単射である.

 

$\infty\not\in\mathbb{N}$を用意し, $\mathbb{N}\cup\{\infty\}$の有限部分集合全体および, $\infty$を含む余有限部分集合全体からなるBool代数を$B^\prime$とすればよい.

修正

その1

\[

M^{-}(F)=\bigcup_{FRU}U

\]

はultra filter $F$に対して成り立つ.

 

その2

 

前回記事の主張は一般にはおそらく真でない. 有限の場合に自明に成り立つことが勘違いの原因だと思う. 反例を構成する予定.

BA+Ultrafilter RelationからBAO

出発点:

\[ L^{-}(F)=\bigcup_{FRU}U \]

\[M^{-}(F)=\bigcap_{FRU}U\] 

 空になる場合についてコメントが必要. ($Lp\rightarrow Mp$が恒真であるかのように勘違いする恐れがある)

 

対応$F\mapsto L^{-}(F)$についてであるが, $L^{-}$は$\cap$に関して分配的なので, ultrafilterの対応(R!)によって定まることが観察される. このことからの想像.

 

Bool代数$B$のultra filter達の間に, 関係$R$を定める. $B$をStone写像すると, Complex Algebraが定まる.

 

表題の主張は, $B$から自然に定まるBAOで, これをJ\'onsson-Tarski写像すると, 先のものと可換になるものが存在するということ.

Existence Lemma について(その2)

粗雑に述べる. 結局のところ, J\'onsson-Tarski Theorem である. また, 位相的含意がありそうだが, 勉強不足なので, よく勉強して, 後の機会に改めて書く.

 

記法は

A New Introduction to Modal Logic

A New Introduction to Modal Logic

 

にならう. 

 

$B$をBAOとする. Basic Modal Languageで考える. 演算子は, $L$, $M$と表記する. $B$の ultra filter 全体における関係$R$を, filter 全体に拡張しておく.

 

$R$の定義は, $F_1RF_2$ $\Leftrightarrow$ $Lp\in F_1$ならば

 $p\in F_2$.

 

また, $B$の filter $F$に対して, $L^{-1}(F)=\{p\mid Lp\in F\}$と定義する. $L^{-}(F)$も$B$における filter である.

 

以上の下で, BAO での Existence Lemma は, 次のように表現できる.

 

\[

L^{-}(F)=\bigcap_{FRU}U

\]

($U$は$FRU$であるような ultra filter 全体を動く)

 

$\subset$は定義により成り立つ. 実質的に, $\supset$が Existence Lemma. 

Existence Lemma について(その1)

正月に見た初夢. Existence Lemma は以下の BAO analog.

 

ブール代数において, proper filter はこれを含む ultra filter 達の共通部分である。

 

証明: $F$を proper filter とする. $\bigcap_{F\subset U}U\subset F$ ($U$は$F$を含むultra filter 全体を動く)を対偶により証明する.

 

$x\not in F$とする. このとき, $F\cup\{\neg x\}$は fip をもつ. さもなくば, いくつかの$F$の元$f_1$, $\ldots$, $f_n$に対して, $f_1\cap f_2\cap\cdots\cap f_n\cap\neg x$ (mathjaxで\wedge の出力の仕方がわからないので$\cap$で代用)となる. このとき, $f_1\cap f_2\caq\cdots\cap f_n\leq x$より$x\in F$となるが, これは仮定に反する.

 

$F\cup\{\neg x\}$が fip をもつことから, $F\cup\{\neg x\}$はある ultra filter $U_0$に延長される. $U_0$は ultra filter であるから, $\neg x\in U_0$より$x\not\in U_0$. したがって$x\not\in\bigcap_{F\subset U}U$.

基本のK

目的はモデルを作ること。最初の一歩。

 

証明は初歩的。練習問題にありそう。

 

Kから公理Kを除き(Nは変えない), 推論規則$\vdash\alpha\rightarrow\beta$ならば$\vdash M\alpha\rightarrow M\beta$ (DR3), および公理$M(\alpha\cup\beta)\rightarrow M\alpha\cup M\beta$ (prime condition)を追加した体系はKと同一である(同じ定理が帰結される)。

理想論

M$, $\mathrm{OB}$をそれぞれ「~は可能である」, 「~はされるべきである」を意味する様相作用素とする.

 

「$p$は望ましい」は「$Mp\rightarrow\mathrm{OB}p$」と表現される.

 

理想論は「(Mp\rightarrow\mathrm{OB}p)\rightarrow\mathrm{OB}p」が公理である体系.

BAOについて

$B$をBAOとする.

 

$\{p\mid\Diamond p=\perp\}$は$B$におけるイデアルである.

 

$\mathfrak{A}$を$B$におけるイデアルとし, $B$における同値関係$\sim_{\mathfrak{A}}$を次によって定義する.

\[

p\sim_{\mathfrak{A}}q\ \text{iff}\ (p\cap\neg q)\cup(\neg p\cap q)\in\mathfrak{A}

\]

$B/\sim_{\mathfrak{A}}$を$B/\mathfrak{A}$と記す. このとき, $B/\mathfrak{A}$には自然にBAOの構造が入り, $B/\mathfrak{A}$において, $\Diamond p=\perp$ iff $p=\perp$が成り立つ.

 

商代数$B/\mathfrak{A}$を

 

Complex Algebraで遊ぶ

$\mathfrak{F}=(W, R)$をフレームとし, $\mathfrak{F}$のComplex Algebraを$\mathfrak{F}^+$とする.

 

$\mathfrak{F}^+$の極大フィルター$U$に対して, $V=\{X\mid m_R(X)\in U\}$は, 素なupward closed setである(つまり, $X\cup Y\in V$ならば$X\in V$または$Y\in V$であり, $X\in V$, $X\subset Y$ならば$Y\subset V$が成り立つ). このことを, BAOの極大フィルターから,様相演算を忘れたブール代数におけるupward closed setが定まる, と解釈したときに, その逆方向は成り立つだろうか.

 

容易に確かめられる, 次の事実はヒントになるだろうか.

 $\mathfrak{F}=(W, R)$が, 任意の$y$, $z\in W$に対して, $xRy$かつ$xRz$を満たすような$x\in W$が存在するようなフレームであるならば, $\{m_R(X)\mid X\in V\}$ ($m_R(V)$と記す)はfipをもつので, $m_R(V)$を含む極大フィルターが存在する.

 

以上は単に恥を書き捨てただけかもしれないので, 最後に, 様相論理の勉強にとって, 有益なことを書く.

 

 

 

$\mathfrak{F}$や$\mathfrak{M}$の書き方は, 

https://rms2005.org/subtext/pdf/0002_AiM5/ms0002.pdfを見るといいよん.

きれいな字を書くための練習方法

小学校の頃に習字をきちんとやらなかったので(すべての漢字を一画で書く無駄な努力をしていた記憶がある)、大人になってから下手な字の矯正のために漢字ドリルを始めた。

 

五年以上継続しているが、いっこうに上達しない。

 

反省してみて、その理由をふと思いついた。

 

普段、字を書くとき、思考の速度に合わせて字を書いている。ところが、練習のときは、きれいな字を書こうと思って、ゆっくり字を書く。つまり、練習が本番の状況を反映していない。書く速度、あるいは加速度によって、力加減($F=ma$!)が違う。

 

結局、「練習は本番のように、本番は練習のように」ということだろう。

KL=KL4の証明

 

Modal Logic (Cambridge Tracts in Theoretical Computer Science)

Modal Logic (Cambridge Tracts in Theoretical Computer Science)

 
http://blog.hatena.ne.jp/umemura_wataru/umemura-wataru.hatenablog.com/edit?entry=10257846132614526333#preview

のp.37の練習問題。

 

KLはKに公理L:$\Box(\Box p\rightarrow p)\to\Box p$を追加した体系.

 

KL=KL4, つまりKLで4:$\Box p\rightarrow\Box\Box p$が成り立つことを示す.

 

Lより

\[\vdash\Box\{\Box(p\cap\Box p)\rightarrow(p\cap\Box p)\}\rightarrow\Box(p\cap\Box p)\tag{1}\]

Kより

\[ \vdash\Box(p\cap\Box p)\rightarrow(\Box p\rightarrow\Box\Box p)\tag{2} \] (1), (2)より

\[ \vdash\Box\{\Box(p\cap\Box p)\rightarrow(p\cap\Box p)\}\rightarrow(\Box p\rightarrow\Box\Box p)\taf{3}\]

命題論理より

\[\vdash p\rightarrow\{\Box(p\cap\Box p)\rightarrow p\}\]

GeneralizationとKとMPより

\[\vdash\Box p\rightarrow\Box\{\Box(p\cap\Box p)\rightarrow p\}\tag{4}\]

命題論理より

\[\vdash(p\cap\Box p)\rightarrow p\]

generalizationとKとMPより

\[\vdash\Box(p\cap\Box p)\rightarrow\Box p\]

generalizationより

\[\vdash\Box\{\Box(p\cap\Box p)\rightarrow\Box p\}\]

 これと命題論理より

\[\vdash\Box p\rightarrow\Box\{\Box(p\cap\Box p)\rightarrow\Box p\}\tag{5}\]

 (4), (5)と命題論理より

\[ \vdash\Box p\rightarrow[\Box\{\Box(p\cap\Box p)\rightarrow p\}\cap\Box\{(p\cap\Box p)\rightarrow\Box p\}]\]

一般に, Kにおいて$\vdash\Box p\cap\Box q\rightarrow\Box(p\wedge q)$であるから

\[\vdash\Box p\rightarrow\Box[\{\Box(p\cap\Box p)\rightarrow p\}\cap\{\Box(p\cap\Box p)\rightarrow\Box p\}]\tag{6}\]

命題論理より \[\vdash[\{\Box(p\cap\Box p)\rightarrow p\}\cap\{\Box(p\cap\Box p)\rightarrow\Box p\}]\rightarrow\{\Box(p\cap\Box p)\rightarrow(p\cap\Box p)\}\tag{7}\]

(7)とgeneralizationとKとMP, および(6)と命題論理より \[ \vdash\Box p\rightarrow\Box\{\Box(p\cap\Box p)\rightarrow(p\cap\Box p)\}\tag{8}\]

(3)と(8)と命題論理より \[ \vdash\Box p\rightarrow(\Box p\rightarrow\Box\Box p) \] 命題論理より \[ \vdash\Box p\rightarrow\Box\Box p \]