一个偏序集可能不存在smallest element,即使存在,也可能对于某些子集不存在smallest element.若它的每一个子集有一个smallest element,则称该集合为良序集(well ordered set).它的order称为良序(well ordering).

值得指出:每一个良序集必是全序的(totally order).因为$\{x,y\}$构成一个子集,那么无论是$x$为first element,还是$y$是first element,都有$x \le y$或者$y \le x$.

例子:

(i)每一个自然数$n$,$n$的所有predecessor组成的集合.即集合$n$是良序的,以大小关系为序.

(ii)全体自然数组成的集合$\omega$是良序的,同样以大小为序.

(iii)集合$\omega \times \omega$,序关系$(a,b) \le (x,y)$$\Leftrightarrow$$(2a+1)2^y \le (2x+1)2^b$,不是良序,$(a,b+1) \le (a,b)$$\forall a,b$,这意味着$\omega \times \omega$不存在least element.

考察集合$\omega \times \omega$的子集$E = \{(a,b) | (1,1) \le (a,b)\}$,则$E$有least element $(1,1)$,但是$E$仍然不是良序的,因为$E$的某些子集不存在least element,所有$(a,b) \neq (1,1)$组成的集合不存在least element.

(iv)$\omega \times \omega$对于字典序构成良序集.

对于良序集,我们有类似于数学归纳法的过程:考察良序集$X$的子集$S$,若任意$X$中的元素$x$满足:entire initial segment $s(x)$包含在$S$中,则$x$本身属于$S$.于是Principle of transifinite induction (超限归纳法)断言:$S=X$.

一般的归纳法与超限归纳法有两点明显的差异:(1)一般归纳法是从predecessor到当前元素,而超限归纳法要求当前元素的所有predecessor是一个集合.(2)超限归纳法没有要求归纳基础.对于(1),在良序集中,一个元素可能不存在直接前导(immediate predecessor).在自然数集$\omega$上,超限归纳法等价于数学归纳法,在一般的良序集上,两者不等价.

例:令$X = \omega^+$,即$X=\omega \cup \{\omega\}$,序关系如下:$\omega$中元素的序保持不变,$\forall n \in \omega$,$n < \omega$,此时$X$是一个良序集,问:是否存在一个子集$S \subset X$,使得$0 \in S$,当$n \in S$时,有$n+1 \in S$,答:有,即$S=\omega$.

第二个差异更多的是语言方面的,而不是概念上(本质的)的,或者说其实超限归纳法已经包含这部分内容.设$x_0$为$X$的smallest element,则$s(x_0)=\emptyset$,于是$s(x_0) \subset S$,根据超限归纳法的假设,$x_0 \in S$.

需要证明这个超限归纳原理,证明不是很难:若$X-S$非空,则存在smallest element $x \in X-S$,这意味着它的initial segment $s(x)$中的每一个元素属于$S$,根据假设,$x \in S$,导致矛盾,故$X-S$只能是空集.

定义：称良序集$A$为良序集$B$的continuation,如果满足:(1)$B$是$A$的子集,即$B$是$A$的一个initial segment;(2)$B$中元素的序和它们在$A$中元素的序一致.

$X$为良序集,$a,b \in X$,$b<a$,则$s(a)$是$s(b)$的continuation,自然,$X$是$s(a)$和$s(b)$的continuation.

设$\mathscr{C}$为某个良序集的initialsegments组成的集合,则$\mathscr{C}$相对于continuation是一个链(chain).

$\mathscr{C}$中元素是良序集,任意两个不同的元素来说,其中一个是另一个的continuation.若一簇良序集构成的集合$\mathscr{C}$对于continuation构成一个chain,$U$是$\mathscr{C}$中集合的并集,那么存在一个唯一的$U$中的良序,使得$U$是$\mathscr{C}$中每一个不为$U$集合的continuation.或者说良序集的chain的并仍然是一个良序的,必须注意,这里的序必须是相对于continuation而言的,若order是inclusion,结论不成立.

证明如下:$a,b \in U$,$\exists A, B \in \mathscr{C}$,使得$a \in A$,$b \in B$,于是,或者$A=B$,或者$A$和$B$中的一个是另一个的continuation.无论何种情形,$a,b$属于$\mathscr{C}$中某一个集合,定义$U$中order如下:对于每一对$\{a,b\}$,它的序取$G$中某个集合(它包含$a$和$b$)中的顺序,$\mathscr{C}$是一个chain,这个order是确定的.也就是说刚才定义的序确实是一个order,同时是一个well ordering.

$U$的非空子集必有非空交集(因为这里面的集合非常特殊,一般的交集没有这种性质),必有first element,$\mathscr{C}$为一个continuation,可以得出:集合的first element同时是$U$的first element.

习题:偏序集$X$的子集$A$称为在$X$中是共尾(cofinal)的.若$X$中每一个元素$x$,存在$A$中元素$a$,使得$x \le a$.证明每一个全序集含有一个cofinal well ordered subset.

良序集之所以重要,是因为下面的结论:

良序定理[Well ordering theorem]：每一个集合可以良序化.

更好的说法是:对于每一个集合$X$,存在以$X$为domain的良序,必须注意,这里并没有说此良序和给定集合$X$上的原来的某些结构有关系.因此如果说偏序集或者全序集中的序不是一个良序时,并不意味着无法将它良序化.

证明这个结论使用Zorn引理.给定集合$X$,考虑$X$中所有良序子集构成的集簇$W$,$W$中元素是$X$中的子集$A$和$A$中的良序,我们通过continuation定义$W$中的一个偏序.

$W$非空,因为$\emptyset \in W$.若$X \neq \emptyset$,$\forall x \in X$,$\{(x,x)\}$.

若$\mathscr{C}$是$W$中的一个chain,则$\mathscr{C}$中集合的并集$U$拥有唯一的良序,使得$U$大于或等于$\mathscr{C}$中的每一个集合.这意味着Zorn引理的假设成立,于是存在maximal well ordered set,设它为$M \in W$,集合$M$必然等于整个集合$X$.

若存在$X$中元素$x \notin M$,那么$M$可以继续扩大,把$x$放在$M$中所有元素之后即可.

习题:一个全序集是良序的,当且仅当每一个元素的严格前驱构成的集合是well ordered.这个条件能否用于偏序集?Well ordering theorem包含选择公理.$R$为集合$X$的一个偏序,存在$X$中的一个全序$S$,使得$R \subset S$,也就是任何一个偏序可以在不扩大定义域的情形下扩展为全序.