偏序关系

前言：到了二元关系中最后一部分，非常非常抽象，但是理解了就还好，我们一步一步来

0X00 「偏序关系」的基本定义

我们先回到最初的定义：

假设 R 是集合 A 上的关系，如果R是自反的、反对称的和传递的，则称 R 是 A 上的一个偏序，记做 \leqslant 。设 \leqslant 为偏序关系，如果 <x, y> \in \leqslant，则记做 x \leqslant y，读作 x 小于等于 y。

这个非常抽象，我们举个例子：

假设我们有这样的集合 A = \{1, 2, 3\} R 是 A 上的小于等于关系也就是 R = \{<x, y>| x ,y \in A \wedge x \leq y\}

所以 R = \{<1, 2>, <2, 3>, <1, 3>, <1, 1>, <2, 2>, <3, 3>\}

我们画出他的关系图：

显然他是自反的（环）、反对称的（无双向边）、传递的

不知道大家看到这里的大家有没有理解到偏序关系的本质：

偏序关系定义了一种方向，只能正着，反证就不行！

比如这里的小于等于就是只有一种方向，可以 1 \leq 2 就不能 2 \leq 1

至此，我们引出下一个定义可比：

存在这种偏序关系的就叫做可比

由于这种顺序结构，我们可以用哈斯图来表示偏序关系

假设 A = \{1, 2, 3\}, \leqslant 是 A 上的「小于等于」关系，则有

\leqslant \ = \{<1, 2>, <1, 3>, <2, 3>, <1, 1>, <2, 2>, <3, 3>\}

画出哈斯图：

这种自底向上的图就是哈斯图

0X01 「偏序集」的基本定义

理解了偏序关系的基本定义以后，我们就很容易理解偏序集

我们把集合 A 和 A 上的偏序关系 \leqslant 一起称作偏序集，记做<A, \leqslant>

0X02 「偏序集」中的特殊元素

最小元和最大元

我们看到这张图片，最大元就是 a, b, c\ 最小元就是 \emptyset

所以直观来说最大元 就是“最大”的那个，在哈斯图中最上面的

相反最小元就是“最小”的那个，在哈斯图图中最小的

而在这张图中：

而这张图就不存在最大元只存在最小元因为 11 9 12 8 10 7 之间就不可比

极小元与极大元

搞清楚了最大元和最小元，我们继续，还是回到这张图上：

里面的极大元是 11 9 12 8 10 7，极小元只有 1。

极大元的意思就是在可比的那一条链中最大的，极小元的意思就是在可比的那一条链中最小的

上界与下界

之前的概念只在一个集合中，而谈到上下界就必须涉及到两个集合了，现在我们给出定义：

设 <A, \leqslant> 为偏序集，B \subseteq A, y \in A

  • 若 \forall x (x \in B \rightarrow x \leqslant y) 则 y 是 B 的上界
  • 若 \forall x(x \in B \rightarrow y \leqslant x) 则 y 是 B 的下界

假设 A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}\ B = \{2, 3, 6\} ，定义了一个偏序关系并有以下哈斯图：

则 B 的上界就是 \6, 12\

由于 2, 3 之间不可比，所以B 的下界只有 1

上确界与下确界

如果能够理解上界和下界的话，上确界与下确界就更好理解了，简单来说

  • 上确界就是上界中“最小”的那个
  • 下确界就是下界中“最大”的那个

还是上面那个例子，B 的上界是 6, 12, 其中“最小”的就是 6。所以 B 的上确界就是 6。

反之 B 的下确界就是 1。

二元关系就结束了。。。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容