良序集
集合论术语
设集合(S,≤)为一全序集,≤是其全序关系,若对任意的S的非空子集,在其序下都有极小元,则称≤为良序关系,(S,≤)为良序集。
定义
全序集的任一非空子集均有极小元,则称该全序集为良序集。
简介
等价地说,良序是良基的线序。
粗略的说,良序集合的排序方式,使得我们可以逐次考虑一个它的元素,而在还没有检视完所有的元素的任何时候,总是有一个唯一的下一个元素可考虑。
良序的例子及反例
1、自然数集在通常序下是良序集。
2、整数集在通常序下不是良序集,例如该集合本身就没有一个极小元。
3、整数的下列关系R是良序的:x R y,当且仅当下列条件之一成立:
x=0;
x是正数,而y是负数;
x和y都是正数,而x≤y;
x和y都是负数,而y≤x。
这个序关系可以表示为:
0 1 2 3 4 …… -1 -2 -3 -4 -5 ……
4、实数集在通常序下不是良序集。
良序的性质
在良序集合中,除了整体上最大的那个,所有的元素都有一个唯一的后继元:比它大的最小的元素。但是,不是所有元素都需要有前驱元。作为例子,考虑自然数的一个次序,这里的所有偶数都小于所有奇数,并在偶数和奇数内应用正常的次序。
这是个良序集合并被指示为ω+ω。注意尽管所有元素都有后继元(这里没有最大元素),有两个元素缺乏前驱元:零和一。
如果一个集合可被良序化,超限归纳法证明技术可以用来证明给定陈述对于这个集合的所有元素为真。
良序定理,等价于选择公理,声称所有非空集合都可以被良序排序。良序定理还等价于佐恩引理
良序的等价条件
对全序集(S,≤),下列命题是等价的:
(1)(S,≤)是良序集,即其所有非空子集都有极小元。
(2)超限归纳法在整个全序集(S,≤)上成立。
(3)(S,≤)上的所有严格递减序列必定在有限多步骤内终止(假定依赖选择公理)。
证明:使用循环证明法。
(1)→(2):反设超限归纳法在(S,≤)上不成立,则存在一个性质φ,使得对S中任意元素x,只要φ对S中小于x的任何元素都成立,那么φ对x也成立,然而φ并非对S中所有元素都成立,即S中所有不满足φ的元素组成的集合A是非空集,则A在序关系≤下不可能有最小元素,否则该最小元素应满足φ,矛盾。
(2)→(3):对序列的首项使用超限归纳法,则结论是显然的。
(3)→(1)(依赖选择公理):对S的任一非空子集A,用选择公理每次从A中选出一个元素,使得从第二次开始每次选出的元素都比前一次的小,则选出的所有元素构成一严格递减序列,该序列必定在有限步内终止,但序列终止的唯一可能是选出了一个元素x使得A中没有比x小的元素,从而x是A中的最小元素。
参考资料
最新修订时间:2022-08-25 14:31
目录
概述
定义
简介
良序的例子及反例
参考资料