格与序导论

第1章 有序集

序, 序, 序——其渗透着整个数学和日常生活, 以至于我们将序视为理所当然的存在. 序以各种伪装出现: 第一, 第二, 第三, ...; 更大vs更小; 更好vs更坏. 进展, 先后, 倾向都可以被归结为序的概念. 我们的首要任务在于打磨这些不够精确的想法, 形式化"小于等于"这种关系. 除了呈现有序集的例子和基本性质, 本章也引入了图表, 其使得序理论生动形象起来.

有序集

究竟何谓序? 或者更数学地说, 何谓有序集?

例子1.1.
定义1.2. 令P是一个集合. P上的一个序 (或者说偏序) 是P上的一个二元关系≤满足对于所有的x,y,z∈P有
  1. x≤x;
  2. x≤y和y≤x可以推出x=y;
  3. x≤y和y≤z可以推出x≤z.
以上的条件分别被称为自反性, 反对称性和传递性. 一个装备有序关系≤的集合P就成为了一个有序集 (或者说偏序集). 有些作者使用缩略词poset. 在任意集合上, =是一个序, 即离散序. 集合P上满足自反和传递但不必然满足反对称性的关系被称为一个半序, 或者有些作者称为预序. P上的一个序关系≤导出了P上的一个严格不等的关系<: P中x<y当且仅当x≤y并且x≠y. 基于<而不是≤重述以上三个条件也是有可能的. 其他与≤相关的记号是可以预见到的, 例如我们交换地使用x≤y和y≥x. x≰y的意思是'x≤y为假'. [译注: 换言之, (x,y)∉≤.] 我们使用不那么常见的符号∥表示不可比较性, 记x∥y如果x≰y且y≰x. 如果P是一个有序集而Q是其一个子集, 那么Q从P那里继承了自然的序关系, 我们将其称为导出序 [译注: 也有人将其翻译成诱导序].
定义1.3. 链和反链. 令P是一个有序集, 那么P被称为一个链, 如果对于所有的x,y∈P都有x≤y或y≤x, 即任意两个元素都是可以比较的. 链也被称为线序集或者全序集. 反链是另一个极端. 有序集P被称为一个反链, 如果x≤y仅当x=y. 显然, 在导出序下, 链的子集是链, 反链的子集是反链. 令P是n元素集{0,1,…,n−1}, 我们用n表示赋予了集合P序0<1<⋯<n−1的链, 而n‾表示作为反链的P. 任何集合S都可以被赋予离散序而成为反链S‾.
定义1.4. 序同构. 我们称P和Q是序同构的, 如果存在一个保持序关系的双射φ:P→Q. 换言之, 对于任意的x,y∈P, x≤y当且仅当φ⁡(x)≤φ⁡(y). 实际上, 保持序关系的映射必然是单射, 因为 φ⁡ (x) = φ⁡ (y) ⟺ φ⁡ (x) ≤ φ⁡ (y) & φ⁡ (y) ≤ φ⁡ (x) ⟺ x≤y & y≤x ⟺ x=y 当然, 双射并非都是保持序关系的. 一旦我们有了一个序同构φ:P→Q, 那么逆映射φ−1:Q→P也是一个序同构.
例子1.5. 实数集ℝ在通常序下形成了一个链. ℕ≔{1,2,3,…}, ℤ, ℚ也都在通常序下成为了链. 这些序关系都与其上的运算相协调. 我们记ℕ0≔ℕ∪{0}.

第2章 格与完全格

定义2.1. 令P是一个有序集而S⊆P. 一个元素x∈P被称为S的一个上界, 如果对于每个s∈S有s≤x. 下界可以被对偶地定义. S的所有上界构成的集合记作Su (读作'S upper'), 而其所有下界构成的集合记作Sl (读作'S lower'): Su ≔ { x∈P | ( ∀ s∈S ) s≤x } , Sl ≔ { x∈P | ( ∀ s∈S ) s≥x } . 既然≤是传递的, Su总是一个up-set而Sl总是一个down-set. 如果Su拥有最小元x, 那么x被称为S的最小上界. 等价地, x是S的最小上界, 如果
  1. x是S的一个上界;
  2. 对于所有S的上界y, x≤y.
