§2.4　序关系（ordered relations）

由于等价关系具有对称性，因此，两个具有等价关系的元素就无所谓次序之分了.但现实世界中，有很多关系对所涉及的对象而言是有次序之分的.例如人与人之间的父子关系；数值之间的“≤”关系等，即它们不具有对称性.下面讨论一种很重要的次序关系.

定义2.4.1　设R是集合A上的二元关系.如果R具有自反性、反对称性和传递性，则称R为一个偏序（或半序、部分序）关系，并将R记为≤，读作“小于等于”，且称<A，≤>为偏序集.

【例2.4】　设A为集合，则<ρ（A），⊆>是一个偏序集，其中ρ（A）是A的幂集.

【例2.5】　设N为自然数集，则<N，≤>是一个偏序集，其中“≤”是数值间的小于或等于关系.

定义2.4.2　设<A，≤>是一个偏序集.如果对任意x，y∈A，都有x≤y或y≤x，则称<A，≤>是一个全序集（total ordering）或链（chain）.

易知，例2.5中的<N，≤>就是一个全序集，而例2.4中的<ρ（A），⊆>则不是全序集.

我们也可以用2.1节中介绍的关系图来表示一个在集合A上的偏序关系≤.但由于所有偏序关系都具有自反性及传递性，因此，其关系图可以用更简单的形式来表示：以平面上的点代表<A，≤>中的元素，对任何x，y∈A，

（1）若x≤y，且x≠y，则将x画在y的下面；

（2）若x≤y，且x≠y，且没有异于x和y的z∈A使得x≤z≤y，则在x与y之间用直线连接它们.

用以上方法表示的图称为Hasse图.

【例2.6】　设A={2，3，6，12，24，36}，令关系≤为

易知，≤是A上的一个偏序关系，<A，≤>的Hasse图如图2.2所示.

设<A，≤>是一个偏序集，显然，对任何B⊆A，<B，≤>也为一个偏序集.

定义2.4.3　设<A，≤>是一个偏序集，若存在b∈B，使得对任何x∈B都有x≤b（b≤x），则称b为B的最大（小）元（the greatest（least）element）.

比如，在例2.6中，

（1）若B={2，6，12，36}，则B的最大元为36，最小元为2；

（2）若B={2，3，6}，则B的最大元为6，没有最小元；

（3）若B={12，24，36}，则B没有最大元，最小元为12；

（4）若B={2，3，6，12，24，36}=A，则B既无最大元，也无最小元

由定义知，最大（小）元如果存在，则是唯一的.

定义2.4.4　设<A，≤>是一个偏序集，若存在b∈B，使得B中没有元素x≠b满足b≤x（x≤b），则b为B的极大（小）元（maximal（minimal））.

比如，在例2.6中，A的极大元为24和36，极小元为2和3.

由定义容易知道，B的最大（小）元必是B的极大（小）元，反之则不然.

定义2.4.5　设<A，≤>是一个偏序集，B⊆A.如果存在a∈A，使得对任何x∈B，均有x≤a（a≤x），则称a为B的上（下）界（upper（lower）bound）.

比如，在例2.6中，

（1）若B={6，12}，则B的上界为12，24，36，下界为2，3，6；

（2）若B={24，36}，则B无上界，而下界为2，3，6，12；

（3）若B={2，3}，则B的上界为6，12，24，36，而无下界；

（4）若B={2，3，24，36}，则B既无上界，也无下界.

由定义及举例不难看出，B（⊆A）的上界和下界可以在B中，也可以在A中.

定义2.4.6　设<A，≤>是一个偏序集，B⊆A.如果a是B的一个上（下）界，且对B的任何一个上（下）界x，均有a≤x（x≤a），则称a为B的上（下）确界，或称a为B的最小上界（最大下界）（least upper bound（greatest lower bound）），通常记为a=sup（B）（a=inf（B））.

比如，在例2.6中，

（1）若B={2，3，6}，则B的上确界为6，无下确界；

（2）若B={12，24，36}，则B无上确界，而下确界为12.

由定义知，若B无上（下）界，则B必无上（下）确界，即便B有上（下）界，若不唯一，则B也不一定有上（下）确界.

定义2.4.7　设<A，≤>是一个偏序集，若A的任何非空子集均有最小元，则称<A，≤>为良序集（well-ordered set）.

由定义不难知道，良序集一定是全序集，但反之不然.例如，<Z，≤>是全序集，但它不是良序集，这是因为由负整数构成的Z的子集无最小元.

定理2.4.1　<A，≤>为良序集的充分必要条件是：

（1）<A，≤>是全序集；

（2）A的每个非空子集均有极小元.

证明：必要性.设<A，≤>为良序集.

（1）任取x，y∈A，则{x，y}有最小元x或者y，于是x≤y或者y≤x，故<A，≤>是全序集.

（2）任取A的非空子集B，由假设B有最小元a，显然a也是B的极小元.

充分性.设偏序集<A，≤>满足（1）、（2），对A的任意非空子集B，由（2）知B有极小元a.下证a也是B的最小元.对任意x∈B，由（1）以及a是极小元知，a≤x，故a是B的最小元.从而由定义知<A，≤>是良序集.