様相論理 is Fun

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

MENU

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

$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$は任意だから, これで主張は証明された.