關於布爾代數的一些筆記（一）

04-30

本篇筆記由於草稿突髮狀況，基本要寫完的情況下丟失了所有的文字，因而重新整理，所以不再保證細節方面做到事無巨細，而只是做一些概要，只詳細寫為了以後的文章做準備的內容。

由於是概述，所以我採用了 Jech 的集合論（Set Thoery）的順序，然後結合 Monk 等人的布爾代數手冊（Handbook of Boolean Algebras），做最基本的介紹。

由於字數限制，包佳齊：關於布爾代數的一些筆記（二）接續這篇內容。

一、布爾代數的定義與基本性質

定義1.1 一個結構 $langle mathscr{B}, 0, 1, +, cdot, - angle$ 被稱為布爾代數（boolean algebra），如果 $0, 1 in mathscr{B}$ ，並且 $+, cdot$ 是 $mathscr{B}$ 上二元函數， $-$ 是 $mathscr{B}$ 上一元函數，且它滿足以下布爾代數公理：
$u + v = v + u$ ； $u cdot v = v cdot u$ 。（交換律）

$u + (v + w) = (u + v) + w$ ； $u cdot (v cdot w) = (u cdot v) cdot w$ 。（結合律）
$u cdot (v + w) = u cdot v + u cdot w$ ； $u + (v cdot w) = (u + v) cdot (u + w)$ 。（分配律）
$u cdot (u + v) = u$ ； $u + (u cdot v) = u$ 。（吸收律）
$u + (-u) = 1$ ； $u cdot (-u) = 0$ 。（補足律）

為方便，如不引起歧義，可直接寫作 $mathscr{B}$ 。一般默認優先度 $-$ 高於 $cdot$ 高於 $+$ 。

容易驗證以下性質：

性質1.2 對布爾代數 $mathscr{B}$ ，以及 $u in mathscr{B}$ ，以下性質成立：
(1) $u + u = u$ ； $u cdot u = u$ 。
(2) $u + 0 = u$ ； $u cdot 0 = 0$ 。
(3) $u + 1 = 1$ ； $u cdot 1 = u$ 。
證明：由吸收律 $u cdot 1 = u cdot (u + -u) = u$ ， $u + 0 = u + (u cdot -u) = u$ ，故 $u + u = u + (u cdot 1) = u$ ， $u cdot u = u cdot (u + 0) = u$ ，從而 $u cdot 0 = u cdot (u cdot -u) = (u cdot u) cdot -u = u cdot -u = 0$ ， $u + 1 = u + (u + -u) = (u + u) + -u = u + -u = 1$ 。證畢。

性質1.3 對布爾代數 $mathscr{B}$ ，以及 $u, v, w in mathscr{B}$ ，若 $u cdot v = u cdot w = 0$ ， $u + v = u + w = 1$ ，那麼 $v = w$ 。於是，對任意 $u in mathscr{B}$ ， $-u$ 唯一地滿足補足律。
證明： $v = v cdot (v + u) = v cdot (w + u) = v cdot w + v cdot u = v cdot w$ ，同理它也等於 $w$ 。證畢。
推論1.4 $-(-u) = u$ 。
性質1.5（De Morgan laws) 對布爾代數 $mathscr{B}$ ，以及 $u, v in mathscr{B}$ ，以下性質成立：
$-(u + v) = -u cdot -v$ ； $-(u cdot v) = -u + -v$ 。
證明：我們只證第一個。由性質1.3，只需證 $(u + v) + (-u cdot -v) = 1$ 以及 $(u + v) cdot (-u cdot -v) = 0$ 。而這些根據分配律與補足律顯然。

我們定義 $u - v = u cdot -v$ ，定義 $u le v$ 當且僅當 $u - v = 0$ 。

