请读者具备离散数学的基础
二、序数
定义自然数集N
后继：\(x^+=x∪\{x\}\)称为\(x\)的后继
自然数的定义如下
\(0=Ø\)
\(1=0^+=\{0\}\)
\(2=1^+=\{0,1\}\)
...
\(N=(N-1)^+=\{0,1,...,N-1\}\)
初始情况为空集，由递推关系得到了自然数集N
其中的元素称为是自然数
自然数定义：
(1)0是自然数
(2)若\(n\)是自然数，则\(n^+\)也是自然数
对于自然数集可以发现另外的性质
(1)\(0∈1∈2∈3...\)，从元素来看小自然数元素属于大自然数的集合
(2)\(0⊆1⊆2⊆3...\)，从集合来看小自然数集合是大自然数集合的子集
所谓公理化就是严格定义，但到目前为之没有一个原则定义像自然数这样的无穷集合
因此引出下面的原则
无穷集合存在原则
无穷集合存在原则：所有自然数形成的是集合，表述为\(0∈N~∧~∀y∈N(y^+∈N)\)即自然数集是由0、任意元素以及任意元素的后继所组成
从自然数集合的定义出发抽象出了一类集合——归纳集合
归纳集合\(s\)满足条件
(1)\(0∈s\)
(2)\(∀x∈s(x^+∈s)\)
从无穷集合存在原则来看，后继运算是封闭的，即使加上后继依然是集合
推广无穷集合存在原则：一定存在着归纳集合，用公式表述为\(0∈s~∧~∀y∈s(y^+∈s)\)
归纳定理（数学归纳法）
定理1：若集合\(ω\)是归纳的，那么对于所有一切的集合\(s\)，若\(s\)是归纳集合，那么\(ω⊆s\)
该定理说明了特殊的归纳集合如自然数集与推广后任意的归纳集合之间的关系，如自然数集是特殊的归纳集合
该证明特别简单，只要证明\(ω\)也是\(s\)的元素即可
N归纳定理：若\(T⊆N\)且\(T\)为归纳集合，则\(T=N\)
从定理1附加上外延原则即可证明，表明任意自然数集合的归纳子集都是等价于自身的
因为归纳集合是无穷的，好比无穷±100还是无穷
数学归纳法证明：
定义集合\(T=\{n~|~n∈N~∧~A(n)\}\)（\(A(n)\)表明是其子集）
要证明集合相等另外一种方法是证明每个元素都在两个集合中
【1-初始】其中子集\(0∈T,0∈N\)证明了第一个元素的情况
【2-假设】假设某自然数后继\(k^+∈T,k^+∈N\)
【3-判断】那么可以得到\(k∈T,k∈N\)
（因为除0以外的任意自然数必定为某一个自然数的后继）
由此完成了证明，这种证明方法称为是数学归纳法
皮亚诺(Peano)自然数公理系统
Peano公理系统简记为\(<N,y^+,0>\)，通过集合论严格定义了自然数应该怎样的，以及加减乘除等运算是如何具体实现的，这些内容你看着会非常熟悉，但定义却完全不同
①\(∀x∈N(x^+≠0)\)
解释：任意自然数可推得其后继不是0
例子：如150的后继是151不会是0
这个定义看上去很奇怪，但这些都是形式化，150这些只是符号而已，不代表其具体意义
比如你可以自己定义'150'实际代表∞，'151'实际代表0
该定义严格定义了符号应该是符合直觉的
比如布尔01二进制的数学系统中，由于其有限性，1的后继是0
②\(∀x∈N~~∀y∈N(x^+=y^+→x=y)\)
解释：如果两自然数后继相等，那么两自然数相等
例子：如x、y的下一个自然数都是100，那么x=y=99
该定义确定了自然数的线性的，如果没有这条
那么你是可以定义'100'、'150'的下一个自然数是151
这样结构就不再是线性的
③有一任意公式\(A(x)\)，\(A(0)~∧~∀x∈N(A(x)→A(x^+))→∀x∈NA(x)\)
该定义是N归纳原则的另一形式，表明了公式在N上如何运作
一方面表明必须能满足0，另一方面必须能从任意元素推得其后继也满足
N的传递性
传递集合定义：某一集合\(s\)满足\(∀x∀y(x∈y~∧~y∈s→x∈s)\)即\(s=\{x~|~∀y(x∈y~∧y∈s~)\}\)则称为传递集合
(1)根据定义s是传递集合，当且仅当\(∪s⊆s\)（可以看成是基于并集合条件更严格的集合）
该定理表明并集合是传递集合的子集
如\(s=\{0,1,2\}\)，\(∪s=\{0,1\}\)
(2)传递集合与以下等价
■\(∀x∈s(x⊆s)\)
■\(s⊆P(s)\)
这一点实际上是对定理一的变换，可以很简单地将等价形式转换成定义形式
第一个形式可以直接等价推得第二个形式
证明：
这里用第一个进行形式证明
\(∀x∈s(x⊆s)⇔∀x∀y(x∈s→(y∈x→y∈s))\)
\(⇔∀x∀y(x∉s~∨~y∉x~∨~y∈s)\)
\(⇔∀x∀y(y∈x~∧~x∈s→y∈s)\)
调换x、y会发现就是定义的形式
结合定理一可推出\(∪s⊆s\)当且仅当\(s⊆P(s)\)
(3)对于任意的传递集合s有\(∪s^+=s\)（证明简单,略）
(4)每一自然数都是传递集合
证明：
假设任意自然数\(k=\{k-1,k-2,..,0\}\)
其中\(∪k=\{k-2,k-3,...,0\}⊆k\)
所以单个自然数一定是一传递集合
该性质表明了自然数具有传递性
(5)根据定理4的证明过程还可以得到性质一个自然数k有\(∪k^+=k\)
(6)自然数若\(m^+=n^+\)则\(m=n\)（皮亚诺自然数公理系统第二条）
该性质体现了自然数的传递性即自然数是线性的
(7)N是传递集合
N是由自然数所组成的集合，构成的整体也是传递集合，可以采用数学归纳证明，这里不再证明
此定理说明了N不仅是归纳集合还是传递集合
(8)若x是传递集合，则\(x^+\)也是传递集合
该性质是定理4、定理5的推广形式，即一个传递集合可以通过后继的运算方式来形成大量的传递集合（像是延伸出道路一样）
证明：
\(∵x^+=x∪\{x\}\)
\(∴∪x^+=∪∪\{x,\{x\}\}=x\)
\(∵x⊆x^+\)
\(∴x^+⊆x^+\)
(9)\(P(x)\)是传递集合，当且仅当x是传递集合（根据定理2可直接证明得到）
必要性证明：
\(∵∪x⊆x⊆P(x),∪P(x)=x,P(x)⊆P(P(x))\)
\(∴∪P(x)⊆P(P(x))\)
充分性证明：
\(∵∪P(x)⊆P(x)⊆P(P(x))\)
\(∴x⊆P(x)\)
(10)若x为传递集合，或x可能不是传递集合但其所有元素都是传递集合，则\(∪x\)也是传递集合
证明也比较简单，略
[总结]
传递集合的引入一方面是探讨了N的传递性，另一方面是表明了传递集合、并集合、幂集合之间的包含关系
N的三歧性
三歧性指\(∀m,n∈N\)必定有以下三种情况之一
(1)\(n∈m→n<m\)
(2)\(n=m→n=m\)
(3)\(m∈n→n>m\)
关系基本性质
在关系中有自反性、对称性、传递性三个最基本的性质
上述讲述了自然数集的情况下在传递性、三歧性方面的特征
假设有在A上的关系F，记作\(<A,F>\)
为了方便理解，这里设\(A=\{2,3,4,5\}\)
即有4个游离的元素
关系即某个元素到某个元素，在可视化当中称为图论用线表示关系
已知关系R
(1)自反性：\(∀i∈A(iRi)\)（这里用粗线框表示自身到自身的关系，称为自环，即所有元素都有自环）
(2)反自反性：\(∀i∈A(i \not R i)\)即不存在自环
(3)非自反性：\(￢∀i∈A(iRi)\)即\(∃i∈A~∧~i\not Ri\)
备注：加“反”的为其逆命题，加“非”的为其否命题
(4)对称性：\(∀i,j∈A(iRj→jRi)\)
即任意边是双向的
(5)反对称性：\(∀i,j∈A∧i≠j(iRj \not →jRi)\)
即任意边是单向的，但对于自身到自身的情况不作约束
(6)严格反对称性：\(∀i,j∈A(iRj \not →jRi)\)
与上面的反对称性不同，此性质蕴含了反自反性，即不能有自环
(7)非对称性：\(￢∀i,j∈A(iRj→jRi)\)即\(∃i,j∈A~∧~iRj~∧~j \not R i\)
(8)传递性：\(∀i,j,k∈A(iRj~∧~jRk~→~iRk)\)
(9)反传递性：\(∀i,j,k∈A(iRj~∧~jRk~\not →~iRk)\)
(10)非传递性：\(￢∀i,j,k∈A(iRj~∧~jRk~→~iRk)\)
(11)完备性：\(∀a,b∈X(aRb~∨~bRa)\)，又称为完全性或可比性，表明任意元素之间必须存在关系，蕴含了自反性
(12)三歧性：三歧性是建立在完备性的基础上，完备性表明了任意元素之间必须存在关系，但并没有限定这个关系是有一个还是有两个，因此引出三歧性，是指任意元素之间存在关系但只能有一个
其中三歧性蕴含了自反性、反对称性
(13)预序性：若具有自反性、传递性则称为具有预序性
(14)拟序性：若具有反自反性、传递性则称为具有拟序性
(15)偏序性：偏序性分为非严格偏序、严格偏序。(非严格)偏序是指具有预序性、反对称性的性质，严格偏序是指具有拟序性、非对称性的性质
严格偏序性
非严格偏序
(16)(非严格)全序性：若具有偏序性、完全性则称为具有全序性（也称为线序性），即具有自反性、反对称性、传递性、完全性
(17)严格全序性：若具有偏序性、三歧性则称为具有严格全序性，即具有自反性、反对称性、传递性、三歧性
(18)等价性：若具有自反性、对称性、传递性则称为具有等价性
[总结以及部分性质的直观差异]
其中自反性、对称性、传递性为基础，完备性之上引出了三歧性，其后引出拟序性、预序性，然后引出偏序性，最后引出了全序性
其中我分为以下这几个方面讨论这些性质之间的差异
■是否有环：即自反性，表明关系对自身到自身而言是否有关系
■是否对称：即对称性，表明关系的有序列是否可交换
■是否完备：即完备性，在元素间关系可能完全有也可能没有，表明了是否完全有关系
■是否唯一：元素之间虽然可能有关系，但其关系是否唯一，如\(gcd(b,a)=gcd(a,b)\)因为对称性的存在导致a元素和b元素有两个关系。三歧性蕴含了反对称性和自反性
■是否整体：从整体上看，其关系组成的图可能是分块的。如等价性因为可以分块引出了等价类的概念，但有些性质很好地保证了整体性即无法分块
■是否树形：元素间关系可能是复杂的，学过图论知道复杂的图是难以处理的，而树结构是更容易处理的。这里引入哈斯图概念，哈斯图首先要满足偏序性，哈斯图可以很好呈现其关系的路径。换一种等价说法就是是否能形成环，如果不能形成环就是树形的
■是否线性：即使是树结构也是较难处理的，但更加特殊的线性那么是最容易处理的
备注：
打√表示满足，打?表示可能满足或部分满足，打×表示完全不满足（如对是否有环打×表明无环是反自反性的），附有*的表示我认为是其核心影响
其中性质分成了三类：是否有环、是否对称是最基础的一类，是否完备、是否唯一是描述元素间关系的一类，是否分块是描述是否为整体性自成一类，是否树形、是否线性用于描述其某一块图形形态的一类
| 性质 | 是否有环 | 是否对称 | 是否完备 | 是否唯一 | 是否整体 | 是否树形 | 是否线性 |
|---|---|---|---|---|---|---|---|
| 完备性 | √ | ? | √ | ? | √* | ? | ? |
| 三歧性 | √ | × | √ | √* | √ | ? | ? |
| 拟序性 | ×* | ? | ? | ? | ? | ? | ? |
| 预序性 | √* | ? | ? | ? | ? | ? | ? |
| 严格偏序性 | × | ? | ? | ? | ? | ? | ? |
| 偏序性 | √ | ×* | ? | ？ | ? | ? | ? |
| 全序性 | √ | × | √* | ? | √* | ? | ? |
| 严格全序性 | √ | × | √ | √* | √ | √* | ? |
| 良序性 | √ | × | √ | √ | √ | √ | √ |
从上图得出以下结论
(1)完备性约束了关系的图必须是不可分块的
(2)三歧性约束了元素间关系必须是唯一的
(3)拟序性和预序性主要约束在对称性上
(4)严格偏序性在对称性上并不是那么绝对，而偏序性的性质更加优良
(5)全序性是建立在偏序性之上的，由于具有完备性导致其是不可分块的
(6)严格全序性是在其完备性的基础上变成了三歧性，因此其图就是一颗树
(7)良序性是后续要讨论的，良序性还保证这棵树是特殊的即一条线，由此从简单性质通过逐步限制变成了最简单的情况
(8)等价性是另外一类性质，很经典的例子就是求余运算本质上是划分等价类
为了方便理解，我给出了下列图来说明性质是如何从复杂变到简单的，变简单是为了容易讨论，变复杂是为了站在更抽象的角度看待问题
图1：偏序性，可以分块而且形态任意
哈斯图形式
图2：全序性，必须是整体的，但形态依然复杂
哈斯图形式
图3：严格全序性，形态简化成必须是树形的
由于不是采用哈斯图，导致看上去非常复杂，实际上是更加简化了，从0开始分叉到1、a、A
哈斯图形式
图4：良序性，形态呈现为最简单的线性
哈斯图形式
序数ω
上面讨论了大量的关系性质，这一目的是为了引出一个概念——排序
排序是非常常见的操作，你会发现良序性的哈斯图是线性的恰好是顺序关系
这些关系性质为实际操作提供了理论基础
自然数在属于关系上具备了良序性\(0∈1∈2∈3...\)，但会发现这种定义局限了
自然数它只局限于数字本身，但排序可能会有小数，而且也会有\(a,b,c,d\)等非数字的
因此从自然数出发去推广了一个新的概念——序数
序数是更加抽象的概念，它建立于自然数之上，它具有排序操作的潜力，但最多只具备严格全序性，它可能并不具备良序性（后续会说明）
编程会遇到比较操作，任何字符串甚至汉字是可以比较的，其理论因为编码集是序数的集合，它具有排序操作即比较操作的潜力
序数定义
(1)0是序数
(2)若a是序数，则\(a^+\)为序数，\(a^+\)也称为后继序数
(3)若s是序数的集合，则\(∪s\)为序数，\(∪s\)也称为极限序数
(4)任意序数均可由(1)(2)(3)得到
本质上就是多了个并集合运算，但提供了无限的扩展性
比如我可以定义\(A=∪\{65,66\},B=∪\{66,67\}\)，虽然运算后\(A=65,B=66\)结果是个自然数，但定义却有所不同了，并集你可以随意扩展其元素，我还可以定义\(我=∪\{64,65,66\}\)，运算结果是一样的，但定义是不同的，这样的定义提供了扩展性去定义各种需要排序的元素实现从任意元素到自然数的映射
序数的性质
(1)任意自然数k是序数，自然数集N也是序数
(2)定义常见运算：
已知\(∀m,n∈N\)
\(m+n=m^{\overbrace{++...+}^{n个}}\)
\(mn=∑^nm\)
\(m^n=∏^nm\)
备注：通过集合论的观点看待运算可以得到些不同的思路
如\(3+2=∪\{5\}=\{0,1,2,3,4\}=5\)
(3)序数一定是集合，这个由定义以及各个原则可以证明
(4)序数是对N的推广，本质上也具有属于关系上的传递性、三歧性
证明序数具有传递性：
要具有传递性即证\(∪ω⊆ω⊆P(ω)\)
序数本质上是提供了并集合运算，但并集合运算和后继运算相互转换，如\(∪\{4,5\}=6\)
可以发现并集合具有这样的性质：\(∪\{n_1,n_2,...,n_m\}=max\{n_1,n_2,...,n_m\}\)
而该性质说明了序数→某自然数的等价形式
证明如下：
首先证明弱形式的情况，即序数都是由自然数组成的
设\(ω=∪\{n_1,n_2,...,n_m\}\)，其中任意元素\(n_i\)都是自然数
其中在\(n_1,n_2,...n_m\)中设\(n_{max(1)},n_{max(2)},...,n_{max(k)}\)是k个最大(可能有多个相同)的一组数，假设该最大自然数为\(Max\)
根据自然数的三歧性以及性质可以得到
\(∀i~(n_i∈\{n_1,n_2,...,n_m\}~∧~n_i≠Max→n_i<Max→n_i⊆Max)\)
设\(k_1=\{n_1,n_2,...,n_m\}-Max\),\(∀i(k_i=\{n_1,n_2,...,n_m\}-Max-∑^{i-1}_{j=1}k_j)\)
\(∵k_i⊆Max\)→\(Max∪k_i=Max\)
\(∴∪\{n_1,n_2,...,n_m\}=Max∪k_1∪k_2∪...∪k_l=Max\)
该形式为弱形式，因为序数本身也可以包含序数，但序数拆分到最后本质上由自然数组成的，这属于递归形式的证明，鉴于博主水平只能给出弱形式即序数由自然数组成的情况下的证明
根据定义序数有后继运算、并集合运算两种方式从自然数0导出，但后继运算根据定义本质上也是并集合运算，因此可以设序数是一个多个自然数或序数的并集合
假设有一序数\(ω\)不管其是如何定义，都可以等价某一自然数\(i\)
问题就变成了\(∪i⊆i⊆P(i)\)也就是怎么证明自然数具有传递性
该内容在【N的传递性】中已经证明，于是证得序数也具有传递性
证明序数具有三歧性：
要具有三歧性即证\(∀x∀y\)满足\(x=y\)或\(x∈y\)或\(y∈x\)中的一个
上面并没有证明自然数具有三歧性，这里进行补充
三歧性是完备性的限制，可以先去证明完备性在去证明三歧性
完备性简单说明：
根据证明传递性中新得到的结论，任意元素最后都可以转成自然数，任意自然数当然存在属于关系，因此一定具有完备性
得到了完备性就可以去证明三歧性
这里使用奇异集合的观点去证明
假设\(∃x∃y(x=y~∧~x∈y)\)、\(∃x∃y(x=y~∧~y∈x)\)或\(∃x∃y(x∈y~∧~y∈x)\)都是无法成立的，如果成立那就是不可能的奇异集合了。因此对于任意集合在属于关系上只要有完备性就一定有三歧性
最大元：\(∃y∈ω~∀x∈ω~(x≠y→x<y)\)则称y是最大元
最小元：\(∃y∈ω~∀x∈ω~(x≠y→x<y)\)则称y是最小元
一个序数可能具有最大元可能具有最小元
冯诺依曼序数
1925年，冯诺依曼（就是做第一台计算机的那个）提出了序数定义，与之前对序数的定义不同，它更加简单且指出了核心性质，这样的序数称为冯诺依曼序数
定义：具有∈三歧性的传递集合就是序数
(1)什么是∈三歧性？
因为之前说明了自然数、序数都具有传递性、三歧性，但是并没有说明是在什么关系上具有三歧性，因此∈三歧性补充说明了是在属于关系上的。也可以说一个关系R具有R xx性之类的
(2)两个序数定义的概念是否等价？
可以从序数概念推得序数具有传递性、三歧性，即序数就是冯诺依曼序数
但反过来冯诺依曼序数是否为序数？
证明：
从冯诺依曼序数出发要去证明是否为序数，假设冯诺依曼序数不是序数
设冯诺伊曼序数\(x\)不是序数，冯诺依曼序数并没在定义上提供运算可以计算其后继
令后继\(s=\{y~|~y∈x^+，y是冯诺依曼序数但不是序数\}\)
\(∵x∈s\)
\(∴s≠Ø\)
但根据存在极小元原则
\(∃Min∈s~∧~Min∩s=Ø\)
显然有\(Min≠Ø\)
\(∵Min\)是\(s\)的元素假定了是冯诺依曼序数而不是序数
根据其∈三歧性得到\(∀y∈Min∃z∈x(F(y∈z,y=z,z∈y)),F(x,y,z)\)表示只能满足其中一个
但是不管根据哪种形式都可以推得\(Min\)是序数，如满足\(y∈z\)那么可以得到\(Min∈z\)，\(z\)是序数所以\(Min\)也是序数，因此矛盾
从而证明所谓的冯诺依曼序数就是之前的序数
序数的形式化定义
冯诺依曼序数采用了更简洁的定义，只要集合满足传递性和∈完备性即可说明是序数
这里采用形式化的定义
定义公式\(On(x):∀y∀z(z∈y∧y∈x→z∈x)∧∀y∈x∀z∈x(y∈z∨y=z∨z∈y)\)
On公式前半部分为传递性，后半部分为∈完备性（也称为∈连接性）
通过这样形式化定义后可以这样定义序数，\(x\)为集合，若\(On(x)≡true\)则\(x\)为序数
Burali-Forti悖论(1897)
这个悖论的提出要早于罗素悖论，但远远没有罗素悖论知名
它的内容是局限在了序数这一概念，但如果推广其本质和罗素悖论一样
内容：
(1)令\(On=\{x~|~On(x)\}\)，则\(On\)为真类
(2)\(On^+∈On,On∈On\)
说明：
根据定义上来说只要满足公式的一定是序数，序数的并运算后依然是序数，即On一定是序数（集合），但它却是真类，因此产生了矛盾
证明1：
假设\(On\)是序数
那么\(On(On)\)必然成立，即\(On\)也是\(On\)的元素
\(∴On∈On\)（参考奇异集合）
因此必定是真类
证明2：
\(On^+=On∪\{On\}\)
根据定义化简得\(On^+=\{x~|~On(x)\}∪\{On\}=On\)
即On及其后继都是等价的，因此必然有\(On^+∈On\)这样的奇怪性质
简单说明：
On的定义用通俗话来说就是它是任何一切序数的类，因此它的元素数是无穷多的，那么无穷的后继当然是等价于无穷的，但是无穷导出了真类而非序数
修正：
一般常用希腊字母\(α,β,γ\)等表示序数
\(∃αA(α)\)表示\(∃x(On(x)∧A(x))\)
\(∀αA(α)\)表示\(∀x(On(x)→A(x))\)（A(x)为任意公式）
罗素悖论采用了子集去导出集合而避免真类，该悖论通过On(x)去导出序数而避免真类
三类序数以及自然数集的形式化定义
在最初序数的定义中，将序数分成了三类：0、后继序数、极限序数
这里采用形式化的定义去描述
(1)后继序数：\(Succ(α)=∃β∈α(α=β∪\{β\})\)
(2)极限序数：\(lim(α)=∀β∈α∃γ∈α(β∈γ)\)
(3)自然数集：N是极限序数，\(N=\{x~|~On(x)∧lim(x)∧x≠0∧∀y∈x(y≠0→Succ(y))\}=Fli(x)\)该定义过于冗长采用\(Fli(x)\)简单表示自然数。首先On(x)是避免悖论，lim(x)是因为N是极限序数，最后一个式子表明自然数本质上是通过导出后继序数得到的
其他特殊元素
(1)后继：略
(2)前节：对于任意序数α，若\(∀β~Sec(β)=\{γ~|~γ∈β\}\)则称β是α的前节
在序数关系上使用后继、前节描述之间的关系，也可以用日常所用的＞、＜、＝、≠、≥、≤去描述。所谓后继就是严格位于其后面1个位置的元素，前节写成\(∀β~Sec(β)=\{γ~|~γ＜β\}\)就能理解了
| 符号 | 等价的形式 |
|---|---|
| α>β | β∈α |
| α<β | α∈β |
| α=β | α⊆β∧β⊆α |
| α≠β | β⊄α∨β⊄α |
| α≥β | β⊆α |
| α≤β | α⊆β |
(3)最大元：若\(∀α∈s∃β∈s(α≤β)\)则称β为最大元
(4)最小元：若\(∀α∈s∃β∈s(α≥β)\)则称β为最小元，最大元最小元就是最值，只不过站在了更抽象的角度去描述
性质：
■若\(α∈s\)为最大元，则\(∪s=α\)（求解最大值的方法）
■若\(β∈s\)为最小元，则\(∩s=β\)（求解最小值的方法）
其实和程序求解没两样，但是引出了另一个思想：假设第一个变量是最值的思想太绕，换个角度想其实是逐位加进来求解并集/交集，不断将新元素加入已求解的并集/交集，当所有元素加入到并集/交集后即求解了最值
■若序数集合\(s\)中不存在最大元且\(s≠Ø\)，则\(∪s\)必定为极限序数（判定是否为极限序数）
证明：
\(∵s≠Ø\)
因为序数要么是空集要么后继序数要么极限序数，这里假设\(∪s\)是后继序数
那么\(∃α→∪s=α^+\)，\(∴α∈∪s\)
\(∴∀β∈α∈∪s\)
\(∴∪s\)的最大元为\(α\)
与条件矛盾，因此不可能为后继序数即必定为极限序数
换成人话就是假设是后续序数去反证有最大元，因为是后继序数必定有前面的一个序数（类型任意），那么一定有前面的序数中任意的元素是在其中的→也在后继序数中，因此证明了有最大元
(5)最小上界（上确界）：若\(∀α,∀β∈s(β≤α)\)则称\(∩α\)是s的最小上界，记作\(∩α=Sup(s)\)。最小上界是最大元的超集，比如\(\{1,2,3,3,4,Ⅴ,5\}\)其中上确界\(Sup(x)=\{Ⅴ,5\}\)，而最大元是任意的一个5或Ⅴ（元素不能相同但是不同序数其值是可以相同的）。简单来说上确界就是最大元的集合，只有最大元唯一时上确界只有唯一元素，同理还有最大下界（下确界）读者应该能猜出定义这里不过多说明（下确界记作\(Inf(s)\)）
备注：最小上界的准确含义是指所有上界（即定义中所有满足条件的\(α\)）的最小元（即做交集操作）
根据上确界或是下确界可以去定义【最值的唯一性】
■特殊情况：但是当不存在最大元时，也是有最小上界的
\(Sup(x)=\begin{cases}∪x，x不存在最大元 \\ \{∪x\}^+，其他情况 \end{cases}\)
该公式只讨论了值，具体细节还需要看定义，比如上一例\(Sup(x)=\{V,5\}=6\)只看公式的话就忽略了中间过程
■序数是自然数，当且仅当序数的非空元素都有最大元（即每一非0元素都有最大元）
超穷归纳法
N归纳定理是在自然数范畴下的归纳方法，在这里拓展至序数范畴
最小序数存在定理：若有任意公式\(A(x)\)存在序数使得公式成立，则存在最小元α使得\(A(α)\)成立
超穷归纳法
\(A(0)∧∀α(A(α)→A(α^+))∧∀α(lim(α)∧∀β∈αA(β)→A(α))→∀αA(α)\)
上面的形式等价于下面
\(∀α(∀β∈αA(β)→A(α))→∀αA(α)\)
在自然数范畴下的归纳法是限定了初始情况以及后继，而超穷归纳法额外增加了极限序数的情况
即后继成立的前提是前节成立（前节是后继的元素），在超穷归纳法下也就是任意集合的子元素必须成立，其中包含了后继序数、极限序数两种情况
序数加法
加法基本定义
这三条分别陈述了0、后继序数、极限序数的三种情况
■\(α+0=α\)
■\(α+β^+=(α+β)^+\)（这里用\(β^+\)是强调\(α\)加的是后继序数）
■\(α+γ=∪\{α+β~|~β＜γ\}\)（其中\(γ\)为极限序数\(lim(γ)\)）
因为序数上的运算与平常的运算稍抽象，因此这里不方便给极限序数的例子
但是0和后继序数就是小学里学到的
\(5+3^+=(5+3)^+=9\)
由上述式子可以推导出一般意义上的加法
■\(α+β=α∪∪\{(a+γ)^+~|~γ<β\}=α∪\{a+γ~|~γ<β\}\)
对于这种定论需要使用超穷归纳法来证明，和普通归纳法相比就是多了个极限序数的情况
(1)首先是证明0的情况
假设\(β=0\)，则\(α+0=α∪\{α+γ~|~γ＜0\}\)
因为在序数范畴里不可能有比0更小的，所以后边为空集即\(α+0=α\)
符合第一个定义
(2)然后是证明后继序数的情况
即假设\(β^+\)，\(α+β^+=α∪∪\{(a+γ)^+~|~γ<β^+\}\)
因为\(β^+\)是后继序数，所以比\(β^+\)小的就是0,1,2... ,β-1,β
即\(α+β^+=α∪∪\{(α+γ)^+~|~γ＜β^+\}=(α+β)^+=α+β^+\)
符合第二个定义
(3)极限序数的情况
假设\(lim(β)\),则\(α+β=α∪\{α+γ~|~γ＜β\}\)
＜本质上是属于关系，这里换成属于会更容易理解
即\(α+β=α∪\{α+γ~|~γ∈β\}=∪\{α+γ~|~γ∈β\}\)
符合第三个定义
因此该结论成立
序数加法的性质
吸收：在实际的序数运算中可能会出现重复元素的情况，若\(α+β=β\)则称为β吸收了α
如果只是局限于自然数的话只能解决为什么1+1=2的问题
但是在序数观点下自然数集也是极限序数，即自然数集也可以做加法
(1)\(N+n=N(n∈N)\)（自然数集具有吸收自然数的性质）
(2)\(N+N=N∪\{N+γ~|~γ＜N\}=N+N\)（自然数集不可加）
二元运算（抽象）：加法本质上是二元运算，即可以抽象为\(τ(x,y)=x+y\)
二元运算这里不会过多说明，但是从二元运算可以讨论许多性质（在一般的范畴下难以讨论，需要这样抽象）
(3)交换性：若\(τ(x,y)=τ(y,x)\)，则称为该运算具有交换性，加法具有此性质
(3)左递增性：若\(x<y\)，\(∀z~τ(x,z)<τ(y,z)\)，在自然数范畴下的加法有此性质，但如果扩展到序数则不具有此性质，如\(N+2=N+3\)
(4)结合律：\((α+β)+γ=α+(β+γ)\)
(5)若\(α+β=α+γ\)，则\(β=γ\)
(6)若\(α+β<α+γ\)，则\(β<γ\)
(7)若\(α<β\)，则\(α+γ≤β+γ\)
序数乘法
定义
■\(α×0=0\)
■\(α×β^+=(α×β)+α\)
■\(α×γ=∪_{β<γ}(α×β)\)（\(lim(γ)\)）
可以发现乘法的定义本质上是基于加法的递归，同样有一个通用的公式
\(α×β=∪\{α×γ+α~|~γ<β\}=\{α×γ+θ~|~γ＜β~∧~θ<α\}\)
同样是用超穷归纳法证明，这里不再说明
序数乘法的性质
(1)结合律：\((α×β)×γ=α×(β×γ)\)
(2)交换律：\(α×β=β×α\)
(3)\(α×β<α×γ\)，当且仅当\(β<γ~∧~α≠0\)
(4)\(α×β=α×γ\)，则\(β=γ~∨~α=0\)
(5)\(α<β\)，则\(α×γ≤β×γ\)
(6)\(α×γ<β×γ\)，则\(α<β\)
序数幂乘
乘法是从加法来的，而幂乘则是由乘法来的
同样根据不同序数有三个定义
■\(α^0=1\)
■\(α^{β^+}=α^β×α\)
■\(α^γ=∪_{}\)
通用公式：\(α^β=1∪∪\{a^γ×α~|~γ<β\}\)
良序关系初步认识
之前有说过良序性，良序性是在直观感受上最简单的性质，满足了排序的要求
这里给出良序性的定义
(1)若集合s的任意非空子集u均满足\(∃x∈u~∧~∀y∈u(y \not Rx)\)则称s在R上具有良序性
(2)序数R具有三歧性、传递性简称是具有全序关系，如果还具有良序性那么就称是具有良序关系
解释：这个定义是来自于最小元，即任意子集如果都有最小元那么就称是有良序性的
很简单的一个例子，如下哈斯图，其中子集\(u=\{2,two\}\)可以发现分叉的（一对多）必然会导致某些子集不存在最小元，因此良序性在直观感受上代表了一对一的线性
至于定义中如何去理解描述的是最小元的含义，我写成这样
\(y \not R x\)实际缩写了\(<y,x>∉R\)，而由于良序性是针对任意关系的，因此抽象成了R
但如果放小只纠结于属于关系，即如果R是代表属于关系的话相当于\(y∉x\)
\(y∈x\)等同于\(y<x\)，那么不属于就是相反即\(x≤y\)结合最小元的定义就不难理解了
进一步抽象后将\(<s,R>\)称为良序结构（其中s称为良序集合）
自然数集是良序的，很早之前就说过在属于关系上满足一种\(0∈1∈2...\)的特殊性质，即有\(<N,∈>\)的良序结构
序数不一定具有良序性是因为可以一对多
良序关系的性质
(1)任一在关系R上的良序集合的子集也具有在R上的良序性
(2)已知良序结构\(<s,R>\)，则\(fld(R)=s\)
(3)关系R的x前节：已知良序结构\(<s,R>\)，则\(O_R(x)=\{y~|~yRx~∧~y∈s\}\)称为关系R的x前节。
比如已知\(<N,∈>\)，那么\(O_R(3)=\{0,1,2\}\)，就实际效果而言和序数下的前节差不多，但是没有一对多，也就是真正体现了排序的性质
(4)保序性：是基于良序描述函数的一个性质。有两个良序结构\(<s,R1>,<u,R2>\)，有一函数\(f:s→u\)。若\(∀x,y∈s\)均有\(xR1y→f(x)R2f(y)\)，则称函数\(f\)是具有保序性的
保序性可以简单理解为某个良序集合经过某一具有保序性的映射后依然维持原来的排序情况
如已知\(1,2,3,4,5\)经过乘二的映射依然保持原来的排列\(2,4,6,8,10\)
(5)有一良序集合S，若\(T⊆s\)，则\(Sup(T)\)为\(S-T\)的最小元。特别地\(Sup(Ø)\)是\(S\)的最小元
(6)显然上一条在s中是不可能存在\(Sup(s)\)的，那么\(s1=s∪\{Sup(s)\}\)则称为是s的良序延拓
(7)好的映射：若有一保序的双射f，若是从一良序集合映射到另一良序集合某一前节，则称为是一好的映射
这种特殊的映射实质上是一种标排序序号的行为，保序性保证了顺序上不会发生变化，映射到前节实质上是保证映射后元素间是紧挨相邻的，比如有\(\{a,b,c,..,z\}\)可以映射到\(\{1,2,3,...,26\}\)（元素是紧挨相邻的，且根据定义第一个元素映射后值必定为自然数0或与0的值相等的符号）
而且这种特殊的映射还有固定的计算公式
(8)若有良序集合s,u，则必然存在唯一的好的映射\(f:s→u\)，\(ran(f)=\{x~|~∃y∈s(x∈Sec(y))∧x∈u\}\)，\(f(x)=Sup\{f(Sec(y))~|~Sec(y)<x\}\)，也存在唯一的好的映射\(g:u→s\)，\(ran(g)=\{x~|~∃y∈u(x∈Sec(y))∧x∈s\}\)（证明较复杂，略）
(9)由上一条还可推得，\(f=g^{-1}\)即之间的好的映射是互逆的（根据双射可得\(ran(f)=u\)即可证）
(10)同构映射：已知良序结构\(<s1,R1>,<s2,R2>\)若存在好的映射\(f:s1→s2\)，\(s2=ran(f)\)则称\(f\)是两个良序结构间的同构映射（同构在良序结构中可直接理解为保序性），简称两良序集合同构，简记为\(Iso(s1,s2,R1,R2)\)或\(Iso(s1,s2)\)，同理其逆映射也为同构映射
(11)若有良序结构\(<s,R>\)，则存在唯一的序数\(α\)使得存在\(Iso(s,α,R,∈)\)（可理解为数组的值与下标的关系）
基于此定理和自然数的公理可以构造出其他的数，比如整数可以是序列\(<1,2,3...-1,-2...0>\)实质上是和序数\(2*N+1\)同构的
备注：康托尔曾定义序数实质上是良序集合的序型，但序型是什么是非常模糊的，可以简单理解为集合元素的数量（类似于基数的概念）
总结
从自然数以及关系的一些性质上引出了Peano公理系统，以及拓展出了序数的概念。序数代表了一种特殊的元素且支持一些常见但又特殊的运算方式，最后序数如同1，2，3可以表示数量即引出基数的概念
参考书籍
《公理集合论导引》张锦文
标签：公理,定义,理论,自然数,后继,三歧性,集合论,集合,序数 From： https://www.cnblogs.com/vntlly/p/16861381.html