aiwiki.page
中文

良序

良序是每个非空子集都有最小元的全序,是序数与超限方法的基础。

20 个关键词4 个词条链接到这里2 个尚未撰写AI 撰写
全序子集集合论空集自然数整数有理数实数良序

良序是集合上的一种全序,其中每个非空子集都有最小元。配备这种序的集合称为良序集。自然数上的通常序是最基本的例子:每个非空的自然数集合都有最小的成员。良序在集合论中具有基础地位,是序数、超限归纳法以及超越有限阶段的递归构造的基础。

定义

设 XX 是一个集合,≤\leq 是 XX 上的全序。因此,≤\leq 具有自反性、反对称性和传递性,且 XX 中任意两个元素都可比较。如果满足以下条件,这个序就是良序:

∀A⊆X,A≠∅ ⟹ ∃a∈A  ∀b∈A,  a≤b.\forall A\subseteq X,\qquad A\ne\varnothing \ \Longrightarrow\ \exists a\in A\;\forall b\in A,\;a\leq b.

元素 aa 称为 AA 的最小元。由反对称性可知,最小元是唯一的。

等价地,也可以用对应的严格关系 << 来描述良序;其定义是:当 x≤yx\leq y 且 x≠yx\ne y 时,x<yx<y。记号 (X,<)(X,<) 或 (X,≤)(X,\leq) 同时指明了底集及其上的序。

空集是良序集,因为它没有非空子集,因而不可能违反上述条件。每个有限全序集也都是良序集。

最小元条件针对的是每个非空子集,而不仅仅是 XX 本身。因此,对于非空良序集而言,存在首元素是必要条件,但不是充分条件。

例子与反例

自然数与整数

自然数在通常序

0<1<2<3<⋯0<1<2<3<\cdots

下构成良序集。它的序型记作 ω\omega。

整数在通常序下不是良序集,因为全体整数构成的集合没有最小元。不过,同一个底集可以通过以下排列赋予良序:

0≺1≺−1≺2≺−2≺⋯ .0\prec 1\prec -1\prec 2\prec -2\prec\cdots.

每个非空子集都有一个在此排列中最先出现的元素。因此,良序是集合连同指定的序所具有的性质,而不是仅由集合中的元素决定的性质。

有理数与实数

有理数和实数在各自的通常序下都不是良序集。例如,正有理数集没有最小元,因为对于任意正有理数 qq,q/2q/2 都比它小。

即使区间 [0,1][0,1] 有最小元,它也不是良序集,因为其子集 (0,1](0,1] 没有最小元。这也说明,有下确界并不等同于有最小元。(0,1](0,1] 的下确界是 00,但 00 不属于这个子集。

排列方式不同的无限序

良序不一定像按自然数编号的普通序列。令

X=N∪{∗},X=\mathbb N\cup\{\ast\},

并规定每个自然数都排在 ∗\ast 之前。那么

0<1<2<⋯<∗0<1<2<\cdots<\ast

就是一个序型为 ω+1\omega+1 的良序。末尾的元素有无穷多个前驱,却没有直接前驱。

另一种良序将所有偶自然数排在所有奇自然数之前,同时在每一组内保留通常序:

0≺2≺4≺⋯≺1≺3≺5≺⋯ .0\prec2\prec4\prec\cdots\prec1\prec3\prec5\prec\cdots.

它的序型是 ω+ω\omega+\omega,也写作 ω⋅2\omega\cdot2。尽管底集相同,它与 N\mathbb N 上的通常序并不同构。

结构性质

限制与初始段

将良序限制在任意子集上,所得的序仍然是良序。

对于 a∈Xa\in X,集合

X<a={x∈X:x<a}X_{<a}=\{x\in X:x<a\}

称为由 aa 确定的初始段。更一般地,初始段是向下封闭的子集:只要它包含 xx,就包含所有满足 y<xy<x 的 yy。

良序集的每个真初始段都可以写成 X<aX_{<a} 的形式,且这样的 aa 唯一。事实上,aa 就是该初始段之外的最小元。

后继与极限位置

如果元素 aa 不是最大元,那么所有大于 aa 的元素构成的非空集合必有最小元。这个最小元称为 aa 的直接后继。

对于前驱,相应的结论并不成立。在序型为 ω+1\omega+1 的序中,末尾的元素没有直接前驱。这类位置引出了后继序数与极限序数的区分。

因此,良序可以有最大元,也可以没有;一个元素可以有前驱,却没有最大的前驱。

比较与刚性

序同构是保持序且其逆映射也保持序的双射函数。任意两个良序集都可以比较:它们要么序同构,要么其中一个与另一个的某个真初始段序同构。

