良序关系

(重定向自良序關係

数学中,集合S上的良序关系(或良序)需要满足:①是在S上的全序关系。②S的所有非空子集在这个次序下都存在最小元素。等价的说,良序是良基的线序。集合S和这个良序关系一起就叫做良序集合

粗略的说,良序集合的排序方式,使得我們可以逐次考虑一个它的元素,而在还没有检視完所有的元素的任何时候,总是有一个唯一的下一个元素可考虑。

例子

  • 自然数的标准排序≤是良序的。
  • 整数的标准排序≤不是良序的,因为比如整数的集合不包含最小元素。
  • 整数的下列关系R是良序的:
x R y,当且仅当下列条件之一成立:
  1. x = 0
  2. x是正数,而y是负数
  3. xy都是正数,而xy
  4. xy都是负数,而yx
R可以显示为如下:
0 1 2 3 4 ..... -1 -2 -3 .....
R 同构序数ω + ω。
  • 可以定义整数的另一个良序关系如下:x <z y 当且仅当 |x| < |y| 或 (|x| = |y| 且x ≤ y)。
这个良序可以显示为如下:
0 -1 1 -2 2 -3 3 -4 4 ...
  • 实数的标准次序≤不是良序的,因为例如开区间 (0, 1)不包含最小元素。存在着依赖於选择公理的证明,其能夠證明实数可以被良序化,但是这些证明是非构造性证明

性质

在良序集合中,除了整体上最大的那个,所有的元素都有一个唯一的后继元:比它大的最小的元素。但是,不是所有元素都需要有前驱元。作为例子,考虑自然数的一个次序,这里的所有偶数都小于所有奇数,并在偶数和奇数内应用正常的次序。

0 2 4 6 8 ... 1 3 5 7 9 ...

这是个良序集合並被指示为ω + ω。注意尽管所有元素都有后继元(这里没有最大元素),有两个元素缺乏前驱元:零和一。

如果一个集合可被良序化,超限归纳法证明技术可以用来证明给定陈述对于这个集合的所有元素为真。

良序定理,等价于选择公理,声称所有集合都可以被良序排序。良序定理还等价于库拉托夫斯基-佐恩引理

等价表述

如果一个集合是良序的,则下列是等价的:

  1. 所有非空子集合都有最小元素。
  2. 超限归纳法在整个有序集合上成立。
  3. 所有严格递减序列必定在有限多步骤内终止(假定依赖选择公理)。

序数

所有良序集合都唯一地序同构于一个唯一的序数。实际上,这个性质是定义序数背后的动机。

参见