S的最小上界存在当且仅当存在x∈P满足 ( ∀ y∈P ) [ ( ( ∀ s∈S ) s≤y ) ⟺ x≤y ] 并且这就刻画了S的最小上界. 对偶地, 如果Sl拥有最大元, 那么其被称为S的最大下界. 既然最小元和最大元都是唯一的, 那么最小上界和最大下界也是唯一的. S的最小上界也被称为S的上确界, 记作sup⁡S. S的最大下界也被称为S的下确界, 记作inf⁡S.
评注2.2. 顶和底. 在上确界和下确界的定义中, 存在两种极端的情况, 即空集和有序集本身, 这值得单独一说. 回忆一下, 当P的顶和底元素存在时, 其被分别记为⊤和⊥. 很容易看出来, 如果P具有顶元素, 那么Pu={⊤}而此时sup⁡P=⊤. 若P没有顶元素, 那么Pu=∅, 因而sup⁡P并不存在. 根据对偶性, 当P具有底元素时, inf⁡P=⊥. 现在考虑空集的情况, 此时每个x∈P都是其上界, 因此∅u=P而sup⁡∅存在当且仅当P具有底元素, 若存在则有sup⁡∅=⊥. 对偶地, 若P有顶元素, 则inf⁡∅=⊤.
记号2.3. 我们记sup⁡{x,y}为x∨y (读作'x join y'), inf⁡{x,y}为x∧y (读作'x meet y'). 类似的, 我们记⋁S (即'join of S') 和⋀S (即'meet of S') 而不是sup⁡S和inf⁡S. 若有必要指出join和meet在某一个特定的有序集P中寻找, 那么记⋁PS和⋀PS. 我们也经常遇到S={Ai}i∈I的情形, 其中I是一个指标集, 那么⋁i∈IAi是比⋁{Ai|i∈I}更紧凑的记号.
定义2.4. 令P是一个非空的有序集.
  1. 若x∨y和x∧y对于任意的x,y∈P均存在, 那么P被称为一个格.
  2. 若⋁S和⋀S对于任意的S⊆P均存在, 那么P被称为一个完全格.
评注2.5.
  1. 令P是任意的有序集. 如果x,y∈P而x≤y, 那么{x,y}u=↑y且{x,y}l=↓x. 因为↑y的最小元是y而↓x的最大元是x, 我们有x∨y=y和x∧y=x. 特别地, 鉴于≤是自反的, x∨x=x且x∧x=x.
  2. 在有序集P中, {x,y}的最小上界x∨y可能出于两种原因并不存在:
    1. 因为x和y没有共同的上界;
    2. 因为它们没有"最小的"上界.
  4. 令P是一个格, 对于a,b,c,d∈P,
    1. a≤b可以推出a∨c≤b∨c和a∧c≤b∧c.
    2. a≤b且c≤d可以推出a∨c≤b∨d和a∧c≤b∧d.
  5. 令P是一个格. 令a,b,c∈P并假定b≤a≤b∨c. 既然c≤b∨c, 我们有(b∨c)∨c=b∨c. 因此, b∨c ≤ a∨c ≤ ( b∨c ) ∨c = b∨c 即a∨c=b∨c. 这个简单的观察及其对偶在计算图上的join和meet时是特别有用的.
评注2.6.
  1. 令P是非空有序集. 如果x≤y, 那么x∨y=y且x∧y=x, 因此为了证明P是一个格, 只需要考虑不可比较的元素是否拥有join和meet即可. 特别地, 每个(非空)链是一个格. 显然, ℝ,ℚ,ℤ,ℕ在其通常的序关系下是一个格. 它们都不是完全格, 每个都缺失顶元素, 而一个完全格必然拥有顶和底. 然而, 对于实数x<y, 闭区间[x,y]是一个完全格.

第3章 形式概念分析

第4章 模格, 分配格, 布尔格

第5章 表示: 有限情形

第6章 Congruences

第7章 完全格与Galois连接

第8章 完全偏序 (CPO) 和不动点定理

第9章 域 (domain) 和信息系统

第10章 极大原理

第11章 表示: 一般情形