偏序集合
在数学中配备了偏序关系的集合
偏序集合(英语:Partially ordered set,简写 poset)在数学中,特别是序理论中,是指配备了偏序关系的集合。这个关系形式化了排序、顺序或排列这个集合的元素的直觉概念。这种排序不必然需要是全部的,就是说不需要但也可以保证在这个集合内的所有对象的相互可比较性。(在数学用法中,全序是一种偏序)。偏序集合定义了偏序拓扑。
定义
设R是非空集合A上的一个二元关系,若R满足: 自反性、反对称性、传递性,则称R为A上的偏序关系。
以下为定义:
非严格偏序,自反偏序
给定集合S,“≤”是S上的二元关系,若“≤”满足:
自反性:∀a∈S,有a≤a;
反对称性:∀a,b∈S,a≤b且b≤a,则a=b;
传递性:∀a,b,c∈S,a≤b且b≤c,则a≤c;
则称“≤”是S上的非严格偏序或自反偏序。
严格偏序,反自反偏序
给定集合S,“<”是S上的二元关系,若“<”满足:
反自反性:∀a∈S,有a≮a;
非对称性:∀a,b∈S,a<b ⇒ b≮a;
传递性:∀a,b,c∈S,a<b且b<c,则a<c;
则称“<”是S上的严格偏序或反自反偏序。
严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。
下面是一些主要的例子:
自然数的集合配备了它的自然次序(小于等于关系)。这个偏序是全序
整数的集合配备了它的自然次序。这个偏序是全序。
自然数的集合的有限子集 {1, 2, ..., n}。这个偏序是全序。
自然数的集合配备了整除关系。
给定集合的子集的集合(它的幂集)按包含排序。
向量空间的子空间的集合按包含来排序。
一般地说偏序集合的两个元素x和 y 可以处于四个互斥关系中的恰好一个: 要么 x < y,要么 x = y,要么 x > y,要么 x 和 y 是“不可比较”的(非前三者)。全序集是用不存在第四种可能性的集合: 所有元素对都是可比较的,并且声称三分法成立。自然数整数有理数和实数都关于自然代数排序是全序的,而复数不是。这不是说复数不能全序排序;比如我们可以按词典次序排序它们,通过 x+iy < u+iv 当且仅当 x < u 或 (x = u 且 y < v),但是这种排序没有合理的大小意义因为它使得 1 大于 100i。按绝对大小排序它们产生在其中所有对都是可比较的预序,但这不是偏序因为 1 和 i 有相同的绝对大小但却不相等,违反了反对称性。
Dilworth 定理
对于一个偏序集,其最少链划分数等于其最长反链的长度。
参考资料
最新修订时间:2024-05-21 15:29
目录
概述
定义
参考资料