请读者具备离散数学的基础
三、基数
可数序数（可数集）
可数、不可数、有限、无限，在高中应该都有接触，但具体定义是什么，或许并不能很准确的说明。
(1)可数无穷序数（简称可数序数）：若序数\(α\)与自然数集\(N\)存在双射函数，则称\(α\)为可数序数，这其实和上次所说的标序号行为没什么两样，即如果一个序数能标序号那么就是可数的。上一次已经说明了良序集合必定有一序数与之同构即是可数的，但从良序拓展到序数可能并非容易，也就是并不能很容易地判断一个序数是否为可数的，比如整数集Z、有理数集Q这些都是可数的，但都要通过特殊的技巧性的方法去找到这样一个双射函数由此说明是可数的。相关内容在很后面会说明
例如整数集可以构造这样的函数去映射\(f(n)=\begin{cases}0,n=0 \\-k,n=2k \\k+1,n=2k+1 \end{cases}\)（即第一项是0，奇数项是正整数，偶数项是负整数）但是这样的双射函数并不一定是唯一的，如果能找到还有其他方法去映射，但是只要能和自然数集映射那么就是可数的
(2)如果集合的元素数有限那么必然可以当作良序集合即必定是可数，但如果是无穷集合就不一定了，因此如果要去证明集合是否可数一般会去讨论无穷集合（如实数集、有理数集之类的）。在序数的观点下某些东西被模糊了，比如极限序数既可以是有限的也可以是无限的
(3)序数\(N^x\)，\(x∈N\)是可数的
如证明\(N^2\)是可数的，根据序数幂乘的公式其下的元素有\(N,N+1,N+2,N×2,N×3,N×4+2...\)即\(N×X+Y~|~X,Y∈N\)的形式
这其实是二维的形式，取决于\(<X,Y>\)元组怎么变化，构造一个二元（并没有限定输入唯一）双射函数即可\(f(X,Y)=1/2((X+Y)^2+X+3Y)\)（从元组到自然数的双射）
当\(x=3\)时，即形式上变成了三维\(XN^2+YN+Z~|~X,Y,Z∈N\)，如果比较难寻找到映射，可以先将两个元素的元组映射（因为可数）为一个元素（即二维变成一维）后，三维的情况就可以化解成二维
同理当\(x=N\)即无穷维时，也是用这样的方法——多维通过可数的二维化为一维，直到化解成二维。
无穷维时，其映射的数量也是无数个，但可以用归纳法去简化描述
令\(A_0=N,A_K=\{α~|~N^k≤α＜N^{k+1}\}\)，因为\(∀k∈N,T_k\)是可数的，且是不相交的\(T_{k_1}∩T_{k_2}=Ø\)因此可以将无穷维分解为可数个（可数不代表有限）不相交的可数集合，最后也可映射为一个二元的映射表
直观上得到了如下的映射表
\(\begin{matrix}0&2&5&9&14&... \\ 1&4&8&13&... \\ 3&7&12&... \\ 6&11&... \\ 10&... \\ \vdots \end{matrix}\)
公式对应于\(f(X,Y)=1/2((X+Y)^2+X+3Y)\)，X代表第几行，Y代表第几列（注：从0开始）
(4)若\(α,β\)是可数序数，则\(α+β\)，\(α×β\)，\(α^β\)也是可数序数
证明：
加法的本质实际上是求解后继元素，因此可以构造\(f(x)=\begin{cases}g1(x),x∈[0,α) \\ g2(x),x∈[α,α+β) \end{cases},x∈α+β\)
这种形式实际上就是上面论证整数集为什么是可数的方法，即划分区域，比如划分了12个区域，则对应于有无穷元素的自然数可以划分出可能长短不一的12个区域进行对应。整数则划分了0、正整数、负整数，则分别对应于自然数的0、奇数、0以外的偶数（如果能想得更远的话，元素数相等的区域实际上就是求余得等价类）
乘法实质是加法的累加，既然加法成立，累加自然也成立，同理幂乘的累乘也成立
在这种证明观点下我个人理解可数是一种多维度可映射至一维的自然数的性质，即一个维度可能的区域可映射至自然数上的某一区域
(5)特殊序数：\(λ_0=N\)，\(λ_{n+1}=N^{λ_n}\)，\(λ=∪\{λ_i~|~i∈N\}\)且均是可数序数，结合(3)(4)并不难证明，这实际上是基于(3)自然数以及推论可数的情况下结合(4)可数序数的运算得出来的特殊的重要序数，如果要写，\(λ=N+N^2+N^3+...\)是一个无限复杂的可数序数，但是都能对应于N是非常难以想象的（换句话说N和λ的元素数是一样的，这也是刚接触基数时比较反常的地方）
势
对于任意序数\(α,β\)，若存在单射函数\(f:α→β\)，则记作\(|α|≤|β|\)（部分会记作\(\overset{=}{α}≤\overset{=}{β}\)或\(card(α)≤card(β)\)），若不存在双射函数\(g:α→β\)，则称为是不等势的记作\(|α|≠|β|\)（若存在双射则是等势的）
当然反过来还有其他符号诸如\(|α|≥|β|\)
\(|α|<|β|\)等价于\(|α|≤|β|∧|α|≠|β|\)（条件：存在单射但不存在双射）
\(|α|>|β|\)等价于\(|α|≥|β|∧|α|≠|β|\)（条件：存在单射但不存在双射）
\(|α|=|β|\)称为是等势的，等价于\(|α|≤|β|∧|α|≥|β|\)（条件：存在双射）
在序理论中有提到大于小于等于不等于之类的定义，说是用属于、包含关系来判断，实际上存在根本性的误区。因为属于包含实质上是比较范围大小而不是比较数量，比较数量则通过单射、双射可以模拟计数的过程，因此比较符的根本定义是计数（可参考希尔伯特无限旅馆悖论）
为什么说单射、双射就是模拟计数的过程。举个例子，\(|3|<|5|\)。其中\(3=\{0,1,2\},5=\{0,1,2,3,4\}\)。单射的过程如下，假设随便从3中拿元素2要去对应5的一个元素0，这实际上就消去了两者的一个元素，继续拿元素会发现3里拿了3个元素，5里拿了3个元素。因此单射模拟的是3和5两个集合不断地都拿出一个元素，能否在3拿光前5不拿光或恰好拿光，如果5拿光了而3还没拿光就是不存在单射即此时其实是有5到3的单射。双射则模拟的是能否在3拿光时5恰好拿光，如果有双射就代表了等势。
比较运算符实际是分成了两种。一个是基于属于、包含的关系\(α<β\)，一个则是基于单射、双射的关系\(|α|<|β|\)
但是两者存在联系，这种联系构成了基数的定义
基数
或许已经注意到了势是一个相对的概念，它并没有固定的大小，像是物理学中的势一样，需要有参考，这个参考就称为基数，用基数作为标尺来衡量，在具有基数的前提下势的意义就是集合的元素数
(1)\(∃α∀β(β<α→|β|<|α|)\)则称\(α\)为基数（人话翻译：若序数的子集的势均严格小于该序数，则该序数是基数），基数所对应的序数的次序称为自然次序（这个定义是保证最小性的原则，比如\(N、N+1、2N、N^2、λ、Z、Q\)都是等势的，那么会选取最小的N作为标尺来衡量，因为其他序数的子集N都与之等势因此无法作为基数）
(2)任意自然数是基数，由此有限集合便采用了这一形式去衡量数量，\(|\{5,7,8\}|=3\)实际意义就是集合有3个元素但深层次的解释是因为3作为了基数（标尺）
(3)自然数集N是基数并记作\(ℵ_0\)，有限集合的基数采用了自然数去衡量，无限集合则用\(ℵ_i\)去描述，其中\(ℵ_0\)是无限集合中最小的，自然也会有\(ℵ_1,ℵ_2...\)更大的基数去描述无限的大小。
ℵ1是什么？
定义\(ℵ_1=\{α~|~On(α)~∧~|α|≤ℵ_0\}\)，\(ℵ_0\)表示的是所有自然数的数量，\(ℵ_1\)表示的是自然数集的所有子集的数量
定义说明：\(On(α)\)表示序数不能为真类，，而\(|α|≤ℵ_0\)代表必须是\(α\)与\(N\)等势或者小于其势
比较著名猜想是1874年康托尔的连续统假设，内容为比\(ℵ_0\)大的基数中最小的是\(ℵ_1\)，希尔伯特将其列为23问题之一，目前在一定程度上得到了解决，结论是不能被证明也不能被证伪，后续会详细说明这部分内容
证明：为什么\(ℵ_1\)是基数？
这个证明非常复杂，读者可以跳过
定义\(R\)为\(ℵ_0\)内的某一良序关系即\(R⊆ℵ_0×ℵ_0\)
定义\(M\)为\(ℵ_0\)内的所有良序关系
因为\(M⊆P(ℵ_0×ℵ_0)\)所以\(M\)为集合
定义类函数\(f_R,∀R∈M\)有
\((1)dom~~f_R=ran~~R\)
\((2)f_R(x)=Sup\{f_R(y)~|~yRx~∧~y∈ℵ_0\}\)
因为\(R\)为良序关系，所以\(f_R(x)\)为序数，所以\(ran~~f_R\)也是序数集合且这个序数集合是可数的或有穷的（R在“无限的情况”下为可数，“有限的情况”下为有穷，Sup运算要么是加法要么是并集得依然保持可数的性质）
简单来说，\(f_R\)是得出R关系某个子集上确界的类函数，其中\(ran~~f_R\)相当于\(fld~~R\)的上确界
定义类函数\(F\)是\(f_R\)的集成，其中
\((1)dom~~F=M\)
\((2)F(R)=ran~~f_R\)
由于\(ran~~f_R\)是可数的（即势等于\(ℵ_0\)）或有穷的（即势小于\(ℵ_0\)），因此必定有\(F(R)∈ℵ_1\)
由此已经得出了一种函数用于得出\(ℵ_1\)的元素，需要反着证明下某个\(ℵ_1\)的元素一定可以通过F函数得出
假设\(∀α∈ℵ_1\)其中如果\(α\)是有穷的即能与某个自然数存在映射，定义本身已经定义了一个R因此可以通过F函数得出
如果\(α\)是无穷的即与\(ℵ_0\)等势，那么存在双射\(g:ℵ_0→α\)，即\(∃β∈α∃n∈ℵ_0(β=g(n))\)可以定义关系\(∀n_1,n_2∈ℵ_0(n_1~R~n_2=g(n_1)∈g(n_2))\)且R由于\(ℵ_0\)因此具有良序性，可以证明任何\(ℵ_1\)的元素可以通过F函数得出
在比较早的文章中介绍了替换原则用以将类转成集合的方法。因为\(F\)是类函数，\(M\)是集合，因此\(ran~~(F↾M)\)是集合，根据之前F的定义，\(M=dom~~F,ran~~F=ℵ_1\)，因此\(ran~~(F↾dom(F))=ran~~F=ℵ_1\)是集合
证明是集合后继续证明它是序数
证明序数关键在于证明它具有传递性、三歧性，由于\(ℵ_1\)是序数的集合，三歧性不证自明，只需要证明传递性即可
证明\(∪ℵ_1⊆ℵ_1\)：\(∪ℵ_1=\{x~|~∃y∈ℵ_1(x∈y)\}\)，\(x,y\)是序数根据三歧性有\(x⊆y\)，因此\(|x|≤|y|≤|ℵ_1|\)即\(x∈ℵ_1\)（\(x→y→ℵ_1\)存在单射，\(x⊆y\)使得\(|x|≤|y|≤|ℵ_1|\)成立，x作为y的一部分可部分映射到\(ℵ_1\)，成立后发现x可作为y的元素映射到\(ℵ_1\)的元素内）
证明\(ℵ_1\)是序数后需要证明基数
反证，假设不满足\(∀β(β＜ℵ_1→|β|<|ℵ_1|)\)条件，\(∃β(β＜ℵ_1~∧|ℵ_1|≤|β|~)\)即\(β\)即是\(ℵ_1\)的子集又必须有单射\(F:ℵ_1→β\)，这种可能性只有\(β\)为可数的情况，显然若\(β\)是有穷必然无法得出这样的结论。如果\(ℵ_1\)是可数序数，根据\(ℵ_1\)的定义，可得出\(ℵ_1∈ℵ_1\)，这显然是不可能的奇异集合，因此矛盾。反证得\(ℵ_1\)是基数
超穷基数ℵi
对于任意的序数i均定义\(ℵ_{i+1}=\{β~|~On(β)~∧~|β|≤|ℵ_i|\}\)
或许你已经注意到类似的基数是有无穷多的，也就是超穷基数在无穷级别的数量上也有无穷多
如何证明这些无穷多的基数也是基数可以参考\(ℵ_1\)的证明把\(R⊆N×N\)换成\(R⊆ℵ_i×ℵ_i\)即可
同时序数\(i\)如果是极限序数，那么\(ℵ_{i}=∪_{α＜i}ℵ_α\)
有时也会将\(ℵ\)写作\(ω\)或\(κ\)
定理：\(∀α∀β (|α|<|β|→|ℵ_α|<|ℵ_β|)\)
在这个意义上超穷基数的比较完全基于有穷基数的比较
基于势的三歧性：基数是特殊的序数，已经知道序数在包含属于关系上具有三歧性，而基数也具有另外一类三歧性是势的三歧性，即任意基数\(κ_1,κ_2\)下述式子中恰好成立一个
■\(|κ_1|<|κ_2|\)
■\(|κ_1|=|κ_2|\)
■\(|κ_1|>|κ_2|\)
这一点根据单射、双射的关系可以得出，这里不作证明（有需要的at博主）
势的比较一般不会刻意写出符号
如\(3<6\)时通常会认为是\(|3|<|6|\)数量上的比较而不是集合范围的比较
不过为了下面讨论的方便不会采用这种说法而是严格根据定义来分成两种比较
共尾性
有一函数\(f\)若满足下列所有条件则称是【严格单调递增的序数函数】并记作\(Smo(f)\)
■\(dom~f∈On\)
■\(ran~f⊆On\)
■\(∀α∈dom~f~~~∀β∈dom~f(α<β→f(α)<f(β))\)（即严格递增）
共尾性：\(∀α∀β(β≤α)\)且存在严格单调递增的序数函数\(f:β→α\)使得\(∃ζ∈ran~f~~~∀γ∈α(γ≤ζ)\)则称\(α\)共尾于\(β\)记作\(cof(α,β)\)
共尾性相比于\(Smo(f)\)来说除了保持递增的性质外，还保证值域中包含了上域的最大值（上域的每一个元素小于等于值域的某个元素，但\(ran~f⊆α\)即上域的最大值于值域中，此外由于严格递增的要求，很明显定义域最大值→值域最大值，博主认为这是所谓的“共尾”，但这个定义可能更宽泛，有些序数根本没有最大值）
对于三类序数而言有这些基本讨论（将\(K_Ⅰ\)表示为后继序数类，\(K_Ⅱ\)表述为极限序数类）
定理1：\(cof(α,0)→α=0\)即0只能与自身共尾
定理2：\(cof(α,1),α∈K_Ⅰ\)即任何后继序数都能和1共尾。
证明：
证明共尾性之前需要先审视\(Smo(f)\)是否满足定义，显然前三条是满足的
序数1只有唯一的元素0，序数α存在\(β^+=α\)使得\(f(0)=β\)存在这样的函数且β也是上域α中的最大值满足共尾性
说明：一般认为共尾性对于后继序数、0没什么意义，其主要意义在极限序数中
自反性：\(cof(α,α)\)
传递性：\(cof(a,β)∧cof(β,γ)→cof(α,γ)\)
定理3：对于任意序数\(α\)均有\(α∈K_Ⅱ→cof(ℵ_α,α)\)（可以找到函数\(f = \{<β,ℵ_β> ~|~ β∈α\}\)）
定理4：集合\(s⊆On\)则存在序数\(α\)和双射\(f\)，使得\(dom~f=α,ran~f=s\)且\(∀α_1,α_2∈α\)均有\(α_1<α_2←→f(α_1)<f(α_2)\)（这个定理相当于\(Smo(f)\)的扩展，即这类函数还存在可逆的双射函数）
定理5：\(∀α∀β(β≤α~∧~∃f(dom~f=β~∧~ran~f⊆α)~∧~∀α_1∈α∃β_1∈β(α_1≤f(β_1)))→∃β_0∈β^+(cof(α,β_0))\)（这个定理相当于共尾性的扩展，原本是值域内一值大于等于上域所有值，变成定义域内有一值映射后大于等于上域所有值，由于定义域包含值域，故存在子集令该元素于定义域外即可使共尾性成立）
定理6：\(∀α∀β(β≤α~∧~|β|=|α|)→∃β_0∈β^+(cof(α,β_0))\)（基数相等即之间存在双射，利用定理4易得满足定理5使得cof成立）
定理7：\(∀α∀β_1∀β_2(β_1≤β_2~∧~cof(α,β_1)~∧~cof(α,β_2))→∃β_0∈β_1^+(cof(β_2,β_0))\)
共尾性的特征数
定义：任意序数\(α\)，使得\(cof(α,β)\)成立的最小序数\(β\)称为共尾性的特征数（简称共尾度），记作\(cf(α)\)
(1) \(cf(α)≤α\)（根据共尾性定义可证）
(2) \(cf(α+1)=1\)
(3) \(cof(α,cf(α))\)
(4) \(cf(0)=0\)
(5) \(cf(ℵ_0)=ℵ_0\)
(6) \(∀α,cf(α)\)是基数
证明：
令\(β=cf(α)\)根据定义显然是序数
证明基数即证\(∀β_1(|β_1|=|β|→β≤β_1)\)
反证，假设\(β_1<β\)
根据定理7可得\(β_1<β~∧~|β_1|=|β|\)可导出\(∃β_2∈β_1^+(cof(β,β_2))\)
可以得到\(β≤β_2≤β_1\)
矛盾，故任何共尾度是基数
正则基数、奇异基数
定义\(Car=\{ℵ_α~|~α∈On\}\)即超穷基数类
定义\(Ca=ℵ_0∪Car\)
(1) \(On=∪Ca\)
(2) \(∀α(α∈Car→cf(α)∈Car)\)
证明：
因为\(α∈Car\)所以\(α∈K_Ⅱ\)
因为\(cof(α,cf(α))\)即\(cf(α)∈K_Ⅱ\)
根据Car定义有\(ℵ_0≤cf(α)\)且\(cf(α)\)也是基数
证得\(cf(α∈Car)\)
(3) \(α∈K_Ⅱ→cf(α)=cf(ℵ_α)\)
证明：
根据定理3可得\(cof(ℵ_α,α)\)
又因\(cof(α,cf(α))\)
根据共尾性的传递性可得\(cof(ℵ_α,cf(α))\)
同理可得\(cof(ℵ_α,cf(ℵ_α))\)
根据定理7：\(∃β≤cf(ℵ_α)(cof(cf(α),β))\)
根据共尾性两个数的关系可得
\(cf(α)≤β≤cf(ℵ_α)\)
\(cf(ℵ_α)≤cf(α)\)
即证\(cf(α)=cf(ℵ_α)\)
基于共尾度定义的基数：
对于任意无穷基数\(κ\)，若\(cf(κ)=κ\)则称\(κ\)为正则基数；若\(cf(κ)<κ\)则称为奇异基数
共尾度简化了比较复杂的基数，如\(κ=λ\)，不管和\(N\)相关的运算多复杂\(|κ|=N\)，但从共尾度角度来说\(cf(κ)=N＜κ\)是奇异基数（\(cof(κ,N)\)可以找到函数\(f=\{<i,N^i~|~i∈N>\}\)），这种情况都能用奇异基数来解释。至此要衡量无穷的大小变成了用正则基数衡量而排除运算情况复杂的奇异基数。如\(cf(N)=N\)是最小的无穷数，\(cf(ℵ_1)=ℵ_1,cf(ℵ_2)=ℵ_2,...\)
(4)证明\(cf(ℵ_1)=ℵ_1\)
反证，假设是奇异基数即\(cf(ℵ_1)<ℵ_1\)
因为\(cof(ℵ_1,cf(ℵ_1)),cf(ℵ_1)∈Car\)
故比\(ℵ_1\)小且在Car类中的只有\(ℵ_0\)
即\(cf(ℵ_1)=ℵ_0\)
即存在一函数\(f:ℵ_0→ℵ_1\)
满足\(ℵ_1=∪ran~f\)
满足\(∀α∈ℵ_0(f(α)<ℵ_1)\)即\(f(α)\)是可数的得\(ℵ_0=∪ran~f\)
显然这是矛盾的
(5) \(∀α∈K_Ⅰ→ℵ_α\)是正则基数
(6) \(∀α∈K_Ⅱ~∧α＜ℵ_α~→ℵ_α\)是奇异基数
遗留问题：已经有方法用来判定正则基数、奇异基数，然而极限序数中\(α=ℵ_α\)的情况并没有包含在内，在这种条件下如何判定基数是正则还是奇异？
弱不可达基数
定义一函数\(f:s→Ca\)其中\(s\)为非空集合，可得\(∪ran~f\)为基数
证明：
根据替换原则，
序数划分与良序集合的划分
On与Ca的同构性
总结
参考书籍
《公理集合论导引》张锦文
标签：公理,ran,cof,cf,集合论,序数,基数,可数 From： https://www.cnblogs.com/vntlly/p/17009328.html