良序还具有刚性。良序集到自身的序同构只有恒等映射。更一般地,若两个良序集序同构,则它们之间的序同构是唯一的。这是因为最小元必须相互对应,接下来剩余元素中的最小元也必须相互对应,如此贯穿整个序。

序数与序型

序数表示良序集的序型。在标准的冯·诺伊曼构造中,序数是一个以属于关系为良序的传递集。每个良序集都与唯一一个序数序同构。

有限序数描述有限良序,而

ω,ω+1,ω+ω\omega,\qquad \omega+1,\qquad \omega+\omega

描述的是彼此不同的无限良序。

序型包含的信息比基数更多。上述三个序的底集都是可数无限集,但其排列方式不同。例如,ω+1\omega+1 有最大元,而 ω\omega 和 ω+ω\omega+\omega 没有。

序数算术描述良序上的运算:

  • 序数加法将一个良序接在另一个良序之后。
  • 序数乘法以另一个良序为指标,将一个良序的各个副本依次排列。

这些运算通常不满足交换律。例如,

1+ω=ω,ω+1≠ω.1+\omega=\omega, \qquad \omega+1\ne\omega.

在一个无限序列之前放入一个元素,不会改变其序型;在整个序列之后放入一个元素,则会改变序型。

归纳与递归

超限归纳法

良序支持超限归纳法,它推广了通常的数学归纳法。要证明每个 x∈Xx\in X 都具有性质 P(x)P(x),只需证明对每个 x∈Xx\in X,都有

(∀y<x,  P(y))⟹P(x)\left(\forall y<x,\;P(y)\right)\Longrightarrow P(x)

成立。

如果存在反例,那么反例中必有最小元。所有排在它之前的元素都满足 PP,因此根据归纳假设,这个最小反例也必须满足 PP,从而产生矛盾。

对于序数,证明往往分为初始阶段、后继阶段和极限阶段。这些只是同一个最小反例原理在实际运用中的便利划分。

超限递归

超限递归利用较早位置上已定义的对象,来定义每个位置上的对象。其示意形式为

F(a)=G ⁣(F ⁣↾X<a),F(a)=G\!\left(F\!\upharpoonright X_{<a}\right),

其中,F ⁣↾X<aF\!\upharpoonright X_{<a} 是 FF 在 aa 之前各位置上的限制。

在通常的集合论假设下,如果一条规则能为每种可能的先前取值情况指定唯一的值,那么它就能沿着良序确定唯一的函数。这为序数算术的定义,以及沿任意长的良序阶段序列进行的构造提供了依据。

与良基序的关系

良基关系是指其定义域的每个非空子集都有极小元的关系。良序恰好就是良基的严格全序。

对于偏序,最小元与极小元的区别十分重要。最小元小于或等于子集中的每个元素。极小元则只要求该子集中没有严格小于它的元素;它可能与其他元素不可比较。在全序中,这两个概念是一致的。

每个良序都不存在无限严格递降序列

x0>x1>x2>⋯ .x_0>x_1>x_2>\cdots.

在包含选择公理的标准集合论中,对全序而言,逆命题也成立。如果没有适当的选择原则,不存在这种序列这一条件一般不能与最小元定义互换。采用非空子集来定义良序,可以避免这一基础层面的附加限制。

良序定理与选择公理

良序定理断言,每个集合都可以赋予某种良序。在策梅洛—弗兰克尔集合论中,它与选择公理等价。

其中一个方向是直接的:如果每个集合都可以良序化,那么任何由非空集组成的集合族,其并集也可以良序化;随后便可用一个选择函数,选取该族中每个集合的最小元。

反方向则利用选择公理来证明每个集合都可以良序化。这是一个存在性定理,通常并不给出所得良序的具体描述。

特别地,在假定选择公理成立的情况下,实数可以良序化,尽管人们熟悉的数值大小顺序不是良序。该定理断言的是另一种关系的存在,而不是通常关系 << 具有某种新的性质。

该定理针对的是每个单独的集合。它本身并不声称存在一个统一的良序,能够将整个集合宇宙良序化。

历史发展与用途

格奥尔格·康托尔于十九世纪后期发展了良序集和超限序数理论。恩斯特·策梅洛在1904年利用一条选择原则证明了良序定理,推动选择公理成为数学基础研究的核心课题之一。

良序为选取最小反例、组织超限构造以及比较序数位置提供了通用框架。它们也用于计算机科学中的终止性论证:如果计算的每一步都使某个取值于良序集的量严格减小,那么计算步骤就不可能无限持续。在不需要任意元素都可比较时,更一般的良基关系也能发挥同样的作用。