序关系

                     

贡献者: hfb25

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

1. 偏序集

定义 1 偏序集、半序集

   如果一个集合 $A$ 上定义了一个序关系 $\prec$,那么称这个集合是带有偏序 $\prec$ 的偏序集(partially ordered set)半序集

   带有偏序 $\prec$ 的偏序集 $A$ 通常记作 $(A,\prec)$.在不致混淆的情况下,可以简称为偏序集 $A$.偏序集上的序关系称为偏序关系(partially ordered relation)

   序关系实际上是给集合中的元素排序,因此 $a \prec b$ 又被称为$a$ 在 $b$ 前,反之 $b \prec a$ 称为$a$ 在 $b$ 后.这种排序方式并不唯一,而且任意两个元素间不一定可以排出前后.

例 1 

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

   其中复数集 $\mathbb{C}$ 上的序关系比较特殊,复数 $a_1+b_1 \mathrm{i} \leq a_2+b_2 \mathrm{i} $ 当且仅当 $a_1\leq a_2$ 且 $b_1 \leq b_2$.复数的序关系通常不使用.

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

例 2 

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

例 3 字典序

   已知 $(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,因此这种序关系称为字典序.

例 4 幂集

   一个集合 $A$ 的幂集2$2^X$ 与子集关系一起构成偏序集.

例 5 

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

2. 全序集

定义 2 全序集

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

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

例 6 

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

例 7 

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

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

定义 3 极小元、极大元

   已知偏序集 $(A,\prec)$:

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

定义 4 最小元、最大元

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

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

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

例 8 

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

习题 1 

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

习题 2 

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

3. 良序集

定义 5 良序集

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

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

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


1. ^ 比如,字典中单词 in 在 a 后,在 it 前.
2. ^ 即集合 $A$ 所有子集的集合.
3. ^ 读者自证.


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

                     

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