偏序与格:定义笔记

定义. 对于集合P和其上的一个二元关系≤, 如果该二元关系是自反的, 传递的, 反对称的, 则称≤为P上的一个偏序, 而P是一个偏序集, 有时也称P是一个偏序. 当然, 这里我们遵循通常的数学实践, 将(P,≤)记成了P. 有的书籍会要求P非空, 有的则不会.
定义. 如果不要求反对称性而只有自反和对称, 则我们就得到了预序的定义.
定义. 如果一个偏序集的任意两个元素之间均可比较大小, 则将其称为链, 或者线序, 全序.
定义. 对于偏序集P和A⊆P, 若x∈A和x≤y可以推出y∈A, 那么称A是一个上集 (upper set). 当然, 这里的y∈P. 对偶地, 可以定义下集 (lower set).
定义. 记U⁡(P)为偏序集P的所有上集构成的族, D⁡(P)为偏序集P的所有下集构成的族. 它们都是P上的Alexandrov拓扑.
定义. 对于偏序集P和A⊆P, 我们定义A的上闭包 (upper closure) 为↑⁡A={x∈P|∃a∈A s.t. a≤x}对偶地, 可以定义A的下闭包 (lower closure) ↓⁡A. 我们注意到, ↑⁡A是一个上集, ↓⁡A是一个下集. 而且, ↑⁡A是以A为子集的最小上集, ↓⁡A是以A为子集的最小下集. 当A是单元素集{x}时, 我们将↑⁡{x}记为↑⁡x, ↓⁡{x}记为↓⁡x.
定义. 对于偏序集P和x,y∈P, 如果x<y且x≤z≤y可以推出z=x或z=y, 那么我们称y覆盖 (cover) x. 覆盖关系构成了Hasse图. 但是, 在我们说Hasse图的时候, 往往指的不是图论的graph, 而指的是用以形象描绘偏序集的具体图示.
定义. 对于偏序集P, 如果a∈P满足对于每个x∈P, a≤x, 那么就称a是P的最小元. 对偶地, 可以定义最大元.
定义. 对于偏序集P, 如果a∈P满足对于每个x∈P, 要么a和x不可比较, 要么a≤x, 那么就称a是P的一个极小元. 换句话说, x≤a可以推出x=a. 对偶地, 可以定义极大元. 最小元也是极小元, 最大元也是极大元.
定义. 对于偏序集P和S⊆P, 称a∈P是S的一个上界, 如果对于每个s∈S, s≤a. S的所有上界构成的集合记为Su. Su的最小元被称为最小上界. 对偶地, 我们可以定义下界, Sl, 以及最大下界.
定义. 对于偏序集P和x,y∈P, 如果{x,y}具有最小上界, 那么就将其记为x∨y, 读作x和y的并 (join). 对偶地, 我们可以定义x和y的交 (meet) x∧y.
定义. 对于偏序集P, 如果对于每个x,y∈P都有x∨y存在, 那么就称P是一个并半格 (join-semilattice). 对偶地, 我们可以定义交半格 (meet-semilattice). 如果偏序集P既是并半格又是交半格, 那么就称P是一个格 (lattice).
定义. 对于格L, 我们有以下性质.
  1. 幂等律: a∨a=a, a∧a=a;
  2. 交换律: a∨b=b∨a, a∧b=b∧a;
  3. 结合律: (a∨b)∨c=a∨(b∨c), (a∧b)∧c=a∧(b∧c);
  4. 吸收律: a∨(a∧b)=a, a∧(a∨b)=a.
命题. 偏序集L是一个格当且仅当其任意的非空有限子集都有上确界和下确界, 也就是并和交.