跳转到内容

序数

维基百科,自由的百科全书
各种各样的
基本

延伸
其他

圓周率
自然對數的底
虛數單位
無限大

數學集合论中,序數(ordinal number,ordinal)是自然數的一種擴展,與基數相對,著重於次序的性質。大於有限數的序數也稱作超限序數

超限序数是由數學家格奥尔格·康托尔于1897年引入,用來考慮無窮序列,並用來對具有序结构無窮集進行分類。

序数对自然数的扩展

自然数可以用来做两件事:描述一个集合的大小,或者描述序列中一个元素的位置。在有限的世界里这两个概念是一致的,当处理无限集合时人们不得不区分这两者。從大小的概念可以引申出如康托尔描述的“基数”,而位置的概念則被推广到这里将要说明的序数。

基数这一概念可以適用於没有特殊结构的集合,而序数却和同一种称为良序集的特殊集合有着密切的关联(这种关联如此密切,以至于一些数学家不去区分这两个概念)。简单说来,一个良序集是一个全序集(任意给定两个元素,可以定义一个大的、一个小的),不存在无穷降链(但可以有无穷升链),換言之有最小元素。序数可以用来标定任何给定的良序集的元素(最小的元素标定为0,其后的标定为1,再后的标定为2,依此类推),同时也可以用来给出良序集的“长度”—没有用来标定良序集的元素的最小序数就是这个良序集的长度。这个“长度”也称为集合的序类型

任何一个序数都是通过先于它的所有序数构成的集合来定义:实际上,序数最常见的定义就是把每个序数等同于先于它的所有序数构成的集合。比如,序数42就是比它小的序数的序类型,也即,我们把从0(所有序数中最小的)到41(42的直接前驅)这些序数組成集合{0,1,2,…,41},该集合就是序数42。相反的,任何下闭的序数集合—意思是说,任何比该集合中一个序数小的序数都在该集合中—就是(或者等同于)一个序数。

ω²的“火柴杆”图像表示,每个竖杆与一个形如“ω·m+n”的序数相对应(这里mn是自然数)。

目前为止,我们只考虑了有限的序数,即自然数。但无限的序数也是存在的:最小的无限序数是ω,它是自然数(有限序数)的序类型,或者等同于自然数集(实际上,自然数集是良序的—正如所有的序数集合一样—并且自然数集也是下闭的,所以它等同于一个序数,也就是我们定义的ω)。

或许对序数更清晰的直觉可以通过检視最初的几个序数建立起来:如上所述,序数开始于自然数,0, 1, 2, 3, 4, 5, …;然后在所有的自然数之后是第一个無限序数,ω,紧接其后的是ω+1, ω+2, ω+3,等等(加号的确切含义将会在后面给出,这里把它看作標籤就可以了)。在这些之后就是ω·2(也即ω+ω), ω·2+1, ω·2+2,等等,紧接着是ω·3,然后是后来的ω·4。我们通过这种方式形成的序数集合(形如“ω·m+n”的序数,这里mn是自然数),一定有一个序数等同於它:即ω2。更进一步,我们可以得到ω3,ω4,等等,以及ωω和其后的ωω²,乃至其后很多的ε0(这只是给出了几个最小—可数—的序数)。我们可以按照如上方式无限的进行下去。

定义

良序集定义

良序集合是在其中所有非空子集都有一个最小元素的有序集合:这等价于(至少在假定依赖选择公理下)说这个集合是全序的并且没有无限递减序列,這樣說可能較直觀。在实践中,良序的重要性體現於超限归纳法的應用,大致上它是声称,若有一性質可从一个元素的前驱传递到这个元素自身,那麼該性質必定对(给定良序集合的)所有元素成立。如果一个计算(计算机程序或游戏)的状态可以被良序,即在每一个步骤都伴随着“更低”的步骤的方式下,则这个计算必然会终止。

现在我们不想区分两个良序集合,如果它们只是在“它们元素的标记”上不同,或者更加形式的说:如果我们可以把第一个集合的元素和第二个集合的元素配對起來,使得如果在第一个集合中一个元素小于另一个元素,则在第二个集合中第一个元素的配对者也小于第二个元素的配对者,反之亦然。这种一一对应叫做序同构(或严格的递增函数),而这两个有序集合被称为序同构的,或相似的(明显的这是一个等价关系)。假定在两个有序集合之间存在一个序同构,这个序同构是唯一的:所以,把兩個集合視為本质上同一的,并寻求同构类型(类)的“规范”代表,就顯得很自然了。这就是序数所提供的作用,并且它还給任何良序集合的元素提供了规范的标记方式。

所以我们本质上希望定义序数为良序集合的同构类:就是说,作為“是序同构”這一等价关系等价类。但是这涉及一个技术上的困难,事实上这个等价类實在太大了,所以在策梅洛-弗兰克尔集合论中並不是一個集合。但是这不是个严重的困难。我们称序数是在这个类中任何集合的序类型