性質1.6 $u le v$ 當且僅當 $u + v = v$ 當且僅當 $u cdot v = u$ 。
證明：若 $u le v$ ，那麼 $u + v = (u + v) cdot (-v + v) = (u cdot -v) + v = v$ ；若 $u + v = v$ ，那麼 $u cdot v = u cdot (u + v) = u$ ；若 $u cdot v = u$ ，那麼 $u cdot -v = u cdot v cdot -v = 0$ 。
性質1.7 $u + v$ 是 $u, v$ 上確界， $u cdot v$ 是 $u, v$ 下確界。
證明：由吸收律以及性質1.6， $u + v$ 是上界。對任意 $w ge u, w ge v$ ， $(u + v) cdot -w = u cdot -w + u cdot -w = 0$ ，故是上確界。 $u cdot v$ 是下確界同理。

下面我們舉幾個例子，好對布爾代數有更加直觀的理解。

例1.8
(0) 零代數， ${0}$ ，其中 $0 = 1$ 。（一般排除這種代數）
(1) ${0, 1}$ 最簡單的布爾代數。
(2) ${0, u, -u, 1}$ 。
(3) ${0, u, v, u + v, -u cdot -v, -v, -u, 1}$ 。可以參見題圖。
例1.9
(4) 集合代數，對任意集合 $S$ ， $mathscr{P}(S)$ 上有布爾代數結構 $langle mathscr{P}(S), emptyset, S, cup, cap, - angle$ 。
(5) 拓撲正則開代數，對任意拓撲空間 $langle X, au angle$ ，有布爾代數結構 $ext{ro}(X)$ ，其中元素為所有正則開集，即 ${U in au: ext{int cl}(U) = U}$ 。具體內容在……中介紹。
(6) Lindenbaum 代數。令 $mathcal{L}$ 為一階語言， $S$ 是其上所有語句，我們知道其上 $leftrightarrow$ 是等價關係，令 $mathscr{B} = S/leftrightarrow$ 為所有等價類的集合，容易驗證其上有布爾代數結構 $langle mathscr{B}, 0, 1, lor, land, eg angle$ ，其中 $0 = [varphi land eg varphi]$ ， $1 = [varphi lor eg varphi]$ ， $[varphi] land [psi] = [varphi land psi]$ ， $[varphi] lor [psi] = [varphi lor psi]$ ， $eg[varphi] = [ eg varphi]$ 。

二、布爾代數的同態與同構

定義2.1 稱 $mathscr{A} subset mathscr{B}$ 為 $mathscr{B}$ 的子代數（subalgebra），如果 $0, 1 in mathscr{A}$ ，並且對任意 $u, v in mathscr{A}$ ， $u + v, u cdot v in mathscr{A}$ 。

我們記 $mathscr{B}^+ = mathscr{B}-{0}$ ，它是一個偏序集，相比於 $mathscr{B}$ 上平凡的偏序，這個偏序集上有很多重要的應用，它在無窮組合中也是經常用到的，不過現在不會詳談。如果感興趣，在我的專欄 Kunen 集合論第一版第二章整理中，有一些涉及，可以作為了解和參考。

定義2.2 若 $a in mathscr{B}^+$ ， $mathscr{B}upharpoonright a = {u in mathscr{B}: u le a}$ 是一個布爾代數。

注意到它保持 $mathscr{B}$ 上的偏序和 $+, cdot$ ，但 $u$ 的補則是 $a - u$ 。我們還注意到這並不是子代數，但是當我們涉及到布爾代數上的同態基本定理的時候，我們就知道它其實是同構與某一個商代數的（定理3.7）。

定義2.3 令 $mathscr{B, C}$ 是兩個布爾代數，映射 $h: mathscr{B o C}$ 是布爾代數同態（homomorphism）當且僅當它滿足：
$h(0) = 0$ ， $h(1) = 1$ ；
$h(u + v) = h(u) + h(v)$ ， $h(u cdot v) = h(u) cdot h(v)$ ， $h(-u) = -h(u)$ 。
一個布爾代數到它自身的同態稱作自同態。

注意到其中有一些條件是可以省去的。

定義2.4 稱 $h: mathscr{B o C}$ 是同構（isomorphism）如果 $h$ 是同態且是雙射。一個布爾代數到它自身的同構稱作自同構（automorphism）。

下面有個基本的判定條件。

