偏序集

在序论中, 偏序集是指一个集合 $X$, 它带有一种将其元素比较大小的方法, 称为偏序. 通常将偏序记为 $\le$, 这样, 对元素 $x,y\in X$, 就可以记 $x\le y$, 表示 $x$ 小于或等于 $y$. 在偏序集中, 我们并不要求任何两个元素都能比较大小, 也就是说, 我们允许有元素 $x,y\in X$, 使得既没有 $x\le y$, 也没有 $y\le x$.

例如, 实数在通常的大小关系下构成偏序集, 此时任何两个元素都可比较大小. 又例如, 一个集合的所有子集在包含关系下也构成偏序集, 也就是说, 一个子集小于等于另一个子集, 是指前者包含于后者. 此时, 就并非所有元素都能比较大小, 因为两个子集有可能互不包含.

偏序集也可视为范畴, 其对象为偏序集的元素, 其态射 $x\to y$ 为偏序集的大小关系 $x\le y$. 此时, 任两个不同构的对象间至多有一个态射. 在高阶范畴论中, 偏序集也就是 $(0,1)$-范畴.

1定义

定义 1.1 (偏序集). 集合 $X$ 上的偏序是指二元关系 $\le$, 满足以下性质:

•	(自反性) 对任意 $x\in X$, 有 $x\le x$.

•	(传递性) 对任意 $x,y,z\in X$, 若 $x\le y$ 且 $y\le z$, 则 $x\le z$.

•	(反对称性) 对任意 $x,y\in X$, 若 $x\le y$ 且 $y\le x$, 则 $x=y$.

此时, 将二元组 $(X,\le )$ 称为偏序集.

此时, 也使用记号 $x<y$ 或 $x⪇y$ 或 $x\lneqq y$ 来表示 $x\le y$ 且 $x\ne y$.

偏序集之间, 保持序关系的映射称为单调映射.

定义 1.2 (单调映射). 设 $(X,{\le }_X)$ 与 $(Y,{\le }_Y)$ 为偏序集, $f:X\to Y$ 为集合间映射.

•	称 $f$ 为单调映射, 若对任意 $x,y\in X$, 满足 $x{\le }_{X}y$, 都有 $f(x){\le }_{Y}f(y)$.

•	称 $f$ 为严格单调映射, 若对任意 $x,y\in X$, 满足 $x{<}_{X}y$, 都有 $f(x){<}_{Y}f(y)$.

所有严格单调映射都是单调映射, 反之则不一定.

2例子

•	实数集 $\mathbb{R}$ 在通常的大小关系下构成偏序集, 这也是全序集.

•	一个集合的所有子集在包含关系下构成偏序集.

•	若 $(X,\le )$ 是偏序集, 则对任意子集 $Y\subset X$, $(Y,\le )$ 也是偏序集.

•	任何集合 $X$ 上, 都可定义 “离散偏序”, 即 $x\le y$ 当且仅当 $x=y$. 此时, $(X,\le )$ 也称为反链.

3性质

4相关概念

术语翻译

偏序集 • 英文 partially ordered set, poset • 德文 halbgeordnete Menge (f) • 法文 ensemble partiellement ordonné (m) • 拉丁文 copia partialiter ordinata (f) • 古希腊文 μερικῶς διατεταγμένον σύνολον (n)

偏序 • 英文 partial order • 德文 Halbordnung (f) • 法文 ordre partiel (m) • 拉丁文 ordo partialis (m) • 古希腊文 μερικὴ διάταξις (f)