最后更新: 2026-05-26 17:31 查看: 194 次纠错评论(0) 课件开VIP

次序关系(偏序关系)

集合中还有一种重要的关系：次序关系。它可用来比较集合中元素的次序，其中最常用的次序关系是偏序关系和全序关系。

定义2．19 设 $R$ 是集合 $A$ 上的二元关系，若 $R$ 是自反的，反对称的和传递的，则称 $R$是 $A$ 上的偏序关系。又记为 $\leq$（注意，此符号在这里并不意味着小于等于）。

常见的偏序关系有：实数集 $R$ 上的小于等于关系 $\leqslant$ ；正整数集 $Z^{+}$上的整除关系；集合 $A$ 的幂集 $P(A)$ 上的包含关系 $\subseteq$ 等。

定义2．20 若集合 $A$ 具有偏序关系 $R$ ，则称 $A$ 为偏序集，记为 $(A, R)$ 。
上述例子可用偏序集 $(R, \subseteq),\left(Z^{+}, /\right),(P(A), \subseteq)$ 表示。
偏序集 $(A, \leq)$ 可以通过图形表示，这样的图叫哈斯图。哈斯图的画法如下：$A$ 中每个元素用结点表示。对于 $a, b \in A$ ，若 $a \leq b$ 则将结点 $a$ 画在结点 $b$ 之下；若 $a$ 与 $b$ 之间不存在其他元素 $c$ ，使 $a \leq c, c \leq b$ ，则在 $a$ 与 $b$ 之间用一条线相连，得到的图形称为哈斯图。

哈斯图是对关系图的简化：由于偏序关系是自反的，即对每个元素 $a$ ，都有 $a R a$ ，因此在图上省去自环；由于偏序关系是传递的，即若有 $a R c, c R b$ 则必有 $a R c$ ，因此省去 $a$ 与 $c$之间的连线；对于 $a R b$ ，规定 $b$ 在 $a$ 的上方，则可省去箭头。