以等价类来定义序数

序数的最初定义,例如在《数学原理》中,把一個良序的序类型定義为,由类似(序同构)于这个良序的所有良序組成的集合。换句话说,序数是良序集合的等价类。这个定义在ZF和相关的公理化集合论中必须抛弃,因为这些等价类太大而不能是集合。但是这个定义,在类型论、蒯因的新基础集合论和有关的系统中仍可使用(就最大序数的布拉利-福尔蒂悖论,在這裡它給出了頗令人惊讶的另一種解决方式)。

序数的冯·诺伊曼定义

與其定义序数为良序集合的等价类,我们可以尝试定义它为(规范的)代表这个类的某个特定良序集合。因此我们希望把序数构造为特殊的良序集合,使得所有良序集合都同构于一个且只是一个序数。

冯·诺伊曼提议了巧妙的定义,现在被作为了标准:定义每个序数为特殊的良序集合,也就是在它之前的所有序数的集合。形式的说:

一个集合S是一个序数,当且仅当S中的元素在集合从属关系下為全序集,并且S的任意元素也是S的子集。

自然地,这样的一个集合S在集合包含關係下為良序集。这依赖于良基公理:所有非空集合B都有一个元素b不相交于B

按此定義,自然数也是序数。(參見自然數的集合論定義)例如,2是4 = {0, 1, 2, 3}的一个元素,而2等于{0, 1},因而它是{0, 1, 2, 3}的子集。

可以通过超限归纳法证明,所有有限的良序集合都精确的同构于这樣構建的序数的其中一个。

进一步的,所有序数的元素也是序数自身。給定两个序数STST的一个元素,当且仅当ST的真子集。此外,要么ST的一个元素,要么TS的一个元素,要么它们是相等的。所以所有的序数集合都是全序集。事实上: 所有的序数集合都是良序集。这个重要结果一般化了“所有的自然数集合是良序集”此一事实,并允许我们自由地通过序数使用超限归纳法

另一个推论是所有序数S都是完全由小于S的序数作为元素的一个集合。这个陈述以其他序数完全确定了所有序数的內部结构。它被用于证明关于序数的很多其他有用的结果。其中的一个例子是在序数间的次序关系的重要性質:所有的序数集合都有一个上确界,这个序数是通过取在这个集合中的所有序数的并集而获得的。另一个例子是所有序数的搜集不是集合的事实。因为所有序数只會是包含其他序数,從而所有序数的搜集的所有成员也是它的子集。所以,如果这个搜集是个集合,通过定义它自身将必定是个序数;那么它将是自身的成员,这跟正规公理矛盾。(请参见布拉利-福尔蒂悖论)。所有序数的类通常寫為"Ord"、"ON"或"∞"。

一个序数是有限的,当且仅当它的反序也是良序的,即当且仅当它的所有子集都有最大元素

假設良序定理,所有集合都可加上良序關係。利用超窮遞歸可證明所有良序集都與某序數同構(即存在雙射使得a>b ⇔ f(a)>f(b))。有限集合所有良序關係都是同構的,若有n個元素,對應序數就是n。無限集合有無限的良序關係,如自然數集配以0<2<4<...<1<3<5<...對應的序數是ω+ω。

注意,序數的元素必然是序數,而序數的子集亦必然是序數。兩個序數是可以比較大小,即會存在單射f使得a>b ⇒ f(a)>f(b)。一個集合對應的最小序數,就是這集合的基數

其他的定义方式

还有序数定义的其他现代公式化。这些定义在本质等价于上面给出的定义。下面给出其中的一个。一个类S被称为传递性的,如果S的每个元素xS的子集,也就是。序数接着被定义为其成员也是传递的传递集合。从它得出成员们自身也是序数。注意使用了正规公理(基础公理)来证实这些序数通过包含(子集)是良序的。

超限归纳法

超限归纳法在任何良序集合中成立,但是它与序数的关系如此重要而值得在这里重申。

若有一性質可从小于给定序数α的序数的集合传递到α自身,則此性质對所有序数都成立。

就是说,如果“若P(β)对所有β<α为真,P(α)就为真”,则P(α)对所有α都为真。或者更加实际的说:为了证明性质P对所有序数α成立,你可以假定它对于所有β<α的更小的序数们已經是成立的。

超限递归

超限归纳不只能用来证明各種結論,而且还可以用于定义(这种定义方式通常称为超限递归—我们使用超限归纳法证明这个结果是良好定义的):形式陈述写起来太冗长,但重點在於,为了在序数α上定义一个(类)函数,你可以假定它对所有β<α更小的序数们已经定义了。你可以通过超限归纳法证明有且只有一个函数满足直到并包括α的递归公式。

