布尔代数导引

本书可以算是Paul Halmos和Steven Givant共同创作的. 实际上, 在本书出版之时, Paul Halmos已经离世了. 这本书应该算是对于Paul Hamos的Lectures on Boolean Algebras的重新组织和改写.

前言

布尔代数的理论于1847年由英国数学家George Boole创立. 他将其构想为一种对于逻辑进行数学分析的合适演算 (或者说算术). 他的演算的形式与如今的现代版本相当不同, 而现代的版本在1864-1895年间经由William Stanley Jevons, Augustus De Morgan, Charles Sanders Peirce和Ernst Schröder的贡献得以成形. 这种演算作为抽象代数的一支的基础, 由一集等式公理化且承认多种不同的解释, 则在1904年由Edward Huntington奠定.

然而, 只有经过Marshall Stone和Alfred Tarski于1930年代的工作之后, 布尔代数才完全挣脱了逻辑的束缚并成为一个现代数学领域, 其拥有深刻的定理并与诸多数学分支有着重要的联系, 包括代数, 分析, 逻辑, 测度论, 概率统计, 集合论, 和拓扑学. 例如, 在逻辑学中, 除了其与命题逻辑的紧密关联之外, 布尔代数也在各种领域找到了应用, 诸如一阶逻辑的完备性定理的证明, categorical in power的可数一阶理论的Łoś猜想的证明, 以及集合论中选择公理和连续统假设的独立性的证明. 在分析学中, Stone所发现的Stone–Čech紧化和Stone-Weierstrass逼近定理与他对于布尔代数的研究密切相关. 可数完备布尔代数 (也称$\sigma$-代数) 和可数完备集合域 (也称$\sigma$-域) 在测度论的基础中扮演着重要的角色. 在数学之外的领域, 布尔代数也在各种地方找到了应用, 诸如人类学, 生物学, 化学, 生态学, 经济学, 社会学, 而布尔代数以其在计算机科学和哲学中的应用最为突出. 例如, 在计算机科学中, 布尔代数被用于电子电路设计 (门网络), 编程语言, 数据库, 以及复杂度理论.

绝大多数关于布尔代数的书籍可以分为两类. 初等材料喜欢强调这个主题的算术方面 (特别是可以在理论之中表达和证明的定律), 并且经常探索其于命题逻辑, 哲学和电子电路设计方面的应用. 高级专著则呈现了理论更加深刻的方面, 难度适合于研究生和专业数学家 (考虑到理解呈现所需的数学背景和成熟度).

这本书是对于本书第二作者的Lectures on Booleans Algebras进行实质性修订产生的版本, 其尽力采取一种折衷之道. 其面向例如已经学习两年大学层次数学的本科生, 并且需要他们已经获得能够读写证明的成熟度. 本书并不假定读者拥有高级材料往往要求的代数学, 集合论和拓扑学方面的背景. 它的确试图将读者导向这个主题更加深刻的一些方面, 特别是其与拓扑学之间的一些重要联系. 理解呈现所需的代数学和拓扑学的部分知识在文本之中得以建立. 还有一个单独的附录, 其涵盖了偶尔用到的来源于集合论的基本概念, 记号, 以及定理.

本书的第一部分, 到第28章为止, 强调了布尔代数算术和代数的方面. 其不需要拓扑, 集合论也只超出了头两年大学数学会学到的知识一点, 不过有两个重要的例外. 首先, 有两个证明使用的数学归纳法的形式超出了自然数而扩展至有时被称为超限序数的东西上. 超限序数和超限归纳法在附录A中讨论, 但是这两个证明的关键想法在自然数和标准数学归纳法的上下文中已经可以理解. 其次, 第10章呈现的一个布尔代数的重要例子基于拓扑的概念. 这些概念在第9章之中讨论. 然而, 这个例子本身以及其所用到的拓扑, 对于理解本书第一部分的剩余内容而言是不必要的. (章节里的一些高级练习可能的确需要理解这部分材料, 但是这些练习完全可以被想要跳过第9章和第10章的读者忽略.) 本书的第二部分, 尤其是第29章, 第34-41章, 以及第43章, 强调了布尔代数和拓扑学之间的内在联系, 因此需要实质性地用到拓扑学的想法和结果, 必要的拓扑学背景在第9, 29, 32, 33章之中提供.

