読者です 読者をやめる 読者になる 読者になる

ブール代数からストーン表現(ストーン双対)まで

ストーン双対 圏論 ブール代数 位相

ブール代数の仕組みについて大まかに説明して、ストーン表現について軽く説明する。まず、束の定義、ブール代数の定義、から始める。

 

[束とは]

束(lattice)とは、半順序(partial order) $(L,\le)$に対して、任意の$x,y \in L$に上限、下限が存在するもののことをいう。半順序は、順序関係に$a,b,c \in L$で次の三つが成り立つもののこと。

  • 反射律 ... $ a \le a $
  • 推移律 ... $a \le b $かつ$ b \le c$ならば、$a \le c$
  • 反対称律 ... $ a \le b $かつ$ b \le a$ならば、$a=b$

たとえば、下記のような下から上に向けての半順序構造があるとする。

レイヤ 1

赤い丸が元で線でつないだ関係が半順序関係であり、$下の丸 \le 上の丸 $である。どちらも半順序構造をなしている図なんだけど、右の図は束になり得るが、左の図は束ではない。左図では、上限(or下限)が複数...2個、見つかる組が存在するためである。

2つの元から先の上限、下限を得る演算を結び(join)、および、交わり(meet)と呼ぶ。結びと交わりは、それぞれ$x \vee y$ , $x \land y $と表記されて、束は元の集合$L$とこれら演算の組 $(L,\vee,\land)$と表記される。束は、joinやmeetのような演算を含む構造のことである。

この定義で言うと、束には必ず半順序構造を含んでいて、$a,b \in L$の順序関係は、束の演算に対して以下が成り立つ。

  • $ a \le b $のとき、$ a \vee b = b  ,  a \land b = a $。 (逆も成り立つ)

一方、束は、次のような代数的な定義もある。それぞれの2項演算$\vee$、$\land$に対して、以下の式を満たすのが束といえる。

  • 可換律 ... $x \vee y = y \vee x   ,   x \land y = y \land x $
  • 結合律 ... $(x \vee y) \vee z = x \vee ( y \vee z )    ,   (x \land y) \land z = x \land ( y \land z ) $
  • 吸収律 ... $(x \vee y) \land x = x    ,    (x \land y) \vee x = x$
  • 冪等律 ... $ x \vee x = x \land x = x$

 

[ブール代数]

 ブール代数(Bool algebra)は、束$(B,\vee,\land)$であって次の条件を満たすもののことである。

  • 分配束である。すなわち、任意の元$a,b,c \in B$に対して、次の分配律が成り立つこと。$ a \vee ( b \land c) = (a \vee b) \land (a \vee c)   ,   a \land ( b \vee c) = (a \land b) \vee (a \land c) $ ... ※この二つの式は同値である。
  • 任意の元$\forall a \in B$で $ a \vee 1 = 1 $ となる"1"、および、$ a \land 0 = 0$となる"0"なる元が存在すること。
  • 任意の元$\forall a \in B$で、$ a \vee \lnot a = 1$かつ、 $ a \land \lnot a = 0$なる演算$\lnot$による元(補元と呼ぶ)が存在すること。つまり$\lnot a \in B$

以上によって、ブール代数は$(B,\vee,\land,\lnot,"0","1")$と表記する。

 

[ブール代数の例]

トリビアルブール代数

ブール代数の例として、もっとも単純なのは、$\textbf{2}=(\{0,1\},\vee,\land,\lnot,0,1)$である。つまり、0と1しかない1ビットの2進演算で、結びと交わりはそれぞれ論理和論理積に対応する。これは"トリビアルブール代数”という。

集合代数

さらに、集合$S$の部分集合族$\mathcal{P}(S)$を元とした、$(\mathcal{P}(S),\vee,\land,\lnot,\emptyset,S)$の集合代数もブール代数となる。この場合、結び(meet)が和集合、交わり(join)が積集合に対応する。たとえば、集合$S=\{0,1,2,3\}$の4つだったとすると、半順序構造の図として書くと、以下のようになる。

Layer 1 φ {0} {1} {2} {3} {0,1} {0,2} {0,3} {1,2} {1,3} {2,3} {0,1,2} {0,1,3} {0,2,3} {1,2,3} S

これは集合のそれぞれの元を"含む"or"含まない"を"1"or"0"で対応させた4ビットの演算と同型になる。(4つのトリビアルブール代数の積ともいえる)ここでは詳しく説明しないが、無限集合でも同じブール代数になる。