下面是通过在序数上超限归纳定义的一个例子(后面还会给出):通过设F(α)是不在对于所有β<αF(β)的集合中的最小序数,定义出一个函数F。注意我们如何假定F(β)在真正定义F的过程中是已知的:这种表面的悖论完全是超限归纳所允许的。现在实际上F(0)是有意义的,因为没有β<0,所以β<0的所有F(β)的集合是空集,所以F(0)必定是0(所有序数中最小的),现在我们知道了F(0),那么F(1)有意义(它是不等于F(0)=0的最小序数),以此类推(這裡的“以此类推”正正就是超限归纳)。不過,这个例子不是太有趣,因为对于所有序数αF(α)=α:而这可以通过超限归纳严格的证明。

后继与极限序数

任何非零序数都有一个最小元素(就是零)。但它可以有或没有最大元素:42或ω+6有最大元素,而ω没有(没有最大自然数)。如果一个序数有最大元素α,则它是在α之后的下一个序数,它叫做后继序数,就是α的后继者,写做α+1。在序数的冯·诺伊曼定义中,α的后继者是,因为它的元素是α的那些元素和α自身。

不是后继者的非零序数叫做极限序数。使用这个术语的一个理由是,极限序数实际上是在拓扑意义上的所有更小序数的极限(参见序拓扑)。

相当一般的说,在 (αι<γ)是一个序数序列(由极限γ标定的族)的时候,并且如果我们假定 (αι)是递增的(αι<αι′只要ι<ι′),或者至少非递减的,我们定义它的极限是集合{αι}的最小上界,就是说大于这个序列任何一项的最小序数(总是存在)。在这个意义上,极限序数是所有(由自身标定的)更小序数的极限。

因此,所有序数要么是零,要么是一个后继者(有一个良好定义的前驱者),要么是极限。这个区别是重要的,因为很多通过超限归纳的定义依赖于它。经常地,在通过超限归纳在所有序数上定义一个函数F的时候,你定义F(0),和F(α+1)(假定F(α)已定义了),并接着对极限序数δ定义F(δ)为对所有β<δF(β)的极限(這裡的極限,要么是指上述的序数极限,要么是別的极限概念,如果F的值並非序數)。所以,在这个定义中有意思的步骤是后继步骤,而不是极限序数。这种函数(特别是非递减和接受序数值的F)被称为是连续的。我们将看到序数加法、乘法和指数作为它们的第二个参数的函数是连续的。

标定序数类

我们已经提到了任何良序集合都类似(序同构)于一个唯一的序数,或者换句话说,它的元素可以通过小于的序数以递增的方式标定。这尤其适用于任何的序数集合:任何的序数集合都自然的通过小于某个的序数来标定。对于序数的类(通过某个性质而定义的序数的搜集,可能对于形成一个集合太大了),带有稍微的修改同样成立:任何的序数类都可以用序数标定(并且在这个类是无界的时候,这使它处在与所有序数的类的类双射中)。所以我们可以自由的谈论在类中的第个元素(一般而言,第“0”个是指最小的,而第“1”个是次小的,以此类推)。形式上说,这个定义本質上是超限归纳法:一个类的第个元素被定义为(假定对于所有的情況已经定义了),大于对于所有的第个元素的最小元素。

又例如,我们可以应用它于极限序数的类:要么是极限要么是零的第个序数是(參見序數算術中關於序數乘法的定義)。类似的,我们可以考虑“加法不可分解”的序数(意味着它是非零序數,且不能是两个严格更小的序数的):第个加法不可分解序数被标定为。标定序数类的技术经常在不动点的論述中有用:例如,使得的第个序数被写为

闭无界集合与类

一个序数被称为是无界的或共尾的,当给定任何序数,总是有这个类的某个元素大于它的时候(则这个类必定是真类,就是说不能是集合)。它被称为是闭合的,如果在这个类中序数的一个序列的极限總會在这个类中:或者等价的说,当标定(类-)函数是连续的,即对于這个极限序数,(在这个类中第个序数)是所有对于的极限;这在拓扑意义上对于序拓扑也是闭合的,(为了避免谈论在真类上的拓扑,你可能要求这个类与任何给定序数的交在序数的序拓扑上是闭合的,这再次是等价的)。

特别重要的序数类是闭合无界的。例如,所有极限序数的类是闭合且无界的:也就是說,总是有一个极限序数大于给定序数,而且极限序数的极限是极限序数。加法不可分解序数的类,序数的类,基数的类,都是闭合无界的;而正规基数的类是无界但不闭合的,序数的任何有限集合則是闭合但非无界的。

一个类是固定的,如果它与所有闭合无界类有非空交集。任何闭合无界类的超类都是固定的,並且固定类必然是无界的;但也有着不闭合的固定类,以及那些没有闭合无界子类的固定类(比如带有可数共尾性的所有极限序数的类)。因为两个闭合无界类的交集是闭合和无界的,所以固定类和闭合无界类的交集是固定的。但是两个固定类的交可以为空,比如带有共尾性ω的序数的类和带有不可数共尾性的序数的类。