引理2.5 如果 $h: mathscr{B o C}$ 是雙射，並且它滿足對任意 $u, v in mathscr{B}$ ， $u le v$ 當且僅當 $h(u) le h(v)$ ，那麼它是同構。
證明：只需證明它是同態。根據定義， $h(u + v) ge h(u), h(v)$ ，若 $h(w) ge h(u), h(v)$ ，那麼 $w ge u, v$ ，即 $w ge u + v$ ，所以 $h(w) ge h(u + v)$ 。同理 $h(u cdot v) = h(u) cdot h(v)$ 。若 $h(0) = w in mathscr{C}$ ，由於是滿射，令 $h(u) = 0$ ，則根據 $u ge 0$ 我們得到 $0 ge w$ ，所以 $h(0) = 0$ ，同理保持 $1$ 。取補同樣滿足。

一行無話。

定義2.6 $h: mathscr{B o C}$ 如果是 $mathscr{B}$ 到 $mathscr{C}$ 的某個子代數的同構，那麼就稱 $h$ 為嵌入（embedding)。顯然嵌入就是單同態。

為了之後的主要需求（（二）中定理5.3-4），我們定義稠密。

定義2.7 布爾代數 $mathscr{A}$ 是 $mathscr{B}$ 的稠密（dense）子布爾代數，如果它是子布爾代數且對任意 $u in mathscr{B}^+$ ，存在 $v in mathscr{A}^+$ 使得 $v le u$ 。
定義2.8 布爾代數嵌入 $h: mathscr{B o C}$ 稱作稠密嵌入，如果 $h(mathscr{B})$ 是 $mathscr{C}$ 的稠密子布爾代數。

三、濾和理想

定義3.1(a) $mathscr{B}$ 是一個布爾代數，一個子集 $I subset mathscr{B}$ 被稱作 $mathscr{B}$ 的理想（ideal），如果它滿足下列條件：

(1) $0 in I$ ， $1 otin I$ ；
(2) 對任意 $u, v in I$ ， $u + v in I$ ；
(3) 如果 $u,v in mathscr{B}$ ， $u in I$ 且 $v le u$ ，那麼 $v in I$ 。

與它對偶的定義是濾。

定義3.1(b) $mathscr{B}$ 是一個布爾代數，一個子集 $F subset mathscr{B}$ 被稱作 $mathscr{B}$ 的濾（filter），如果它滿足下列條件：
(1) $1 in F$ ， $0 otin I$ ；
(2) 對任意 $u, v in F$ ， $u cdot v in I$ ；
(3) 如果 $u,v in mathscr{B}$ ， $u in F$ 且 $u le v$ ，那麼 $v in F$ 。

直觀上來說，濾說了些比較大的元素，而理想說了些比較小的元素。其實兩個定義的 (1) 條件都並不必要，只是習慣以及為了防止商代數是零代數的情況出現，我們去除全集的情況，這樣定義。

如果學習過偏序集的理想和濾，就知道這裡的定義是很相似的。一個平凡的理想是 ${0}$ ；此外還有主理想，素理想等定義。對偶也有，這裡不再贅述。

我們考慮一個同態 $h: mathscr{B o C}$ 。

定義3.2 $ker{h} = {u in mathscr{B}: h(u) = 0}$ 。

我們證明 $ker{h}$ 是一個理想。

性質3.3 $ker{h}$ 是一個理想。
證明：顯然。

接下來我們定義商代數。