例 2.31 （1）设集合 $A=\{2,3,6,12,24,36\}$ ，／是 $A$ 上的整除关系，偏序集 $(A, /)$ 的哈斯图如图 2．2（a）所示。（2）$A=\{1,2,3,4,5,6\}$ ，偏序集 $(A, \leq)$ 的哈斯图如图 2.2 （b）所示。（3）设集合 $A=\{1,2\}$ 。则 $P(A)=\{\varnothing,\{\{1\},\{2\},\{1,2\}\}$ ，偏序集 $(P(A), \subseteq)$ 的哈斯图如图 2.2 （c）所示。
定义 2.21 对于集合 $A$ 上的偏序关系 $R$ ，如果 $A$ 中两个元素 $a, b$ 有 $a R b$ ，则称 $a$ 与 $b$ 是可比较的。

在例 2.30 （3）中，$\varnothing$ 与 $\varnothing,\{1\},\{2\},\{1$ ， $2\}$ 都是可以比较的，而 $\{1\}$ 与 $\{2\}$ 无包含关系，故不可比较。所以，在偏序集合中任意两个元素不一定是可比较的。

下面，介绍偏序集合中所具有的几个特殊元素。
 ![图片](/uploads/2025-01/ee2d04.jpg)
 
 定义2．22 设 $(A, \leq)$ 是一个偏序集合，$B \subseteq A$ 。则
（1）如果存在一个元素 $b \in B$ ，对所有 $b^{\prime} \in B$ ，都有 $b^{\prime} \leq b$ ，则称 $b$ 是 $B$ 的最大元；如果都有 $b \leq b^{\prime}$ ，则称 $b$ 是 $B$ 的最小元。
（2）如果存在一个元素 $b \in B$ ，且在 $B$ 中不存在元素 $b^{\prime}$ ，使 $b \neq b^{\prime}, b \leq b^{\prime}$ ，则称 $b$ 是 $B$ 的极大元；如果在 $B$ 中不存在元素 $b^{\prime}$, 使 $b \neq b^{\prime}, b^{\prime} \leq b$ ，则称 $b$ 是 $B$ 的极小元。

（3）如果存在一个元素 $a \in A$ ，对所有 $b^{\prime} \in B$ ，都有 $b^{\prime} \leq a$ ，则称 $a$ 是 $B$ 的上界；如果对所有 $b^{\prime} \in B$ ，都有 $a \leq b^{\prime}$ ，则称 $a$ 是 $B$ 的下界。
（4）如果 $a \in A$ 是 $B$ 的上界，且对 $B$ 中每个上界 $a^{\prime}$ ，都有 $a \leq a^{\prime}$ ，则称 $a$ 为 $B$ 的上确界（或称最小上界）；如果 $a \in A$ 是 $B$ 的下界，且对 $B$ 中每个下界 $a^{\prime}$ ，都有 $a^{\prime} \leq a$ ，则称 $a$ 为 $B$ 的下确界（或称最大下界）。

这几个概念有明确区别，不能混淆。
容易证得如下结论。
（1）如果在 $B$ 中存在最大元（最小元），则必唯一。
（2）$B$ 中最大元（最小元）必为极大元（极小元），而极大元（极小元）不一定是最大元（最小元）。

例 2.32 以例 2.30 （1）为例。
（1）设 $B=\{2,3,6\}, ~ B$ 的最大元为 6 ，最小元不存在。 $B$ 的极大元为 6 ，极小元为 2,3 。 $B$ 的上界是 $6,12,24,36$ ，下界不存在。 $B$ 的上确界是 6 ，下确界不存在。
（2）设 $B=\{2,3\}, B$ 的最大元，最小元不存在。 $B$ 的极大元，极小元均为 $2,3 \circ B$ 的上界是 $6,12,24,36$ ，下界不存在。 $B$ 的上确界是 6 ，下确界不存在。

上面的例子说明偏序集或它的子集不一定存在最小元（最大元）；上（下）界可以存在，也可以不存在；若存在，也不一定唯一；若上（下）确界存在，则必唯一。

极大元（极小元）不一定唯一，并且可以证明任意两个极大元（极小元）是不可比较的。证明留作习题。

定理 2.22 设偏序集 $(A, \leq), B \subseteq A$ ，如果 $B$ 中存在最大元（最小元），则必唯一。
证明：用反证法证明。假设 $b_1, b_2$ 是 $B$ 的最大元，$b_1 \neq b_2$ ，由于 $b_1$ 是最大元，可知 $b_2 \leq b_1$ ；又由于 $b_2$ 是最大元，可知 $b_1 \leq b_2$ ；又因偏序关系 $\leqslant$ 具有反对称性，所以 $b_1=b_2$ 。

最小元性质的证明与此类似。

定理 2.23 设偏序集 $(A, \leq), B \subseteq A, B$ 中最大元（最小元）必为极大元（极小元）。
证明留作习题。
在例 2.30 （2）中，任意两个元素是可以比较的。这样的偏序关系被称为全序关系。
定义2．23 设缇集合 $A$ 上的偏序关系，如果对于 $A$ 中任意两个元素 $a, b \in A$ ，必有 $a \leq b$或 $b \leq a$ ，则称 $\leq$ 是 $A$ 上的全序关系（或称线性次序关系）。如果集合 $A$ 上具有全序关系，则称 $A$ 为全序集或线性次序集，记为 $(A, \leq)$ 。

例 2.30 （ 1 ），（3）就不是全序关系。
应用上述概念，我们可以引入一个在计算机科学中常用的词典次序概念。
设 $R$ 是集合 $A$ 上的全序关系，令 $P=A \cup A^2 \cup \ldots \cup A^n=\cup_{i=1}^n A^i$ ，也就是说 $P$ 是由有序 $t$ 元组 $(t \leq n)$ 所组成的集合。在 $P$ 上定义关系 $S$ 为：

对 $P$ 中任意两个元素 $\left(a_1, a_2, \ldots, a_t\right)$ 和 $\left(b_1, b_2, \ldots, b_r\right), t \leqslant r \leqslant n,\left(a_1, a_2, \ldots, a_t\right)$ $R\left(b_1, b_2, \ldots, b_r\right)$ 当且仅当下面 3 个条件之一成立。
（1）$\left(a_1, a_2, \ldots, a_t\right)=\left(b_1, b_2, \ldots, b_t\right)$ ；
（2）$a_1 \neq b_1$ ，且在 $A$ 中 $\left(a_1, b_1\right) \in R$ ；
（3）$a_i=b_i, i=1,2, \ldots, k(k<t)$ ，且 $a_{k+1} \neq b_{k+1}$ 以及在 $A$ 中 $\left(a_{k+1}, b_{k+1}\right) \in R$ 。
又，如果 $\left(\left(a_1, a_2, \ldots, a_t\right),\left(b_1, b_2, \ldots, b_r\right)\right) \notin S$ ，则 $\left(\left(b_1, b_2, \ldots, b_r\right),\left(a_1, a_2, \ldots, a_t\right)\right) \in S$ 。

容易验证 $S$ 是 $P$ 上的全序关系（证明留作习题），并称 $S$ 为 $P$ 上的词典序。
通常的英文词典是词典序的特例，如设 $A=\{a, b, c, \cdots, z\}, A$ 上的全序关系记为 $\leq$ ，使 $a \leq b \leq c \leq \cdots \leq z$ ，并设 $P=A \cup A^2 \cup A^3$ ，也就是说 $P$ 是由小于或等于 3 个英文字母所构成的英文字全体。设 $S$ 是 $P$ 上的字典序，那么，me $S$ men（条件 1）；beg $S$ men（条件 2）；men $S$ met （条件 3）；get $S$ go（最后规定）。

拟序关系
定义 2.24 集合 $A$ 上的二元关系 $R$ 是反自反的和传递的，称 $R$ 为 $A$ 上的拟序关系。称 $(A$ ， $R$ ）为拟序集，或记为 $(A,<)$（注意，此符号 $<$ 在这里也不意味着小于）。

常见的拟序关系有：实数集 $R$ 上的小于关系 $<$ ；集合 $A$ 的幂集 $P(A)$ 上的真包含关系С。对于拟序关系，有如下定理。
定理 2.24 集合 $A$ 上的二元关系 $R$ 是拟序的，则 $R$ 必为反对称的。
证明：若 $R$ 不是反对称的，则存在 $a, b \in A$ ，使得 $(a, b) \in R,(b, a) \in R$ ，因为 $R$ 是拟序的，所以 $R$ 是传递的，因此有 $(a, a) \in R$ ，与 $R$ 反自反矛盾。所以 $R$ 反对称。

由定理 2.24 ，可知拟序关系实际上是满足反自反的，反对称的和传递的。同时也可以看出拟序关系和偏序关系之间有着一定的联系。拟序集 $(A,<)$ 偏序集 $(A, \leq)$ 有着同样的哈斯图。

由拟序关系，偏序关系的定义以及闭包的定义容易得到如下性质。
定理 2.25 设 $R$ 是 $A$ 上的二元关系，则
（1）若 $R$ 是 $A$ 上的拟序关系，则 $r (R)=R \cup I_A$ 是 $A$ 上的偏序关系。
（2）若 $R$ 是 $A$ 上的偏序关系，则 $R-I_A$ 是 $A$ 上的拟序关系。
证明留作习题。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：偏序关系

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)