本书第一部分所讨论的一些重要结果有规范形式定理 (其给出了对于由一集元素所生成的布尔子代数的描述, 第11章), 以及其对于布尔理想而言的类似物 (第18章); 同态扩张定理 (第13章) 以及其于可数无原子布尔代数的同构定理的证明上的应用 (第16章), 还有证明自由代数的存在定理的应用 (第28章); 原子布尔代数的表示定理 (所有的原子布尔代数可以被同构地映射为一个集合域, 并且这个映射保持所有存在的上确界为并, 第14章); 极大理想定理 (每个真理想都可以被扩张为一个极大理想, 第20章), 以及其于著名的表示定理上的应用 (每个布尔代数都同构于一个集合域, 第22章 [译注: Stone表示定理]); 补的存在和唯一性定理 (

第1章 布尔环

环是算术的抽象版本, 而算术这种东西是你在大学之前就学过的. 环的原型是整数环, 其由一个宇宙 (即整数集) 和宇宙上的三种运算构成: 二元的加法和乘法, 以及一元的负 (negation) 运算 (以构成negative). 而且, 还存在着两个突出的整数, 零和一. 整数环满足许多基本的规律, 这对于中学生而言也是熟悉的: 加法和乘法的结合律,$$\begin{array}{rcl}p+(q+r)& =& (p+q)+r\\ p\cdot (q\cdot r)& =& (p\cdot q)\cdot r\end{array}$$加法和乘法的交换律,$$\begin{array}{rcl}p+q& =& q+p\\ p\cdot q& =& q\cdot p\end{array}$$加法和乘法的恒元律 (identity laws),$$\begin{array}{rcl}p+0& =& p\\ p\cdot 1& =& p\end{array}$$加法的逆元律 (inverse law),$$\begin{array}{rcl}p+(-p)& =& 0\end{array}$$以及乘法相对于加法的分配律,$$\begin{array}{rcl}p\cdot (q+r)& =& p\cdot q+p\cdot r\\ (q+r)\cdot p& =& q\cdot p+r\cdot p\end{array}$$整数环和一般的环的区别在于, 对于后者而言, 宇宙可以是任意的非空集合, 而不仅仅是数字的集合, 而其操作于该集合中取参数和值. 加法的结合律, 交换律, 恒元律, 逆元律, 以及乘法的结合律, 还有乘法之于加法的分配律是必须满足的: 这些是环公理. 乘法的交换律在任意的环中不一定满足; 而若满足, 则称这个环为交换的. 并且, 环也不必总是拥有一个幺元 [译注: 原文是unit, 特指乘法的单位元], 这指的是满足乘法的恒元律的一个元素$1$; 而若满足, 则称这个环为含幺环.

除了整数环之外, 还有其他一些自然的环的例子. 最平凡的情况是宇宙中只有一个元素的环: 此元素即零元. 这被称为一个退化的环. 最简单的非退化含幺环就正好有两个元素, 零元和幺元. [译注: 退化的环中的零元也可以被视为幺元; 另外, 这个例子里的零元和幺元当然要求是不同的元素.] 其加法和乘法操作可由算术表描述.$$\begin{array}{|ccc|}\hline +& 0& 1\\ 0& 0& 1\\ 1& 1& 0\\ \hline\end{array}\text{和}\begin{array}{|ccc|}\hline \cdot & 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ \hline\end{array}$$对于这两个算术表的检视告诉我们二元环具有诸多特别的性质. 首先, 每个元素都是其自身的加法逆元:$$p+p=0$$因此, 负运算是多余的: 每个元素都是其自身的负 (negative). 满足这个条件的环被称为是特征为$2$的. 其次, 每个元素都是其自身的平方:$$p\cdot p=p$$具有这种性质的元素被称为是幂等的. 当每个元素都是幂等的, 那么环自身就被称为是幂等的.

一个布尔环是一个含幺元的幂等环. (警告: 一些作者将布尔环定义为幂等环, 不论其是否具有幺元, 他们将我们刚才所定义的概念称为含幺元的布尔环.) 二元环是布尔环最简单的非退化例子. [译注: 之所以说是非退化, 是因为退化环其实也满足布尔环的要求.] 在整本书中这个环将被一直记为$2$, 这和通常的整数$2$的符号相同. 此记号并不常见, 但是却非常方便. 这也与von Neumann对于序数的定义相合 (在这种定义下序数$2$与集合$\{0,1\}$是相同的), with sound general principles of notational economy, and (in logical expressions such as two-valued) with idiomatic linguistic usage.

布尔环的定义中的幂等条件对于这种环的结构有着很强的影响, 其两个最令人惊讶的后果是(a)一个布尔环总是特征为$2$的以及(b)一个布尔环总是交换的. 为了证明, 计算${(p+q)}^2$, 然后使用幂等性就能得到$$0=q\cdot p+p\cdot q$$更细致的推导如下: 根据分配律和幂等律, 可以推出$$\begin{array}{rcl}p+q& =& (p+q)\cdot (p+q)\\ & =& (p+q)\cdot p+(p+q)\cdot q\\ & =& p\cdot p+q\cdot p+p\cdot q+q\cdot q\\ & =& p+q\cdot p+p\cdot q+q\end{array}$$我们为第一个项和最后一个项的左边加上$p$的逆元, 然后给右边加上$q$的逆元, 再动用加法的性质即可得到之前的结果, 特别是要使用逆元律和恒元律.

这个结果可以用来推出前面的两条断言, 一个接着一个. 置$p=q$, 然后使用幂等性就可以得到(a):$$0=p\cdot p+p\cdot p=p+p$$[注记: (b)的推导我稍微修改了一下, 比原文更加直接.] 根据断言(a), 我们可以推出$$p\cdot q+p\cdot q=0=q\cdot p+p\cdot q$$为第一个项和第三个项的右边加上$-(p\cdot q)$即可得到(b):$$p\cdot q=q\cdot p$$

既然我们知道布尔环中的负 (negation) 操作就是恒等 (identity) 操作, 那么就没有必要对于加法的逆而言使用减号, 而我们之后将再也不会这么做.

第2章 布尔代数

令$X$是一个任意的集合, 令$\mathcal{P}(X)$是$X$的所有子集构成的集合 (class) (或者说$X$的幂集). $\mathcal{P}(X)$上存在着三种自然的集合 (set-theoretic) 操作, 分别是二元操作并与交, 还有一元操作补. 根据定义, 两个子集$P$和$Q$的并$P\cup Q$是由存在于$P$中或者$Q$中的元素所构成的集合, 交$P\cap Q$是存在于$P$且存在于$Q$中的元素所构成的集合, 补$P^{\prime }$是($X$中的)不在$P$之中的元素所构成的集合. 这里还有两个突出的子集: 空集$\varnothing$, 其没有元素, 以及全集 (universal set) $X$. 集合$\mathcal{P}(X)$, 连带着并, 交, 补操作, 还有突出的子集$\varnothing$和$X$, 被称为由$X$的所有子集构成的布尔代数 (或者说域(field)), 或者$X$上的幂集代数(power set algebra).

这种代数的算术

第3章 布尔代数和布尔环的比较

布尔代数的理论和布尔环的理论是紧密关联的; 实际上, 它们只是看待相同主题的不同方式. 更确切地说, 每个布尔代数都可以被转变为一个布尔环, 通过定义合适的加法和乘法, 并且反过来, 每个布尔环都可以被转变为一个布尔代数, 通过定义合适的join, meet, 和补.

第4章 对偶原理

每个布尔多项式都有一个对偶: 其被定义为交换$0$和$1$且在同时交换$\wedge$和$\vee$所得到的多项式. 例如, 多项式$$(p\vee q^{\prime })\wedge (p^{\prime }\vee 1)\wedge 0\text{和}(p\wedge q^{\prime })\vee (p^{\prime }\wedge 0)\vee 1$$互为对偶. (布尔多项式的定义和通常的多项式相同, 只是可容许的运算不是加法和乘法, 而是meet, join, 和补.) 每个布尔方程 (或者说等式) 都有一个对偶, 其是通过构造等式两边的布尔多项式的对偶得到的. 方程$$p\wedge p^{\prime }=0\text{和}p\vee p^{\prime }=1$$互为对偶, 以下等式亦如此也:$$p\wedge (q\vee r)=(p\wedge q)\vee (p\wedge r)\text{和}p\vee (q\wedge r)=(p\vee q)\wedge (p\vee r)\text{.}$$

更青睐于布尔代数的语言而非布尔环的语言的一个技术原因是所谓的对偶原理.

第5章 集合域

构造$\mathcal{P}(X)$并非根据$X$作成一个布尔代数的唯一自然方式. 更一般的方式是考虑在交并补下封闭的$\mathcal{P}(X)$的一个任意非空子类$A$; 换言之, 如果$P$和$Q$在$A$之中, 那么$P\cap Q$, $P\cup Q$, $P^{\prime }$也在$A$之中.

第6章 初等关系

代数系统的诸多性质之中通常最不那么深远的是其元素之间的关系 (与子集之间的关系和其上函数之间的关系形成对比). 本章我们将讨论在布尔代数之中成立的一些初等关系. 既然我们之后将要遇到一个特别有力的工具 (即布尔代数的表示定理), 使用这个工具可以将所有的初等关系归约为集合论的平凡结果, 所以目前讨论的目的更多是为了刻画而非穷尽这个主题. 附带的目的是建立之后全书将自由使用的一些记号.

这一整章$p,q,r,\dots$指代的是一个任意但固定的布尔代数$A$的元素.

第7章 序

我们继续与一个任意但固定的布尔代数$A$打交道.

第8章 无穷操作

布尔代数的无限子集可能没有上确界.

第9章 拓扑

有价值的布尔代数例子, 特别是完备布尔代数的例子, 可以使用拓扑空间构造. 本章的目的在于浏览一下构造这种布尔代数所需的基本拓扑概念.

拓扑是一种非常一般的几何, 其适合于研究连续函数. 基本的概念是开集, 其是对于实数集的开区间的概念的抽象和推广. 一个拓扑空间是一个集合$X$, 连带着一个$X$的子集类$\mathcal{T}$, 其满足三个条件: 首先, $\varnothing$和$X$在$\mathcal{T}$之中; 其次, $\mathcal{T}$在有限交下封闭, 意即任意来自于$\mathcal{T}$的集合的有限族之交仍然在$\mathcal{T}$之中; 最后, $\mathcal{T}$在任意并下封闭, 意即任意来自于$\mathcal{T}$的集合的任何族之并仍然在$\mathcal{T}$之中. $X$的元素被称为点, 而$\mathcal{T}$的成员被称为开集.

第10章 正则开集

本章的目的在于讨论又一个布尔代数的例子. 本章的例子可能是到目前为止最为复杂的, 但是这个布尔代数的元素仍然是某个集合的子集. 然而, 运算不再是通常的集合论操作, 所以说这布尔代数也并非集合域. 这种布尔代数的人工例子并不难制造; 不过它们将在之后相当自然地出现, 在布尔代数的一般理论之中扮演着重要角色.

回忆一下 (第9章) 一个拓扑空间$X$中的一个开集是正则的, 如果其与其闭包的内部相合. 接下来的定理 (归功于MacNeille [43]和Tarski [75]) 断言了正则开集构成了一个完备布尔代数, 即$X$的正则开代数.

第11章 子代数

一个布尔代数$A$的(布尔)子代数是$A$的一个子集$B$满足$B$连带着$A$的突出元素和运算 (其被限制于集合$B$) 是一个布尔代数. 代数$A$被称为$B$的一个(布尔)扩张.

第12章 同态

一个布尔同态是一个从某个布尔代数$B$到某个布尔代数$A$的映射$f$, 其满足

1. $f(p\wedge q)=f(p)\wedge f(q)$
2. $f(p\vee q)=f(p)\vee f(q)$
3. $f(p^{\prime })={(f(p))}^{\prime }$

第13章 同态的扩张

一个布尔同态$f$被称为一个布尔同态$g$的扩张, 如果$g$的定义域是$f$的定义域的一个子代数, 并且对于$g$的定义域中的每个$p$都有$$f(p)=g(p)\text{.}$$如果$f$是一族同态的每个成员的扩张, 那么其被称为这个族的共同扩张. 在一般情况下, 一族布尔同态并不一定有共同扩张; 然而, 存在特殊的情形使得这样的扩张的确存在.

第14章 原子

第15章 有限布尔代数

第16章 无原子布尔代数

第17章 congruence和商

第18章 理想和滤子

第19章 理想的格

第20章 极大理想

第21章 同态和同构定理

第22章 表示定理

第23章 Canonical Extensions

第24章 完备同态和完备理想

第25章 完备化

第26章 代数的积

第27章 因子的同构

第28章 自由代数

第29章 布尔$\sigma$代数

第30章 可数链条件

第31章 测度代数

第32章 布尔空间

第33章 连续函数

第34章 布尔代数和布尔空间

第35章 理想的对偶性

第36章 同态的对偶性

第37章 子代数的对偶性

第38章 完备性的对偶性

第39章 布尔$\sigma$空间

第40章 $\sigma$代数的表示

第41章 布尔测度空间

第42章 不完备代数

第43章 积的对偶性

第44章 代数的和

第45章 可数因子的同构