序关系

                     

贡献者: hfb25; xiaokuc

  • 本词条需要更多讲解,便于帮助理解。
预备知识 二元关系

   法国的布尔巴基学派曾对数学里的结构进行梳理,并且提炼出了三大基本结构:代数结构,拓扑结构以及序结构,序结构通常是一个装备了序关系的集合,它在组合数学,分析学中有着奠基的作用。

1. 1.偏序关系

   偏序关系(partially ordering relation)是一类二元关系。称在非空集合 $A$ 上关系 $\leq$ 是一个偏序关系,如果 $\leq$ 满足条件:

  1. 自反性:$\forall x\in A,x\leq x$;
  2. 反对称性:$\forall x,y\in A,\ x\leq y,\ y\leq x \Rightarrow x = y $;
  3. 传递性:$\forall x,y,z\in A,\ x\leq y,\ y\leq z \Rightarrow x\leq z $。

   我们称 $\leq$ 是 $A$ 上的偏序关系,并且把赋予偏序结构 $\leq$ 的集合 $A$,即 $(A;\leq)$ 称为偏序集(半序集,有序集,序集)

例 1 

   各种数集(包括 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$)按通常的序关系(大小关系)构成偏序集。

   注解:一般我们不提及 $\mathbb{C}$ 上的序关系,因为从 $\mathbb{R}$ 中拓展得到的 $\mathbb{C}$ 上的序关系性质并不良好,但有必要时也可以在 $\mathbb{C}$ 上定义一些特别的序关系来便于研究

   这个例子说明序关系实际上是数与数大小关系的抽象。

例 2 整除序

   $\mid$ 是自然数集 $\mathbb{N}$ 上的一个可除关系, 即 $m \mid n$ 表示 $ m$ 整除 $n$.则 $(\mathbb{N};\mid)$ 是一个偏序集.

例 3 包含序

   设 $E$ 是一个集合, $\mathbb{P}(E)$ 表示 $ E $ 的所有子集 (包括空集 $ \varnothing $) 组成 的集合, 称为 $ E $ 的幂集.定义 $\mathbb{P}(E)$ 上的包含关系 $\subseteq $ 为序关系. 则 $(\mathbb{P}(E) ; \subseteq) $ 是 一个有序集.

例 4 有限偏序集的例子

   设集合 $A = \{a,b,c\}$,关系 $\leq\!= \{(a,a),(a,b),(a,c),(b,b),(c,c)\}$,可以验证 $\leq$ 是 $A$ 上的偏序关系。

例 5 字典序

   已知 $(A,\prec),(B,\leq)$ 是两个偏序集,那么笛卡尔积 $A\times B$ 按某个序关系 $\leqslant$ 构成偏序集。这个序关系 $\leqslant$ 满足:

  1. $\forall(a_1,b_1),(a_2,b_2) \in A\times B, a_1\prec a_2 \Rightarrow (a_1,b_1)\leqslant(a_2,b_2)$;
  2. $\forall(a_1,b_1),(a_2,b_2) \in A\times B, a_1=a_2, b_1\leq b_2 \Rightarrow (a_1,b_1) \leqslant (a_2, b_2)$。

   由于字典通常按照这样的顺序编排1,因此这种序关系称为字典序。

例 6 小时百科词条序

   小时百科的知识树(目录树)可以看做一个偏序集,"词条预备知识"是这个偏序集的序关系,词条 A 在词条 B 前意味着词条 A 是词条 B 的预备知识

2. 1.exp。序的对偶原理

   从偏序的定义来看,我们发现它是有方向性的,如果我们把方向取反,自然而然能得到一个和原偏序有着千丝万缕关系的新偏序,也就是偏序的对偶关系。

引理 1 序对偶

   设 $A$ 是一个非空集合. 若 $R$ 是 $E$ 的一个序关系, 则 $R$ 的对偶关系 $R^{d}$ 也是 $A$ 的一个序关系

   证明留作读者自行完善。

   我们将以上引理换一种方式叙述就得到了这条神奇的玩意儿:

定理 1 对偶原理

   设 $A$ 是一个非空集合. 则关于 $(A;\leq)$ 的任意一个命题,都存在与之相对应的 $(A;\geq)$ 上的一个命题

   于是大多数情况下,我们考虑一对互为对偶的序关系时只用考虑其中一个(如同考虑非交换结构时只考虑左一样)

   (以下内容待修整,修整原因:部分符号与序论符号不一致,顺序不合理)

3. 全序集

定义 1 全序集

   偏序集 $(A;\leq)$ 称为全序集(totally ordered set)有序集(ordered set),当且仅当对任意 $a,b \in A$,$a \leq b$ 或 $b \leq a$。

   全序集上的序关系称为全序关系(totally ordered relation)

例 7 

   数集 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ 按通常的序关系构成全序集。

例 8 

   将例 5 中的偏序集 $A,B$ 换成全序集,则按同样的序关系,$A\times B$ 也构成全序集。

   一个显然但重要的事实是,任何偏序集的非空子集按原来的序仍是偏序集,任何全序集的非空子集按原来的序仍是全序集。

定义 2 极小元、极大元

   已知偏序集 $(A;\leq)$:

  1. 如果存在某个 $a \in A$,使得对任意 $x \in A, x\leq a$ 都有 $x = a$,那么称 $a$ 为偏序集 $A$ 的极小元(minimal element)
  2. 如果存在某个 $b \in A$,使得对任意 $x \in A, b\leq x$ 都有 $x = b$,那么称 $b$ 为偏序集 $A$ 的极大元(maximal element)

定义 3 最小元、最大元

   已知偏序集 $(A;\leq)$ 的某个非空子集 $B$:

  1. 如果存在某个 $a \in B$,使得 $\forall x \in B, a \leq x$。那么 $a$ 被称为 $B$ 的最小元(least element)
  2. 如果存在某个 $b \in B$,使得 $\forall x \in B, x \leq b$。那么 $b$ 被称为 $B$ 的最大元(greatest element)

   极大元、极小元与最大元、最小元极易混淆。偏序集的极大元、极小元不一定唯一,但最大元、最小元只要存在必然唯一。在全序集中两者统一。2

例 9 

   集合 $A=\{0,1,2\}$,在上面定义偏序关系 $\leq$ 为 $0\leq 0$, $1\leq 1$, $1\leq 2$, $2\leq 2$。那么子集 $\{0,1\}$ 的极大元为 0 和 1,不存在最大元。

习题 1 

   证明:如果偏序集的某个子集存在最大元,那么它的极大元必然存在且唯一,并且两者相等。

习题 2 

   证明:对于全序集的任意非空子集,如果存在极大元,则最大元必然存在,且两者相等。

4. 良序集

定义 4 良序集

   全序集 $(A,\leq)$ 称为良序集(well-ordered set),当且仅当它的任意非空子集都有极小元。

   良序集上的序关系称为良序关系(well-ordered relation)

   任何良序集的非空子集仍是良序集。


1. ^ 比如,字典中单词 in 在 a 后,在 it 前。
2. ^ 读者自证。


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利