(ストーン表現はこれを位相空間に拡大して示したものなのだけど、詳細は後で...)

 

自由ブール代数

ある文に対して"真"か"偽"を判断できるものを命題とする。他に影響を与えない独立な命題(独立命題)$P$と$Q$があった場合、この二つから"$P$ または $Q$"とか、"$P$ かつ $Q$"、"$P$ではない"として、別の命題を作ることができる。さらに、作成された命題から"または"や"かつ"で命題を作っていく。"または"や"かつ"をブール代数の$\vee$、$\land$とみなし、"ではない"というのを$\lnot$と考えれば、ここで生成された命題群はブール代数となる。これを、「P,Qで生成された自由ブール代数(free boolean algebra)」と呼ぶ。生成する独立命題集合を$X(:例ではX=\{P,Q\})$としたとき、このブール代数を$\textrm{F}(X)$と表す。

例として、上記の場合の順序集合の図を以下に示す。

Layer 1 FALSE PandQ Pand(notQ) (notP)andQ (notP)and(notQ) P Q PiffQ Piff(notQ) (notQ) (notP) PorQ Q→P P→Q (notP)or(notQ) TRUE

生成される独立命題が有限のN個の場合、$2^{2^n}$個の元のブール代数となる。これの詳細は、英語のwikipediaに詳しい。

Free Boolean algebra - Wikipedia, the free encyclopedia

 "自由"という概念自体は、普遍代数にも適用でき、さまざまな場面で検討できるので興味深い。

[ブール環]

ブール環(bool ring)は、環$R=(R,+,・,-,0,1)$で、任意の元$\forall x \in R$に対し、冪等式が満たされるものを言う。

\[ x^2 \simeq x \]

この条件の追加だけで、ブール環は可換環であり、さらに次も成り立つ。(加群に対しての逆元が自分自身に等しい)

\[ x + x = 0 \]

さらに、ブール代数とブール環は演算の変換をすることで、同型になる。

  • $a・b=a \land b   ,   \lnot a = - a  $ ... ブール代数←→ブール環
  • $a+b = (a \land \lnot b) \vee ( \lnot a \land b)$ ... ブール代数→ブール環
  • $a \vee b = a+b + a・b $ ... ブール環→ブール代数

 

[ブール代数準同型]