引理3.4 對理想 $I subset mathscr{B}$ ，考慮關係 $sim$ ，使得 $u sim v$ 當且僅當 $(u - v) + (v - u) in I$ 。則 $sim$ 是等價關係。
證明：只需證傳遞性。令 $(u - v) + (v - u) in I$ ， $(v - w) + (w - v) in I$ ，那麼 $u - w = u cdot -w = u cdot -v cdot -w + u cdot v cdot -w in I$ ， $w - u = w cdot -u = w cdot v cdot -u + w cdot -v cdot -u in I$ ，它們的和也在 $I$ 中。得證。
引理3.5 對理想 $I subset mathscr{B}$ 以及它誘導的等價關係 $sim$ ，它的商集合 $mathscr{B}/sim$ 上有一個自然的布爾代數結構。
證明：首先定義運算。 $[0]_sim = 0$ ， $[1]_sim = 1$ ， $[u]_sim + [v]_sim = [u + v]_sim$ ， $[u]_sim cdot [v]_sim = [u cdot v]_sim$ ， $-[u]_sim = [-u]_sim$ 。下面證明其合理。這裡只證加法，其它的「給讀者留做習題」。
考慮到對稱性，只用考慮一邊。對於 $u_1 sim u_2$ ，我們只需證 $u_1 + v sim u_2 + v$ ，我們算 $(u_1 + v) - (u_2 + v) = u_1 cdot -u_2 cdot-v + v cdot -u_2 cdot -v = u_1 cdot -u_2 cdot -v$ ， $(u_2 + v) - (u_1 + v) = u_2 cdot -u_1 cdot-v + v cdot -u_1 cdot -v = u_2 cdot -u_1 cdot -v$ ，兩者的和為 $ig((u_1 - u_2) + (u_2 - u_1)ig) cdot v in I$ 。得證。
定義3.6 上述引理中的布爾代數稱為商布爾代數（quotient algebra），記作 $mathscr{B}/I$ 。

下面我們證明同態基本定理。

定理3.7 $mathscr{B}/ker{h} cong h(mathscr{B})$ 。
證明：我們構造典範映射， $ilde{h}: mathscr{B}/ker{h} o h(mathscr{B}), [u]_sim mapsto h(u)$ ，我們證明這是個合理的映射。對任意 $u_1 sim u_2$ ，即 $hig((u_1 - u_2) + (u_2 - u_1)ig) = 0$ ，我們有 $h(u_1 - u_2) = 0$ ， $h(u_2 - u_1) = 0$ ，即 $h(u_1) cdot -h(u_2) = 0$ ， $h(u_1) + -h(u_2) = 1$ ，於是有 $h(u_1) = h(u_2)$ 。其次我們證明它是雙射。滿射顯然，我們證明單射。若 $h(u_1) = h(u_2)$ ，那麼 $hig((u_1 - u_2) + (u_2 - u_1)ig) = 0$ ，故 $(u_1 - u_2) + (u_2 - u_1) in ker{h}$ ，即 $u_1 sim u_2$ 。得證。

考慮某個布爾代數 $mathscr{B}$ 以及 $a in mathscr{B}^+$ ，考慮映射 $h: mathscr{B} o mathscr{B}upharpoonright a, u mapsto a cdot u$ ，這顯然是同態，它的 $ker$ 為 ${u in mathscr{B}: a cdot u = 0}$ ，我們知道它是理想，所以 $mathscr{B}upharpoonright a cong mathscr{B}/ker{h}$ 。

考慮到下列命題，我們其實可以用環的方式去探討布爾代數的理想和商，於是同構定理也成立。

引理3.8 $u oplus v = (u - v) + (v - u)$ ，則 $langle mathscr{B}, oplus, cdot, 0, 1 angle$ 構成特徵為 $2$ 的含幺環。
證明：明顯 $u oplus u = 0$ 。 $oplus$ 的結合律證明比較繁雜，但是是純粹的計算，這裡不再證明。 $0 oplus u = u$ ，因而是阿貝爾群。而可證 $-$ 與 $cdot$ 服從分配律，所以 $oplus$ 與 $cdot$ 也服從分配律。乘法結合律顯然，幺元顯然。得證。
引理3.9 $I subset mathscr{B}$ 是布爾代數 $mathscr{B}$ 的理想當且僅當它是環 $mathscr{B}$ 的真理想。
證明：（「 $Rightarrow$ 」）首先若 $u, v in I$ ，那麼 $u oplus v in I$ ， $u cdot v in I$ ，其次對任意 $w in mathscr{B}$ ， $w cdot u in I$ ，而 $1 otin I$ ，故它是環的真理想。（「 $Leftarrow$ 」） $1 otin I$ 。對任意 $u, v in I$ ，對任意 $w le u$ ， $w = w cdot u in I$ ，現在只需證 $u + v in I$ ，但 $u + v = (u cdot -v) + v le (u cdot -v) + v + v cdot -u = (u cdot -v) oplus v in I$ ，得證。