ブール代数からストーン表現(ストーン双対)まで
ブール代数の仕組みについて大まかに説明して、ストーン表現について軽く説明する。まず、束の定義、ブール代数の定義、から始める。
[束とは]
束(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$
たとえば、下記のような下から上に向けての半順序構造があるとする。
赤い丸が元で線でつないだ関係が半順序関係であり、$下の丸 \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つだったとすると、半順序構造の図として書くと、以下のようになる。
これは集合のそれぞれの元を"含む"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)$と表す。
例として、上記の場合の順序集合の図を以下に示す。
生成される独立命題が有限の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の倍数の自然数すべての集合"というのは、無限集合であり、補集合も無限集合であるため、「どちらか一方がイデアルに含まれ」ていないため、極大イデアルではない。フレチェフィルターも同様である。それを含む極大イデアル/極大フィルターは存在することは(選択公理を用いて)証明できるのだが、具体的に構成することできない(非常に難しい)。このあたり、"選択公理"と関連し、"具体的に構成できない"点がバナッハ・タルスキーパラドクスを思い出す。
[ストーン表現とは]
さて、やっとここまできて、ストーン表現が説明できる。
位相空間で、
- コンパクトで、
- ハウスドルフで、
- 完全非連結 (あるいは開かつ閉集合を基底にもつ ... これは同値)な、
なものをブール空間という。ブール空間$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$の通常の位相 |
|
|
|
可算無限集合$\mathbb{N}$の集合代数$B \simeq \mathcal{P}(\mathbb{N})$ |
たとえば$ [ 0,\frac{1}{n} ]$? |
|
|
|
カントール集合$K$ |
|
|
[ゲーデルの不完全性定理の代数化]
ところで、wikipediaのゲーデルの不完全性定理 - Wikipediaという記事の中に"不完全性定理の代数化”という章があって、
とある。これとの対応を、ざっくりと考えてみると、
- 上記の可算無限集合を変数に持つ$\textrm{F}(X)$が、"ロビンソン算術を含むリンデンバウム代数"に対応し、
- 超フィルターの補集合である超イデアルがフリーのために"具体的に構成"できないことが、"再起可算素イデアルpが存在しない"に対応
するのではないかと、素人考えで勘ぐっているが、正しいのかは定かでない。
[参考]