ブール代数$B=(B,\vee_B,\land_B,\lnot_B,0_B,1_B)$と$B'=(B',\vee_{B'},\land_{B'},\lnot_{B'},0_{B'},1_{B'})$があったとして、$B$の元から$B'$の元への関数$f:B \to B'$が、次のように演算結果を保存するとき、$f$を準同型(homomorphism)と呼ぶ。$a,b \in B$として、

  • $f(a \vee_B b) = f(a) \vee_{B'} f(b)$
  • $f(a \land_B b) = f(a) \land_{B'} f(b)$
  • $f( \lnot_B a) = \lnot_{B'} f(a)$

 ブール代数は束であり、半順序構造なので、当然、束や半順序の準同型でもある。さらに、同型のブール環に対しても演算が保存されるので、環についての準同型とも言える。さらにさらに、後で述べるストーン表現は、ブール代数と(ある条件の)位相空間との同型を示している。

 

[ブール代数イデアルとフィルター]

環論や順序の理論でイデアル(ideal)はよく出てくる。ブール代数においては、イデアルとフィルター(filter)が双対的な関係なのでまとめて定義を見る。

ブール代数$(B,\vee,\land,\lnot,0,1)$において、イデアル:$I \subseteq B$ 、フィルター:$F \subseteq B$は、Bの部分集合で、次の3つの条件を満たすものである。

[イデアル$I$の条件]
  • $0 \in I $
  • $a \in I , b \in B $ならば、$a \land b \in I$  (つまり、$a' \le a$なら、$a' \in I$ )
  • $a , b \in I $ならば、$ a \vee b \in I$
[フィルター$F$の条件]
  • $1 \in F$
  • $a \in F , b \in B $ならば、$a \vee b \in I$  (つまり、$a \le a'$なら、$a' \in F$ )
  • $a , b \in F $ならば、$ a \land b \in F$

あるイデアルに対して、それぞれの元の補元を集めるとフィルターになる。逆も同じなので、いわばコインの裏表の関係である。

たとえば、さっきの4つの元の集合代数によるブール代数であれば、"$\{2,3\}$の部分集合すべて"はイデアルに、"$1$を含む$B$の部分集合すべて"はフィルターとなる。

[principal or free]

イデアル:$I$ / フィルター:$F$ の要素すべてに対し 結び/交わり をとることができる。この値が "1"/"0" の場合、フリーイデアル(free ideal) /フリーフィルター(free filter)または、non-principal ideal / non-principal filterと呼ぶ。

  • イデアルの場合 ... \[ \bigvee_{i \in I} i  = 1 \]
  • フィルターの場合... \[ \bigwedge_{f \in F} f  = 0  \]

"1"/"0" ではない場合、principal ideal / principal filter、主イデアル / 主フィルターと呼ぶ。前述した例で言うと、"$\{2,3\}$の部分集合すべて"、"$1$を含む$B$の部分集合すべて"いずれも、主イデアル、主フィルターで、要素すべての結び / 交わりの値は、定義から"$\{2,3\}$"、"$\{1\}$"となる。

[フリーイデアル(フィルター)の例]

自然数の集合$\mathbb{N}$の集合代数$\mathcal{P}(\mathbb{N})$を考える。このブール代数の元のうち、有限個の集合であるものを$I_{fin}$とする。

\[  I_{fin} = \{a|a \in \mathcal{P}(\mathbb{N}) , a   \textrm{is finite} \} \]

これは、フリーイデアルになる。このコインの裏側、つまり、各要素の補集合の集合を考えると、これもフリーフィルターとなり、フレチェフィルター(Frechet filter):$\mathcal{F}_f$と呼ばれる。

\[   \mathcal{F}_f = \{a|a \in \mathcal{P}(N) , \lnot a   \textrm{is finite} \} \]

有限集合のブール代数イデアルは、基本的に主イデアルである。無限集合の場合に、フリーイデアル(フリーフィルター)が現れる。

 

[準同型イデアルとフィルター]

イデアル準同型と非常に重要な係わり合いをする。

ブール代数$B$,$B'$において、準同型$f:B \to B'$が有るとする。このとき、

  • $f$のカーネル(kernel):$\textrm{ker}(f)$ (f(x)=0を満たすx)は、B代数上のイデアルである。逆に、B代数上のイデアルであれば、それをカーネルとした準同型が存在する。
  • $f$のコカーネル(cokernel):$\textrm{coker}(f)$ (f(x)=1を満たすx)は、B代数上のフィルターである。逆に、B代数上のフィルターであれば、それをコカーネルとした準同型が存在する。

これにより、イデアルやフィルターは、対象のブール代数に対して"割る"ことができる。たとえば、イデアル$I$に対して

\[   f:B \to B/I ... fは、  \textrm{ker}(f)=I  なる準同型    \]

となる 剰余代数(商代数)$B/I$のブール代数をつくることができる。(フィルターも同様)

たとえば、自然数の集合$\mathbb{N}$の集合代数$\mathcal{P}(\mathbb{N})$を$I_{fin}$で割って、$\mathcal{P}(\mathbb{N})/I_{fin}$というブール代数を考えることができる。これは、有限集合(finite)はすべて"0"に、補有限集合(cofinite)(補集合が有限な集合)はすべて"1"にマッピングされ、補集合をとっても無限な無限集合(例えば:2の倍数)に対して、それぞれのブール代数の要素が位置づけられる、かなりイメージしにくいブール代数となる。

 

[極大イデアルと極大フィルター]

 極大イデアル、または、極大フィルターを次のように定義する。

ブール代数$B$のイデアル:$I$  , フィルター:$F$ で、その剰余代数$B/I$  ,  $B/F$が、"トリビアルブール代数”であるとき、極大イデアル(maximal ideal)  ,  極大フィルター(ultrafilter)という。

\[ B/I_{max}  \simeq  \textbf{2}    ,    B/F_{max}  \simeq  \textbf{2}   \]

 この定義から、$B$のどの元$\forall a \in B$も、$a$または、$\lnot a$のどちらか一方が$I_{max}$,$F_{max}$に含まれることになる。(両方とも含まれることはない)(これは逆も成り立つ)

 

さらに、あるイデアルやフィルタが存在すれば、それを含んで上記を満たす極大イデアル , 極大フィルターを見つけることができることが、選択公理を用いて、示されている。

 

たとえば、前出の"$\{2,3\}$の部分集合すべて"というイデアルは、

  • "$\{0,2,3\}$の部分集合すべて"
  • "$\{1,2,3\}$の部分集合すべて"

の二つが、それを含む極大イデアルとなる。"$1$を含む$B$の部分集合すべて"は、これ自体が極大フィルターである。

フリーイデアルはどうか?前出の$I_{fin}$は、極大イデアルではない。自然数の集合$N$の部分集合で、例えば"2の倍数の自然数すべての集合"というのは、無限集合であり、補集合も無限集合であるため、「どちらか一方がイデアルに含まれ」ていないため、極大イデアルではない。フレチェフィルターも同様である。それを含む極大イデアル/極大フィルターは存在することは(選択公理を用いて)証明できるのだが、具体的に構成することできない(非常に難しい)。このあたり、"選択公理"と関連し、"具体的に構成できない"点がバナッハ・タルスキーパラドクスを思い出す。

 

[ストーン表現とは]

さて、やっとここまできて、ストーン表現が説明できる。

 位相空間で、

  1. コンパクトで、
  2. ハウスドルフで、
  3. 完全非連結 (あるいは開かつ閉集合を基底にもつ ... これは同値)な、

なものをブール空間という。ブール空間$S$から、開かつ閉集合族を得る関数を$\textrm{B}(S)$と書くことにする。

ブール代数$B$から、その極大フィルターの集合を得る関数を$\textrm{S}(B)$と書くことにする。

すると、ある任意のブール代数$B$の極大フィルターの集合$\textrm{S}(B)$は、ブール空間となる。また、任意のブール空間$S$の開かつ閉集合族$\textrm{B}(S)$は、ブール代数となる。それぞれ対応するブール代数、ブール空間が存在して、

\[ f:B \to \textrm{B}(\textrm{S}(B))        f(a)=\{ U \in \textrm{S}(B):a \in U \} \]

 というマッピングが可能である。これがストーン表現である。$S$からも同様に一対一の対応関数が可能となる。

[例]

有限集合(finite boolean algebra)の集合代数に対応するブール代数については、直感的にも理解できる。有限集合は離散位相なので、集合$X$に対して、$B \simeq \mathcal{P}(X)$、$X \simeq \textrm{S}(B)$となる。有限集合代数の超フィルターはすべて主フィルターで、集合の要素ごとに定められることを考えると想像がつく。

ところが、無限集合の集合代数や、無限個の変数を持つ自由ブール代数については、ややこしい。

自然数$\mathbb{N}$の集合代数(infinite boolean algebra)は、非可算で連続体濃度の$\mathcal{P}(\mathbb{N})$となる。これの超フィルターは、自然数の主フィルターだけでなく、フリーな超フィルターも含んでいる。

可算無限個の変数$X$を持つ自由ブール代数$\textrm{F}(X)$については、対応するブール空間は、カントール集合$K$となる。(有限個の変数の場合の自由ブール代数の超フィルターがどうなっているかを確認すればよい。)しかし、principalな超フィルターは存在しないで、すべてフリーな超フィルターとなる。

以上を簡単に表でまとめると、以下のようになる。

 

ブール代数 $B$ ブール空間 超フィルター $S(B)$  そのほか

有限集合$X$の集合代数$B \simeq \mathcal{P}(X)$

有限集合$X$の通常の位相

  • 有限集合$X$の要素に対応する主な超フィルター
 

可算無限集合$\mathbb{N}$の集合代数$B \simeq \mathcal{P}(\mathbb{N})$

たとえば$ [ 0,\frac{1}{n} ]$?

  • $\mathbb{N}$の元に対応する主な超フィルター
  • フレチェフィルターを含むフリーな超フィルター
  • 連続体濃度
  • $\mathcal{P}(\mathbb{N})/I_{fin}$では主な超フィルターがなくなる

可算無限集合$X$を変数にもつ自由ブール代数$B \simeq \textrm{F}(X)$

カントール集合$K$

  • すべてフリーな超フィルター
  • 可算濃度!!!(有限個の変数の場合は$2^{2^{|n|}}$であるにもかかわらず!!)
  • 可算なブール代数は集合代数とは必ずしも一致しないが、$\textrm{F}(X)$の商代数と一致する。(論理式を評価する形で対応づけられる)

[ゲーデル不完全性定理の代数化]

ところで、wikipediaゲーデルの不完全性定理 - Wikipediaという記事の中に"不完全性定理の代数化”という章があって、

( Q ) を含む再帰的可算(RE)素イデアル p ⊂ B は存在しない。

とある。これとの対応を、ざっくりと考えてみると、

するのではないかと、素人考えで勘ぐっているが、正しいのかは定かでない。

 

[参考]