與其考慮作適用於序數的(真)類的公式化定義,我们可以對在给定序数之下的序数的集合作公式化定義:极限序数的子集被称为是在之下无界的(或共尾的),假定小于的任何序数會小于在这个集合中的某个序数。更加一般的说,我们可以称任何序数的子集为共尾于,如果小于的所有序数會小于或等于在这个集合中的某个序数。稱这个子集下闭合,如果它对在内的序拓扑是闭合的,就是说,在这个集合中的序数的极限要么在这个集合中,要么等于自身。

序數算術

在序数上有三个常见运算:加法、乘法和(序数)指数。每个大致上都可以用两种不同的方式定义:要么构造一個明確的良序集合去表示這個運算,要么使用超限递归。康托尔范式提供了一個表示序数的标准方式。所谓的"自然"算术运算保持了交换律,但代价是损失了连续性。

序数与基数

基数的初始序数

每个序数都有一个关联的基数,就是通过简单的忘记次序而获得的它的。如果某良序集合的序类型就是該序數,那麼它們都會有相同的势。有给定基数作为它的势的最小序数,叫做这个势的初始序数。所有有限序数(自然数)是初始的,而絕多数无限序数都不是初始的。选择公理等价于声称所有集合都可以良序化,就是说所有基数都有一个初始序数。在这种情况下,传统上把基数等同为該初始序数,并称這個初始序数是一個基数。

第α个无限序数被写为。它的势被写为。例如,ω0 = ω的势为,它也是ω²或ε0(都是可数序数)的势。所以(假定选择公理)我们把ω等同於,除了记号用在写基数的时候,而ω用在写序数的时候(这一點很重要,因为)。还有,是最小的不可数序数(要看出其存在性,只需考虑由自然数的良序的等价类組成的集合:每个这樣的良序都定义了一个可数序数,然後是这个集合的序类型),是势大于的最小序数,以此类推,而对自然数n的极限(任何基数的极限是基数,所以这个极限实际上是在所有之后的第一个基数)。

共尾性

序数共尾性是作为的共尾子集的序类型的最小序数。注意一些作者只对极限序数定义或使用共尾性。序数或任何其他良序集合的集合的共尾性是这个集合的序类型的共尾性。

因此对于极限序数,存在着一個极限為-标定的严格递增序列。例如,ω²的共尾性是ω,因为序列ω·m(这裡的m在自然数上取值)趋向于ω²;但是,更加一般的说,任何可数极限序数都有共尾性ω。一個不可数的极限序数可以有要么同一样的共尾性ω,要么有不可数共尾性。

0的共尾性是0。任何后继序数的共尾性是1。任何极限序数的共尾性至少是

等于其共尾性的序数叫做正规的,并且它总是初始序数。任何正规序数的极限都是初始序数的极限,因而也是初始的,即使它不是正规的(它通常不是)。如果有选择公理,则对于每个α,都是正规的。在这种情况下,序数0, 1, , ,和都是正规的,而2, 3, ,和ωω·2是非正规的初始序数。

任何序数α的共尾性都是正规序数,就是说α的共尾性的共尾性等同于α的共尾性。所以共尾性运算是等幂的。

某些“大的”可数序数

我们已经提及了(参见康托尔范式)序数艾普塞朗數ε0,它是满足等式的最小序數,所以它是序列0, 1, , , ,等的极限。很多序数可以用特定序数函数的不动点的方式定义(如果使得的第个序数叫做,则我们總可以继续尝试找到使得的第个序数,“以此类推”,但微妙在于“以此类推”)。我们可以尝试有系统的这么做,而不管用什么系统来定义和构造序数,总是有一个序数正好位于这个系统所构造的所有序数之上。也許以这种构造系统的方式限定的最重要的序数是邱奇-克莱尼序数(儘管名字中有,这个序数是可数的),它是不能以可计算函数表示的最小序数。不過,還是可以在之下定义相当大的序数,它們有的標誌著特定形式系统的“证明论強度”(例如,標誌著皮亚诺算术的強度)。也可以在邱奇-克莱尼序数之上定义更大的序数,這些大序數會在逻辑的多个部分有研究价值。

参见

参考资料

  • Conway, J. H. and Guy, R. K. "Cantor's Ordinal Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 266-267 and 274, 1996.
  • Sierpiński, W. (1965). Cardinal and Ordinal Numbers (2nd ed.). Warszawa: Państwowe Wydawnictwo Naukowe. Also defines ordinal operations in terms of the Cantor Normal Form.
  • Patrick Suppes, Axiomatic Set Theory, D.Van Nostrand Company Inc., 1960

站外链接