2025-08-04T05:02:10Z

Zhy137036：

<div style="word-wrap: break-word;text-wrap: pretty;color: var(--color-subtle);font-style: italic;width:Fit-content;padding:1rem 1rem 2rem 1rem;border-left:solid #00000030 5px;background-color:var(--color-surface-2)">PrSS 虽然结构简单，但是却是目前已知的最强大的递归核心的基础．<ref>曹知秋. 大数理论. ''(EB/OL)'', Vol.1, pp.53-54. https://github.com/ZhiqiuCao/Googology</ref><br /><span style='float:right'><del>------</del> 曹知秋</span></div>

'''初等序列系统（Primative Sequence System, PrSS）'''是一种 [[Beklemishev's Worm|Worm]] 型[[序数记号]]。

=== 定义 ===

==== 合法式 ====
一个'''合法'''的 PrSS 表达式是形如 <math>S=(s_{1},s_{2},\cdots,s_{n})|n,s_{1},s_{2},\cdots,s_{n}\in\mathbb{N}</math>

且满足 <math>s_1=0,s_{k+1}-s_k\leqslant1(k=1,2,\cdots n-1)</math> 的自然数列（特别地，空序列 <math>()</math> 是合法的 PrSS 表达式）

实际上，以 1 序列开头的 PrSS 也是被广为接受的，其更多被用于表示阶差型序列。但无论 0 或 1 为开头，均不影响 PrSS 的展开方式与极限。

'''例：'''

* <math>(0,1,1,2,2)</math> 是一个合法的 PrSS 表达式
* <math>(\Omega,1,2)</math> 不是一个合法的 PrSS 表达式，因为 <math>\Omega\notin\mathbb{N}</math>
* <math>(0,2,4,6,8)</math> 不是一个合法的 PrSS 表达式，因为不满足条件 <math>s_{k+1}-s_k\leqslant1</math>

==== 结构 ====
合法的 PrSS 表达式可以分为零表达式、后继表达式、极限表达式，其定义如下：

*'''零表达式'''：满足 <math>n=0</math> 的表达式，即空序列 <math>()</math>
*'''后继表达式'''：满足 <math>n>0</math> 且 <math>s_{n}=0</math> 的表达式，例如 <math>(0,1,2,0)</math>
*'''极限表达式'''：满足 <math>n>0</math> 且 <math>s_{n}>0</math> 的表达式，例如 <math>(0,1,2,1)</math>

一个 PrSS 的'''极限表达式'''由以下四个部分组成：

# 末项（Last Term）
# 坏部（Bad Part）
# 坏根（Bad Root）
# 好部（Good Part）
'''末项：'''对于最大下标为 <math>n</math> 的 PrSS 表达式 <math>S=(s_{1},s_{2},\cdots,s_{n})</math>，其末项 <math>L=s_{n}</math>，即 <math>S=(s_{1},s_{2},\cdots,L)</math>

'''坏根：'''对于 <math>S=(s_{1},s_{2},\cdots,s_{n})|L=s_{n}</math>，令 <math>k=\max\{1 \leq k < n|s_{k}<s_{n}\}</math>，那么坏根定义为 <math>r=s_{k}</math>，即 <math>S=(s_{1},s_{2},\cdots,r,\cdots,L)</math>

通俗的说，是最靠右的小于末项的项。

因为极限表达式满足 <math>L=s_n>0</math> 且 <math>s_1=0</math>，所以坏根总是存在的。

'''坏部：'''对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，坏部定义为 <math>B=(s_{k},s_{k+1},\cdots,s_{n-1})</math>，即 <math>S=(s_{1},s_{2},\cdots,s_{k-1},B,L)</math>

通俗地说，是坏根（含）到末项（不含）的部分。坏部最短为 1 项。

'''好部：'''对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，好部定义为 <math>G=(s_{1},s_{2},\cdots,s_{k-1})</math>，即 <math>S=(G,B,L)</math>

通俗地说，好部是坏部之前的部分。好部可以为空。

=== 展开 ===
PrSS 的良序性已经得到证明，且其标准式的序等价于字典序，因此所有标准的 PrSS 表达式都一一对应着一个序数．

对于一个合法的 PrSS 表达式 <math>S=(s_1,s_2,\ldots,s_{n-1},s_n)</math>，其展开规则如下：

* 如果 <math>S</math> 是零表达式，则 <math>S</math> 代表序数 <math>0</math>
* 如果 <math>S</math> 是后继表达式，则其前驱是 <math>S'=(s_1,s_2,\ldots,s_{n-1})</math>
* 如果 <math>S</math> 是极限表达式，则根据前文定义确定好部、坏部，得到 <math>S=(G,B,L)</math>. 则其基本列的第 <math>m</math> 项定义为 <math>S[m]=(G,\underbrace{B,B,B,\cdots,B}_{m})</math>，其中 <math>m\in\mathbb{N}</math>. 或者说 <math>S</math> 的'''展开式'''为 <math>(G,\underbrace{B,B,B,\cdots}_{\omega})</math>

举例：

<math>S=(0,1,{\color{red}2},3,3,{\color{green}3})</math>

末项是标绿的 <math>{\color{green}3}</math>，坏根是从右往左数第一个比 <math>{\color{green}3}</math> 小的数，也就是标红色的 <math>{\color{red}2}</math>。

接下来，根据坏部的定义可以知道坏部是 <math>(2,3,3)</math>。

坏根之前的好部不用管，将末项抛弃：

<math>S=(0,1,{\color{red}2},3,3)</math>

复制坏部：

<math>S=(0,1,{\color{red}2},3,3,{\color{red}2},3,3,{\color{red}2},3,3,\cdots)</math>

我们就成功地展开了一个 PrSS 表达式。

=== PrSS 良序性的证明 ===
参见 [[PrSS的良序性]]。

=== 与康托范式的对应 ===
参见词条 [[PrSS VS 康托范式]]。

=== 拓展 ===
PrSS 记号有两种拓展：
* 高维 PrSS，如 PrSS 原作者所创的 [[BMS]]
* 阶差 PrSS ，有两种形式：
** [[长初等序列|LPrSS]] 及各种 [[Kirby-Paris Hydra|Hydra]] 记号
** [[HPrSS]]，[[0-Y]]，[[Y序列]] 等复杂阶差型记号

它们以 PrSS 序列为基础，刻画了非常巨大的序数。

=== 历史 ===
在 2014.8.14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS。<ref>Bashicu, H. (2014). basic言語で巨大数を作ってみたので上げてみる [I tried creating a huge number in basic language, so I thought I'd share it.]. ''(EB/OL)''. https://gyafun.jp/ln/archive/ln10.html</ref>

== 参考资料 ==
<references />

[[分类:入门]]
[[分类:记号]]

2025-07-29T08:00:56Z

Zhy137036：把“证明”改成分类

<div class="googology-home">
<h1 class="main-title"><span class="mw-headline" id="Googology_Wiki">Googology Wiki</span></h1>
<div class="tagline">Mapping the Universe of Monumental Numbers.</div>

<div class="fixed-grid">
<div class="fixed-btn">
[[:Category:记号|<span class="btn-text blue">记号</span>]]
</div>
<div class="fixed-btn">
[[:Category:分析|<span class="btn-text blue">分析</span>]]
</div>
<div class="fixed-btn">
[[:Category:入门|<span class="btn-text blue">入门</span>]]
</div>
<div class="fixed-btn">
[[:序数表|<span class="btn-text blue">序数表</span>]]
</div>
<div class="fixed-btn">
[[:前沿研究|<span class="btn-text blue">前沿</span>]]
</div>
<div class="fixed-btn">
[[:Googology_梗百科|<span class="btn-text blue">梗百科</span>]]
</div>
<div class="fixed-btn">
[[:大数简史|<span class="btn-text blue">大数简史</span>]]
</div>
<div class="fixed-btn">
[[:Googology_社区|<span class="btn-text blue">社区</span>]]
</div>
<div class="fixed-btn">
[[:记号展开器|<span class="btn-text blue">展开器</span>]]
</div>
<div class="fixed-btn">
[[:Category:证明|<span class="btn-text blue">证明</span>]]
</div>
</div>


<div class="wiki-stats-container">
<div class="home-card">
<h2 style="margin-top: 0">数据统计</h2>
<p>Googology Wiki 欢迎你的编辑！</p>

<div class="template-statsbar">
<div class="template-statsbar__item">
<div class="template-statsbar__label">总条目数</div>
<div class="template-statsbar__data" id="totalArticles">loading...</div>
</div>

<div class="template-statsbar__item">
<div class="template-statsbar__label">总编辑数</div>
<div class="template-statsbar__data" id="totalEdits">loading...</div>
</div>

<div class="template-statsbar__item">
<div class="template-statsbar__label">注册用户数</div>
<div class="template-statsbar__data" id="totalUsers">loading...</div>
</div>

</div>
</div>
</div>
</div>

无穷基数的平方等于自身

2025-07-29T08:00:15Z

Zhy137036：

2025-07-29T07:45:44Z

Zhy137036：创建页面，内容为“== <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math> 的证明 == 证明：我们如下定义 <math>\mathrm{Ord}^2</math> 上的良序： <math display=block> \begin{aligned} (\alpha,\beta)<(\gamma,\delta)\iff{}&\max\{\alpha,\beta\}<\max\{\gamma,\delta\}\\ &\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land \alpha<\gamma)\\ &\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land\alpha=\gamma\land\beta<\delta)\\ \end{aligned} </math> 可以证明，…”

基数

2025-07-29T07:24:38Z

Zhy137036：/* 定理 \aleph_\alpha*\aleph_\alpha=\aleph_\alpha 的证明 */

'''基数'''<ref>冯琦. 集合论导引[M]. 北京: 科学出版社, 2019.</ref>是一类特殊的[[序数]]。

==== 定义 ====

我们说两个集合 <math>A,B</math> '''等势'''，当且仅当在它们之间存在一个'''双射（一一对应）'''，记为 <math>|A|=|B|</math>。

对于任意一个序数 <math>\alpha</math> 而言，<math>\alpha</math> 的'''势'''，记为 <math>|\alpha|</math>，是与 <math>\alpha</math> 等势的最小序数，即

* <math>|\alpha| = \min\{\beta \leq \alpha\ |\ |\alpha|=|\beta|\}</math>

一个序数 <math>\alpha</math> 是'''基数'''，当且仅当 <math>\alpha=|\alpha|</math>。

==== 基数上的序关系 ====

基数的'''序'''被定义为如下形式

<math>|X| \leq |Y|</math>，如果存在一个单射自 <math>X</math> 到 <math>Y</math>

我们同样可以定义严格序

<math>|X| < |Y|</math> 表示 <math>|X| \leq |Y|</math> 且 <math>|X| \neq |Y|</math>

例：

<math>|A|<|\mathfrak{P}(A)|=|\{\emptyset,\{\emptyset\}\}^{A}|</math>

==== 有限基数和无穷基数（超限基数） ====
<math>\forall n \in \omega(n=|n|)</math>，这意味着所有的自然数 <math>n</math> 都是一个基数。

从而，我们称呼一个集合 <math>X</math> 的基数是有限的，当且仅当存在一个自然数 <math>n \in \mathbb{N}</math> 使得 <math>|X|=|n|=n</math>

此时我们称呼 <math>X</math> 是有 <math>n</math> 个元素的。'''有限基数'''即全体自然数。

若一个基数不是有限的，则我们称它为'''无穷基数（超限基数）'''。

==== 极限基数和后继基数 ====

一个基数 <math>k</math> 是一个'''后继基数'''，当且仅当存在一个基数 <math>\lambda</math>，使得 <math>k</math> 是最小的大于 <math>\lambda</math> 的基数，此时也称 <math>k</math>为<math>\lambda</math> 的基数后继。

一个基数 <math>k</math> 是一个'''极限基数'''，当且仅当对于任意 <math>\lambda < k</math>，<math>\lambda</math> 的基数后继也小于 <math>k</math>。

有以下定理：
# 若一个[[序数#有限序数与超限序数|无穷序数]]是基数，我们便称之为'''阿列夫数'''；
# <math>\aleph_{0} = \omega = |\omega|</math>，<math>\omega</math>是第一个无穷基数；
# <math>\aleph_{1} = \omega_{1} = |\omega_{1}|</math>，<math>\omega_{1}</math>是第一个不可数基数。
# 第一个不可数的极限基数为<math>\aleph_{\omega}</math>

由此我们定义阿列夫数的递增序列

* <math>\aleph_{0}=\omega</math>
* <math>\aleph_{\alpha+1}=\omega_{\alpha+1}=\aleph_{\alpha}</math> 的基数后继
* <math>\aleph_{\gamma}\text{(}\gamma\text{是非零极限序数)}=\bigcup\{\omega_{\alpha}|\alpha<\gamma\}</math>

我们称一个基数为 <math>\aleph_{0}</math> 的无穷集合是'''可数的（countable）'''，一个基数不为 <math>\aleph_{0}</math> 的无穷集合是'''不可数的（uncountable）。'''

==== 基数的运算 ====

我们依赖集合的基本运算，来定义基数的运算。

对于两个基数 <math>a,b</math>，有两个基数分别为 <math>a,b</math> 且'''互不相交'''的集合 <math>A,B</math>，有

* <math>a+b=|A\cup B|</math>
* <math>a\cdot b=|A\times B|</math>
* <math>a^{b}=|A^{B}|</math>

其中 <math>A^{B}</math> 表示全体从 <math>B</math> 到 <math>A</math> 的映射所构成的集合。

基数有以下的运算规律：

对于任意基数 <math>a,b,c</math>，有：
* <math>a+b=b+a</math>;
* <math>a\cdot b=b\cdot a</math>;
* <math>a+(b+c)=(a+b)+c</math>;
* <math>a\cdot (b\cdot c)=(a\cdot b)\cdot c</math>;
* <math>(a\cdot b)^{c}=a^{c}\cdot b^{c}</math>;
* <math>a^{b+c}=a^{c}\cdot a^{b}</math>;
* <math>(a^b)^{c}=a^{b\cdot c}</math>;
* 如果 <math>a\leq b</math>，那么 <math>a^{c}\leq b^{c}</math>;
* 如果 <math>0<b\leq a</math>，那么 <math>c^{b}\leq c^{a}</math>;
* <math>a^{0}=1, 1^{b}=b</math>，若 c 非空，<math>0^{c}=0</math>.

基数有如下定理：
* <math>\aleph_{\alpha} \cdot \aleph_{\alpha} = \aleph_{\alpha}</math>
* <math>\aleph_{\alpha}+\aleph_{\beta}=\aleph_{\alpha}\cdot \aleph_{\beta} = max\{\aleph_{\alpha},\aleph_{\beta}\}</math>

==== 共尾度 ====

对于一个[[良序]]集合 <math>(W,<)</math> 而言，我们称序数 <math>\alpha</math> 为它的长度或者序型，记成 <math>\alpha=ot(W,<)</math>，当且仅当它与 <math>(\alpha,<)</math> 同构。

设 <math>\alpha</math> 是一个非零[[序数#极限序数|极限序数]]，<math>\alpha</math> 的'''共尾度'''，记为 <math>\mathrm{cf}(\alpha)</math>，由以下等式定义：
* <math>\mathrm{cf}(\alpha)=min\{ot(A,<)|A\subseteq \alpha \and \forall \beta(\beta < \alpha \rightarrow \exist \gamma(\gamma \in A\and \beta < \gamma))\}</math>

即，<math>\mathrm{cf}(\alpha)</math> 是 <math>\alpha</math> 的最短的无界子集的长度。

设 <math>\alpha \geq \gamma \geq \omega</math> 为两个极限序数，那么以下三个命题等价：
# <math>\gamma=\mathrm{cf}(\alpha)</math>
# 存在从 <math>\gamma</math> 到 <math>\alpha</math> 的无界单增映射，并且对于任何一个 <math>\eta<\gamma</math>，任意一个从 <math>\eta</math> 到 <math>\alpha</math> 上的映射一定在 <math>\alpha</math> 中有界
# <math>\gamma</math> 为最小的序数<math>\beta</math>，使得存在一个严格递增的长度为 <math>\beta</math> 的序数序列 <math>\langle \alpha_{\xi}:\xi<\beta \rangle</math>，<math>\lim_{\xi\to \beta}\ \alpha_{\xi}=\alpha</math>

显然，共尾度是一个极限序数且当 <math>\alpha</math> 为极限序数时它的共尾度是正则的。

一个基数是'''正则的'''当且仅当它的共尾度为自身。一个基数是'''奇异的'''当且仅当它不是正则的。

有如下定理：
* 所有后继基数都是正则基数。
* 所有奇异基数都是极限基数。

==== 定理 <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math> 的证明 ====

证明：我们如下定义 <math>\mathrm{Ord}^2</math> 上的良序：

<math display=block>
\begin{aligned}
(\alpha,\beta)<(\gamma,\delta)\iff{}&\max\{\alpha,\beta\}<\max\{\gamma,\delta\}\\
&\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land \alpha<\gamma)\\
&\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land\alpha=\gamma\land\beta<\delta)\\
\end{aligned}
</math>

可以证明，这个序是一个良序。

我们令 <math>\Gamma(\alpha,\beta)</math> 表示集合 <math>\{(\gamma,\delta)\in\mathrm{Ord}^2\mid(\gamma,\delta)<(\alpha,\beta)\}</math> 的序型。可以证明，<math>\Gamma:\mathrm{Ord}^2\to\mathrm{Ord}</math> 保序且一对一。

下面用 <math>\Gamma[\alpha\times\beta]</math> 表示 <math>\{\Gamma(\gamma,\delta)\mid(\gamma,\delta)\in\alpha\times\beta\}</math>，即集合 <math>\alpha\times\beta</math> 在 <math>\Gamma</math> 下的像集。

注意到 <math>\Gamma[\omega_\alpha\times\omega_\alpha]=\Gamma(0,\omega_\alpha)\ge\omega_\alpha</math>，以及 <math>\mathrm\Gamma[\omega\times\omega]=\omega</math>（取对角线计数）。

我们要证 <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math>，只需证 <math>\Gamma[\omega_\alpha\times\omega_\alpha]=\omega_\alpha</math>。

使用反证法。令 <math>\alpha</math> 是使得 <math>\omega_\alpha<\Gamma[\omega_\alpha\times\omega_\alpha]</math> 的最小序数，则存在 <math>\beta,\gamma<\omega_\alpha</math> 使得 <math>\Gamma(\beta,\gamma)=\omega_\alpha</math>。

那么我们取 <math>\delta</math> 满足 <math>\max\{\beta,\gamma\}<\delta<\omega_\alpha</math>，则 <math>\omega_\alpha=\Gamma(\beta,\gamma)\in\Gamma[\delta\times\delta]</math>。

取上式两侧的基数，得到 <math>\aleph_\alpha<|\delta\times\delta|</math>。

因为 <math>\delta>\max\{\beta,\gamma\}\ge\omega</math>，所以可设 <math>\delta</math> 的基数为 <math>\aleph_\xi</math>，其中 <math>\xi<\alpha</math>。

我们刚才设 <math>\alpha</math> 是使得 <math>\omega_\alpha<\Gamma(\omega_\alpha\times\omega_\alpha)</math> 的最小序数，所以 <math>\omega_\xi=\Gamma[\omega_\xi\times\omega_\xi]</math>，即 <math>\aleph_\xi=\aleph_\xi\times\aleph_\xi</math>。

所以 <math>|\delta\times\delta|=|\delta|\times|\delta|=\aleph_\xi\times\aleph_\xi=\aleph_\xi<\aleph_\alpha</math>，矛盾。

因此，对任意序数 <math>\alpha</math>，都有 <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math>。

==== 参考资料 ====
<references />

[[分类:集合论相关]]

基数

2025-07-29T07:23:11Z

Zhy137036：

'''基数'''<ref>冯琦. 集合论导引[M]. 北京: 科学出版社, 2019.</ref>是一类特殊的[[序数]]。

==== 定义 ====

我们说两个集合 <math>A,B</math> '''等势'''，当且仅当在它们之间存在一个'''双射（一一对应）'''，记为 <math>|A|=|B|</math>。

对于任意一个序数 <math>\alpha</math> 而言，<math>\alpha</math> 的'''势'''，记为 <math>|\alpha|</math>，是与 <math>\alpha</math> 等势的最小序数，即

* <math>|\alpha| = \min\{\beta \leq \alpha\ |\ |\alpha|=|\beta|\}</math>

一个序数 <math>\alpha</math> 是'''基数'''，当且仅当 <math>\alpha=|\alpha|</math>。

==== 基数上的序关系 ====

基数的'''序'''被定义为如下形式

<math>|X| \leq |Y|</math>，如果存在一个单射自 <math>X</math> 到 <math>Y</math>

我们同样可以定义严格序

<math>|X| < |Y|</math> 表示 <math>|X| \leq |Y|</math> 且 <math>|X| \neq |Y|</math>

例：

<math>|A|<|\mathfrak{P}(A)|=|\{\emptyset,\{\emptyset\}\}^{A}|</math>

==== 有限基数和无穷基数（超限基数） ====
<math>\forall n \in \omega(n=|n|)</math>，这意味着所有的自然数 <math>n</math> 都是一个基数。

从而，我们称呼一个集合 <math>X</math> 的基数是有限的，当且仅当存在一个自然数 <math>n \in \mathbb{N}</math> 使得 <math>|X|=|n|=n</math>

此时我们称呼 <math>X</math> 是有 <math>n</math> 个元素的。'''有限基数'''即全体自然数。

若一个基数不是有限的，则我们称它为'''无穷基数（超限基数）'''。

==== 极限基数和后继基数 ====

一个基数 <math>k</math> 是一个'''后继基数'''，当且仅当存在一个基数 <math>\lambda</math>，使得 <math>k</math> 是最小的大于 <math>\lambda</math> 的基数，此时也称 <math>k</math>为<math>\lambda</math> 的基数后继。

一个基数 <math>k</math> 是一个'''极限基数'''，当且仅当对于任意 <math>\lambda < k</math>，<math>\lambda</math> 的基数后继也小于 <math>k</math>。

有以下定理：
# 若一个[[序数#有限序数与超限序数|无穷序数]]是基数，我们便称之为'''阿列夫数'''；
# <math>\aleph_{0} = \omega = |\omega|</math>，<math>\omega</math>是第一个无穷基数；
# <math>\aleph_{1} = \omega_{1} = |\omega_{1}|</math>，<math>\omega_{1}</math>是第一个不可数基数。
# 第一个不可数的极限基数为<math>\aleph_{\omega}</math>

由此我们定义阿列夫数的递增序列

* <math>\aleph_{0}=\omega</math>
* <math>\aleph_{\alpha+1}=\omega_{\alpha+1}=\aleph_{\alpha}</math> 的基数后继
* <math>\aleph_{\gamma}\text{(}\gamma\text{是非零极限序数)}=\bigcup\{\omega_{\alpha}|\alpha<\gamma\}</math>

我们称一个基数为 <math>\aleph_{0}</math> 的无穷集合是'''可数的（countable）'''，一个基数不为 <math>\aleph_{0}</math> 的无穷集合是'''不可数的（uncountable）。'''

==== 基数的运算 ====

我们依赖集合的基本运算，来定义基数的运算。

对于两个基数 <math>a,b</math>，有两个基数分别为 <math>a,b</math> 且'''互不相交'''的集合 <math>A,B</math>，有

* <math>a+b=|A\cup B|</math>
* <math>a\cdot b=|A\times B|</math>
* <math>a^{b}=|A^{B}|</math>

其中 <math>A^{B}</math> 表示全体从 <math>B</math> 到 <math>A</math> 的映射所构成的集合。

基数有以下的运算规律：

对于任意基数 <math>a,b,c</math>，有：
* <math>a+b=b+a</math>;
* <math>a\cdot b=b\cdot a</math>;
* <math>a+(b+c)=(a+b)+c</math>;
* <math>a\cdot (b\cdot c)=(a\cdot b)\cdot c</math>;
* <math>(a\cdot b)^{c}=a^{c}\cdot b^{c}</math>;
* <math>a^{b+c}=a^{c}\cdot a^{b}</math>;
* <math>(a^b)^{c}=a^{b\cdot c}</math>;
* 如果 <math>a\leq b</math>，那么 <math>a^{c}\leq b^{c}</math>;
* 如果 <math>0<b\leq a</math>，那么 <math>c^{b}\leq c^{a}</math>;
* <math>a^{0}=1, 1^{b}=b</math>，若 c 非空，<math>0^{c}=0</math>.

基数有如下定理：
* <math>\aleph_{\alpha} \cdot \aleph_{\alpha} = \aleph_{\alpha}</math>
* <math>\aleph_{\alpha}+\aleph_{\beta}=\aleph_{\alpha}\cdot \aleph_{\beta} = max\{\aleph_{\alpha},\aleph_{\beta}\}</math>

==== 共尾度 ====

对于一个[[良序]]集合 <math>(W,<)</math> 而言，我们称序数 <math>\alpha</math> 为它的长度或者序型，记成 <math>\alpha=ot(W,<)</math>，当且仅当它与 <math>(\alpha,<)</math> 同构。

设 <math>\alpha</math> 是一个非零[[序数#极限序数|极限序数]]，<math>\alpha</math> 的'''共尾度'''，记为 <math>\mathrm{cf}(\alpha)</math>，由以下等式定义：
* <math>\mathrm{cf}(\alpha)=min\{ot(A,<)|A\subseteq \alpha \and \forall \beta(\beta < \alpha \rightarrow \exist \gamma(\gamma \in A\and \beta < \gamma))\}</math>

即，<math>\mathrm{cf}(\alpha)</math> 是 <math>\alpha</math> 的最短的无界子集的长度。

设 <math>\alpha \geq \gamma \geq \omega</math> 为两个极限序数，那么以下三个命题等价：
# <math>\gamma=\mathrm{cf}(\alpha)</math>
# 存在从 <math>\gamma</math> 到 <math>\alpha</math> 的无界单增映射，并且对于任何一个 <math>\eta<\gamma</math>，任意一个从 <math>\eta</math> 到 <math>\alpha</math> 上的映射一定在 <math>\alpha</math> 中有界
# <math>\gamma</math> 为最小的序数<math>\beta</math>，使得存在一个严格递增的长度为 <math>\beta</math> 的序数序列 <math>\langle \alpha_{\xi}:\xi<\beta \rangle</math>，<math>\lim_{\xi\to \beta}\ \alpha_{\xi}=\alpha</math>

显然，共尾度是一个极限序数且当 <math>\alpha</math> 为极限序数时它的共尾度是正则的。

一个基数是'''正则的'''当且仅当它的共尾度为自身。一个基数是'''奇异的'''当且仅当它不是正则的。

有如下定理：
* 所有后继基数都是正则基数。
* 所有奇异基数都是极限基数。

==== 定理 <math>\aleph_\alpha*\aleph_\alpha=\aleph_\alpha</math> 的证明 ====

证明：我们如下定义 <math>\mathrm{Ord}^2</math> 上的良序：

<math display=block>
\begin{aligned}
(\alpha,\beta)<(\gamma,\delta)\iff{}&\max\{\alpha,\beta\}<\max\{\gamma,\delta\}\\
&\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land \alpha<\gamma)\\
&\lor(\max\{\alpha,\beta\}=\max\{\gamma,\delta\}\land\alpha=\gamma\land\beta<\delta)\\
\end{aligned}
</math>

可以证明，这个序是一个良序。

我们令 <math>\Gamma(\alpha,\beta)</math> 表示集合 <math>\{(\gamma,\delta)\in\mathrm{Ord}^2\mid(\gamma,\delta)<(\alpha,\beta)\}</math> 的序型。可以证明，<math>\Gamma:\mathrm{Ord}^2\to\mathrm{Ord}</math> 保序且一对一。

下面用 <math>\Gamma[\alpha\times\beta]</math> 表示 <math>\{\Gamma(\gamma,\delta)\mid(\gamma,\delta)\in\alpha\times\beta\}</math>，即集合 <math>\alpha\times\beta</math> 在 <math>\Gamma</math> 下的像集。

注意到 <math>\Gamma[\omega_\alpha\times\omega_\alpha]=\Gamma(0,\omega_\alpha)\ge\omega_\alpha</math>，以及 <math>\mathrm\Gamma[\omega\times\omega]=\omega</math>（取对角线计数）。

我们要证 <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math>，只需证 <math>\Gamma[\omega_\alpha\times\omega_\alpha]=\omega_\alpha</math>。

使用反证法。令 <math>\alpha</math> 是使得 <math>\omega_\alpha<\Gamma[\omega_\alpha\times\omega_\alpha]</math> 的最小序数，则存在 <math>\beta,\gamma<\omega_\alpha</math> 使得 <math>\Gamma(\beta,\gamma)=\omega_\alpha</math>。

那么我们取 <math>\delta</math> 满足 <math>\max\{\beta,\gamma\}<\delta<\omega_\alpha</math>，则 <math>\omega_\alpha=\Gamma(\beta,\gamma)\in\Gamma[\delta\times\delta]</math>。

取上式两侧的基数，得到 <math>\aleph_\alpha<|\delta\times\delta|</math>。

因为 <math>\delta>\max\{\beta,\gamma\}\ge\omega</math>，所以可设 <math>\delta</math> 的基数为 <math>\aleph_\xi</math>，其中 <math>\xi<\alpha</math>。

我们刚才设 <math>\alpha</math> 是使得 <math>\omega_\alpha<\Gamma(\omega_\alpha\times\omega_\alpha)</math> 的最小序数，所以 <math>\omega_\xi=\Gamma[\omega_\xi\times\omega_\xi]</math>，即 <math>\aleph_\xi=\aleph_\xi\times\aleph_\xi</math>。

所以 <math>|\delta\times\delta|=|\delta|\times|\delta|=\aleph_\xi\times\aleph_\xi=\aleph_\xi<\aleph_\alpha</math>，矛盾。

因此，对任意序数 <math>\alpha</math>，都有 <math>\aleph_\alpha\times\aleph_\alpha=\aleph_\alpha</math>。

==== 参考资料 ====
<references />

[[分类:集合论相关]]

序数坍缩函数

2025-07-28T10:13:13Z

Zhy137036：

'''序数塌缩函数（Ordinal Collapsing Function，OCF）'''是一种[[序数]]函数。它们的特点是利用足够大的序数（通常是[[序数#非递归序数|非递归序数]]）来输出递归序数。事实上，OCF 有很多不同的版本。本词条着力于介绍 [[EBO]] 之前的 '''BOCF'''（Buchholz's OCF）和 '''MOCF'''（Madore's OCF）。

== 教学 ==

=== BOCF 简介 ===
''前排提醒：对严谨数学定义不感冒或看不懂的读者可以直接跳到[[OCF#直观理解与操作规则|直观理解与操作规则]]。''

==== 定义 ====
首先我们给出 BOCF 只引入第一个非递归序数 <math>\Omega</math> 的定义：

# <math>C_0(x)=\{0,\Omega\}</math>
# <math>C_{n+1}(x)=C_n(x)\cup\{\alpha+\beta,\psi(\gamma)|\alpha,\beta,\gamma\in C_n(x),\gamma <x\}</math>
# <math>C(x)=\bigcup_{n<\omega}C_n(x)</math>
# <math>\psi(x)=\min\{\alpha<\Omega|\alpha\not\in C(x)\}</math>

其中的 <math>\Omega</math> 要求是一个足够大的序数。以往的资料一般使用第一个[[序数#可数序数与不可数序数|不可数序数]] <math>\omega_1</math> 来作为它。但我们发现，第一个非递归序数 <math>\omega_1^{CK}</math> 已经可以满足我们的需求。因此，目前提到 <math>\Omega</math>，默认指的是 <math>\omega_1^{CK}</math>。

这四条规则很是抽象，让我们一条一条来看。

规则 1：<math>C_0(x)=\{0,\Omega\}</math>。对于任意的 x ， <math>C_0(x)</math> 是同一个集合。

规则 2，这个规则递归定义了 <math>C_{n+1}(x)</math>，它是 <math>C_n(x)</math> 再加上 <math>C_n(x)</math> 中的元素通过加法和 ψ 函数能产生的所有元素。这里要求 ψ 函数自变量小于 x，因为 <math>\psi(x)</math> 是需要 <math>C(x)</math> 来定义的。

规则3，<math>C(x)</math> 是对所有的 <math>C_n(x)</math> 取并集得到的集合。

规则4，<math>\psi(x)</math> 就是所有小于 <math>\Omega</math> 的序数中，不属于 <math>C(x)</math> 的最小序数。

==== <math>\varepsilon_0</math> 之前 ====
以下是一些运算实例：

* <math>C_0(0)=\{0,\Omega\}</math>
* <math>C_1(0)=\{0,\Omega,\Omega\times2\}</math>
* <math>C_2(0)=\{0,\Omega,\Omega\times2,\Omega\times3,\Omega\times4\}</math>
*……

<math>C(0)=\{0,\Omega,\cdots\}</math>，省略号省掉了大于 <math>\Omega</math> 的序数。

因此 <math>\psi(0)</math> 是最小的小于 <math>\Omega</math> 的不在 <math>C(0)</math> 里的序数，即 1。

下一个例子是 <math>\psi(2)</math>，假定首先你已经知道了 <math>\psi(1)=\omega</math>（可以自己验证），我们要开始计算 <math>\psi(2)</math>，还是不展示大于 <math>\Omega</math> 的序数：

* <math>C_0(2)=\{0,\Omega\}</math>
* <math>C_1(2)=\{0,\psi(0)=1,\Omega,\cdots\}</math>
* <math>C_2(2)</math> 包含了 1，2 和 <math>\psi(1)</math>，即 ω
* <math>C_3(2)</math> 包含了 <math>1,2,3,4,\omega,\omega+1,\omega+2,\omega\times2</math>

以此类推，最后能得到 <math>C(2)</math> 中包含了全体小于 <math>\omega^2</math> 的序数和一大堆大于 <math>\Omega</math> 的序数。因此根据定义，<math>\psi(2)=\omega^2</math>。

ψ 函数内是极限序数并不影响定义和计算。

你有没有觉得一步一步按定义走太过于繁琐？下面给出它的 2 个性质:

# <math>\psi(m+1)=\psi(m)\times\omega</math>，m 是任意序数
# <math>\psi(\lambda)=\sup\{\psi(\kappa)|\kappa<\lambda\}</math>，α 是任意非 0 极限序数

根据这个性质，我们可以轻松的得到：

* <math>\psi(\omega)=\omega^{\omega}=\psi(\psi(1))</math>
* <math>\psi(\omega+1)=\omega^{\omega+1}=\psi(\psi(1)+1)</math>
* <math>\psi(\omega\times2)=\omega^{\omega\times2}=\psi(\psi(1)\times2)</math>
* <math>\psi(\omega^2)=\omega^{\omega^2}=\psi(\psi(2))</math>
* <math>\psi(\omega^{\omega})=\omega^{\omega^{\omega}}=\psi(\psi(\psi(1)))</math>
* <math>\psi(\omega^{\omega^{\omega}})=\omega^{\omega^{\omega^{\omega}}}=\psi(\psi(\psi(\psi(1))))</math>
* ……

到这里和[[康托范式]]，[[veblen函数|Veblen 函数]]的 <math>\varphi(x)</math> 都是一致的。然而，在 <math>\varepsilon_0</math> 开始，OCF 将与它们分道扬镳。

==== <math>\varepsilon_0</math> 与平台期 ====
<math>\varepsilon_0=\alpha\rightarrow\psi(\alpha)</math> 的第一个不动点，这里没有问题。问题出在 <math>\psi(\varepsilon_0+1)</math> 上。

注意到 <math>C_0(\varepsilon_0+1)=\{0,\Omega\}</math>，<math>C_1(\varepsilon_0+1)</math> 中小于 <math>\Omega</math> 的最大元素是 <math>\psi(0)</math>，<math>C_2(\varepsilon_0+1)</math> 中小于 <math>\Omega</math> 的最大元素是 <math>\psi(\psi(0))</math>，<math>C_2(\varepsilon_0+1)</math> 中小于 <math>\Omega</math> 的最大元素是 <math>\psi(\psi(\psi(0)))</math>……

因此，<math>\psi(\varepsilon_0)</math> 始终无法出现在这里面。这直接导致了 <math>C(\varepsilon_0+1)</math> 中，小于 <math>\Omega</math> 的最小的不在里面的依然是 <math>\psi(\varepsilon_0)</math>，相当于“卡住了”。这意味着对于所有的 <math>\varepsilon_0\leq\alpha\leq\Omega</math>，都有 <math>\psi(\alpha)=\psi(\varepsilon_0)</math>。这就像一个巨大的平台，因此称为'''平台期'''。

直到 <math>\psi(\Omega+1)</math> 才迎来了转机。因为 <math>\Omega</math> 也在 <math>C_0(x)</math> 里面，因此 <math>\psi(\Omega)</math> 终于可以被放进 <math>C_1(\Omega+1)</math> 里面了。结果是 <math>\psi(\Omega+1)=\psi(\Omega)\times\omega</math>。后面再一次向上增长，直到 <math>\alpha\rightarrow\psi(\Omega+\alpha)</math> 的不动点。从这里到 <math>\psi(\Omega+\Omega)</math> 又是一段平台期。直到 <math>\psi(\Omega+\Omega+1)</math> 再次恢复增长。

这样的定义可以一直运行到 <math>\psi(\Omega\times\omega)</math>，再往后走不下去了。可是它相比其他[[序数记号]]，如 [[Veblen函数]]依然是孱弱的。为了继续前进，我们需要引入更多的非递归序数。

==== 更多的非递归序数 ====
下面是引入更多非递归序数的 BOCF 定义：

# <math>C_0^v(x)=\{\alpha|\alpha<\Omega_v\}\cup\{\Omega_{\beta}|v<\beta<\omega\}</math>
# <math>C_{n+1}^v(x)=\{\alpha+\beta,\psi_{\delta}(\gamma)|\alpha,\beta,\gamma\in C_n^v(x),\gamma<x,\delta<\omega\}</math>
# <math>C^v(x)=\bigcup_{n<\omega}C_n^v(x)</math>
# <math>\psi_v(x)=\min\{\alpha<\Omega_{v+1}|\alpha\notin C^v(x)\}</math>

<math>\psi</math> 函数即 <math>\psi_0</math> 函数。

可以看到，根据定义，有 <math>C_0^1(0)=\{\alpha,\Omega_2|\alpha<\Omega\}</math>，随后 <math>C_n^1(0)</math> 是根据 <math>C_0^1(0)=\{\alpha,\Omega_2|\alpha<\Omega\}</math> 中元素进行加法所得到的所有东西，注意到它们内部依然不存在 <math>\Omega\sim\Omega_2</math> 的序数。因此，<math>\psi_1(0)=\Omega</math>。对于 <math>\psi_1(1)</math>，因为它可以把 <math>\psi_1(0)</math> 塞进 C 里，因此，最后有 <math>\psi_1(1)=\Omega\times\omega</math>。之后的内容是顺理成章的，类似 <math>\psi(0)\sim\psi(\psi(\psi(\cdots)))</math> 的过程，有 <math>\psi_1(\psi_1(\psi_1(\cdots)))=\Omega^{\Omega^{\Omega^{\cdots}}}</math>。我们暂时记 <math>\psi_1(1,0)=\alpha\rightarrow\psi_1(\alpha)</math> 的不动点。可以验证，对于 <math>\psi_1</math> 函数来说，这里依然存在 <math>\psi_1(1,0)<\alpha<\Omega_2</math> 的平台期。后面的一切都是顺理成章的。直到任意的 <math>\psi_n</math>，都是一样的。

但有一点需要注意，对于 <math>\psi</math> 函数来说，<math>\psi(\psi_1(\Omega_2))</math> 并没有打破从 <math>\psi(\psi_1(1,0))</math> 开始的平台期，这个平台期继续向前，直到 <math>\psi(\Omega_2)</math> 才结束。这一现象称为'''藏层'''。

BOCF 的 <math>\psi(\Omega_{\omega})=\sup\{\psi(\Omega),\psi(\Omega_2),\psi(\Omega_3),\cdots\}</math>，这一序数有一个名字是[[BO]]（Buchholz's Ordinal ）,在[[googology]]中是一个非常重要的序数。

''tips：OCF中的 <math>\Omega</math> 不一定非得是[[序数#非递归序数|非递归序数]]，它只需要大于'''所有你研究的序数'''就可以了，比方说你想要研究 [[Bashicu矩阵|BMS]]，那么理论上你只需要保证它大于 BMS 极限就可以了。但是我们的研究是永无止境的，因此普遍使用非递归序数这一大于所有递归序数的东西来充当 <math>\Omega</math>。''

==== 直观理解与操作规则 ====
让我们从 <math>\psi(0)=1</math> 开始。

BOCF 有这样的性质：

<math>\psi(m+1)=\psi(m)\times\omega</math>，m 是任意序数。

因此，可以得到 <math>\psi(1)=\omega</math>。得到之后，你对 <math>\psi(1)</math> 之前的序数已经很清楚了，于是，可以把这些序数也都放进 <math>\psi</math> 函数内部，于是，你最大能得到 <math>\psi(\psi(1))=\psi(\omega)=\omega^{\omega}</math>。得到它之后，你又对它之前的序数很清楚了，于是又可以把它们也放进 <math>\psi</math> 函数内部，最大能得到 <math>\psi(\psi(\psi(1)))=\omega^{\omega^{\omega}}</math>……以此类推，你可以得到嵌套任意多层的 <math>\psi(\psi(\psi(\cdots)))</math>。

这个时候，我们的新朋友 <math>\Omega</math> 出场了。我们令 <math>\psi(\Omega)=\psi(\psi(\psi(\cdots)))</math>，于是我们可以继续：<math>\psi(\Omega+1)=\psi(\Omega)\times\omega</math>。现在你会发现，它内部既然可以加一，那是不是也可以加上更大的序数呢？答案是肯定的。你先前已经得到了 <math>\psi(\Omega)</math>，那么对它之前的序数已经清楚了。于是只需要重走一遍 1 到 <math>\psi(\Omega)</math> 的路，就可以得到 <math>\psi(\Omega+\psi(\Omega))</math>。和前面类似的，得到 <math>\color{red}\psi(\Omega+\psi(\Omega))</math> 后，也就可以理解 <math>\psi(\Omega+{\color{red}\psi(\Omega+\psi(\Omega))})</math>，毕竟只是在 <math>\psi</math> 内重走一遍先前走过的路。上面的路又可以一直走下去，直到 <math>\psi(\Omega+\psi(\Omega+\psi(\Omega+\cdots)))</math>。

于是，<math>\Omega</math> 再次登场，它让 <math>\psi(\Omega+\psi(\Omega+\psi(\Omega+\cdots)))=\psi(\Omega+\Omega)=\psi(\Omega\times2)</math>。我们又可以按先前的思路，首先得到 <math>\psi(\Omega\times2+1)=\psi(\Omega\times2)\times\omega</math>，然后重走一遍 1 到 <math>\psi(\Omega\times2)</math> 的路，就得到 <math>\psi(\Omega\times2+\psi(\Omega\times2))</math>；再重走一遍 <math>\psi(\Omega\times2)</math> 到 <math>\psi(\Omega\times2+\psi(\Omega\times2))</math> 的路，就得到 <math>\psi(\Omega\times2+\psi(\Omega\times2+\psi(\Omega\times2)))</math>，再以此类推，得到 <math>\psi(\Omega\times2+\psi(\Omega\times2+\psi(\Omega\times2+\cdots)))</math> 后再把它变成 <math>\psi(\Omega\times3)</math>，然后再……

说到这里，读者应该对 <math>\Omega</math> 有一定的认识了。它的“能力”是让'''包着它的一层'''<math>\psi</math> 函数连同内部的其他内容一起嵌套 n 层。如 <math>\psi(\Omega\times3)=\psi(\Omega\times2+\Omega)=\psi(\Omega\times2+\psi(\Omega\times2+\psi(\Omega\times2+\cdots)))</math>。细心的读者可能注意到，这其实是[[不动点]]的体现。没错，OCF 中的 <math>\Omega</math> 可以说是不动点的“化身”，只要它出现，就一定是代表了一个不动点。事实上，前文只展示了加法。<math>\Omega</math> 对于乘法和乘方所做的事情和加法是如出一辙的，以下是例子：

得到 <math>\psi(\Omega\times\omega)</math>，理解加一个 <math>\Omega</math> 起到什么作用之后，只需要重走一遍 <math>\omega</math> 到 <math>\psi(\Omega)</math> 的路，就能得到 <math>\psi(\Omega\times\psi(\Omega))</math>，然后再重走一遍 <math>\psi(\Omega)</math> 到 <math>\psi(\Omega\times\psi(\Omega))</math> 的路，就能得到 <math>\psi(\Omega\times\psi(\Omega\times\psi(\Omega)))</math>……最后得到 <math>\psi(\Omega^2)=\psi(\Omega\times\Omega)=\psi(\Omega\times\psi(\Omega\times\psi(\Omega\times\cdots)))</math>。

得到 <math>\psi(\Omega^3)</math>，理解加一个 <math>\Omega^2</math> 起到什么作用之后，只需要重走一遍 1 到 <math>\psi(\Omega^3)</math> 的路，就能从 <math>\psi(\Omega^3+\Omega^2\times1)</math> 开始得到 <math>\psi(\Omega^3+\Omega^2\times\psi(\Omega^3))</math>，然后再重走一遍 <math>\psi(\Omega^3)</math> 到 <math>\psi(\Omega^3+\Omega^2\times\psi(\Omega^3))</math> 的路，就能得到 <math>\psi(\Omega^3+\Omega^2\times\psi(\Omega^3+\Omega^2\times\psi(\Omega^3)))</math>……最后得到 <math>\psi(\Omega^3\times2)=\psi(\Omega^3+\Omega^2\times\Omega)=\psi(\Omega^3+\Omega^2\times\psi(\Omega^3+\Omega^2\times\psi(\Omega^3+\Omega^2\times\cdots)))</math>。

得到<math>\psi(\Omega^{\Omega^{\Omega}})</math> 和 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^1})</math>，只需要重走一边 1 到 <math>\psi(\Omega^{\Omega^{\Omega}})</math> 的路，就能从 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^1})</math> 开始得到 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}})}})</math>，然后再重走一遍 <math>\psi(\Omega^{\Omega^{\Omega}})</math> 到 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}})}})</math> 路，就能得到 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}})}})}})</math>……最后得到 <math>\psi(\Omega^{\Omega^{\Omega}\times2})=\psi(\Omega^{\Omega^{\Omega}+\Omega^{\Omega}})=\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}+\Omega^{\psi(\Omega^{\Omega^{\Omega}+\Omega^{\cdots}})}})}})</math>。

以下是 [[BHO]]（即 <math>\psi(\Omega^{\Omega^{\Omega^{\cdots}}})</math>）之前的 BOCF 的操作规则：

* <math>\psi(\alpha_1)+\psi(\alpha_2)+\cdots+\psi(\alpha_{n-1})+\psi(0)=\psi(\alpha_1)+\psi(\alpha_2)+\cdots+\psi(\alpha_{n-1})+1</math>
* <math>(\psi(\alpha_1)+\psi(\alpha_2)+\cdots+\psi(\alpha_{n-1})+\psi(\alpha_n))[m]=\psi(\alpha_1)+\psi(\alpha_2)+\cdots+\psi(\alpha_{n-1})+\psi(\alpha_m)[m]</math>
* <math>\psi(X+1)[m]=\psi(X)\times m</math>
* <math>\psi(X+\psi(Y))[m]=\psi(X+\psi(Y)[m])</math>

这四条和康托范式的规则是一样的，主要是要找准表达式最右侧的结构。如果最右侧是外面的 1 那就是后继，最右侧是 <math>\psi</math> 里面的 1 那就是乘 <math>\omega</math>。最右侧如果是 <math>\psi(X)</math>，则先操作它。

但如果最右侧是 <math>\Omega</math> 呢？很简单，只需要找到包着它的那一层 <math>\psi</math>，然后在原位嵌套即可。即：

<math>\psi(Z\sim\Omega)=\psi(Z\sim\psi(Z\sim\psi(Z\sim\cdots)))</math>，其中 ~ 是 + 或者 × 或者 ^。注意这里的 Z 并不一定是一个序数，它可以只是一个算式。比如说 <math>\psi(\Omega^{\Omega^{\Omega}+\Omega^{\Omega}})</math> 对应的 Z 是<math>\psi({\color{red}\Omega^{\Omega^{\Omega}+\Omega^{\color{black}\Omega}}})</math> 标红的部分。

有的时候最右侧的 <math>\Omega</math> 被藏起来，你需要自己去挖掘出来。比方说 <math>\psi(\Omega^3\times2)</math>，你需要把它写成 <math>\psi(\Omega^3+\Omega^2\times\Omega)</math> 这种形式。

''tips：BOCF 中实际上并不存在乘法和乘方，因此上文的大部分式子严格来说是不标准的。但是在 googology 绝大多种情况下，为了方便和清晰性，我们都会用这种“部分”引入乘法和乘方的 BOCF 不标准式。''

BHO 之上，就需要引入更多的非递归序数 <math>\Omega_2,\Omega_3,\Omega_4,\cdots</math>。对于他们来说，有 <math>\psi_1</math> 函数，<math>\psi_2</math> 函数，<math>\psi_3</math> 函数……分别对应，<math>\Omega_{m+1}</math> 和 <math>\psi_m</math> 函数之间的关系与 Ω 和 ψ 函数的关系是一模一样的。（<math>\psi</math> 函数即 <math>\psi_0</math> 函数，<math>\Omega</math> 即 <math>\Omega_1</math>）

对于 <math>\psi_m</math> 函数，有如下规则：

* <math>\psi_m(0)=\Omega_m</math>
* <math>\psi_m(X+1)=\psi_m(X)\times\omega</math>
* <math>\psi_m(Y\sim\Omega_{m+1})=\psi_m(Y\sim\psi_m(Y\sim\psi_m(Y\sim\cdots)))</math>

不难发现和 <math>\psi</math> 函数的操作规则几乎一模一样。

比如说，有 <math>\psi_1(0)=\Omega</math>，<math>\psi_1(1)=\Omega\times\omega</math>,<math>\psi_1(\psi_1(0))=\Omega^2</math>,<math>\psi_1(\psi_1(0)\times2)=\Omega^3</math>,<math>\psi_1(\psi_1(\psi_1(0)))=\Omega^{\Omega}</math> 等等。最后会得到 <math>\psi_1(\Omega_2)=\psi_1(\psi_1(\psi_1(\cdots)))=\Omega^{\Omega^{\Omega^{\cdots}}}</math>。借助 <math>\psi_1</math> 函数，我们确实突破了前面 BHO 的界限。但事情还没这么简单。

因为 OCF 存在一个“藏层”现象。即，<math>\psi(\psi_1(\Omega_2))</math> 这样的式子是不标准的，它等价于 <math>\psi(\Omega_2)</math>。相当于那个 <math>\psi_1</math> 的层被“藏起来”了，因此称为藏层。

根据前文所说，<math>\Omega_n</math> 是一定要找 <math>\psi_{n-1}</math> 函数去嵌套的。那么，面对藏层，我们要如何操作呢？

答案是，找到包着 <math>\Omega_n</math> 的最近的 <math>\psi_m</math> 函数满足 <math>m < n</math>，我们视作 <math>\psi_{n-1}</math> 函数被藏在了这个 <math>\psi_m</math> 内部。随后进行嵌套，但要在嵌套过程中把内部的 <math>\psi_m</math> 改成 <math>\psi_{n-1}</math>，即：

<math>\psi_m(Y\sim\Omega_n)=\psi_m(Y\sim\psi_{n-1}(Y\sim\psi_{n-1}(Y\sim\cdots)))</math>

举例，考虑 <math>\psi(\Omega_3+\psi_2(\Omega_3+\Omega_2))</math>，最右端是 <math>\Omega_2</math>，它要找一个最近的 <math>\psi_n</math> 函数满足 n<2，是最外层的 ψ 函数。于是我们按照操作规则得到展开式为 <math>\psi(\Omega_3+\psi_2(\Omega_3+\psi_1(\Omega_3+\psi_2(\Omega_3+\psi_1(\Omega_3+\psi_2(\Omega_3+\cdots))))))</math>。

BO 是 <math>\psi(\Omega_{\omega})</math>，它的[[基本列]]是 <math>\{\psi(0),\psi(\Omega),\psi(\Omega_2),\psi(\Omega_3),\psi(\Omega_4),\cdots\}</math>。从这条基本列中的元素开始按照操作规则展开所得到的式子就是标准的，如果得不到，则是不标准的。

以上就是 BO 前的 BOCF 的直观理解与操作规则。

==== 枚举 ====
参见词条 [[BOCF VS veblen函数|BOCF VS Veblen 函数]]。

=== MOCF ===
下面是 MOCF 的数学定义：

# <math>C_0(x)=\{0,1,\omega,\Omega\}</math>
# <math>C_{n+1}(x)=\{\alpha+\beta,\alpha\times\beta,\alpha^\beta,\psi(\gamma)|\alpha,\beta,\gamma\in C_n(x)|\gamma<x\}</math>
# <math>C(x)=\bigcup_{n<\omega}C_n(x)</math>
# <math>\psi(x)=\min\{\alpha<\Omega|\alpha\notin C(x)\}</math>

可以发现，MOCF 和 BOCF 不同的点在于它把加法、乘法和乘方都放进了 <math>C(x)</math> 中，而 BOCF 只有加法。因此，MOCF 的 <math>\psi(0)=\varepsilon_0</math>，并且有 <math>\psi(X+1)=\psi(X)^{\psi(X)^{\psi(X)^{\cdots}}}</math>。在出现 <math>\Omega</math> 的地方，两种 OCF 是一样的，如平台期等概念，二者也是一样的。

下面是引入更多非递归序数的 MOCF 定义：

# <math>C_0^v(x)=\{\alpha|\alpha<\Omega_v\}\cup\{\Omega_{\beta}|\beta<\omega\}</math>
# <math>C_{n+1}^v(x)=\{\alpha+\beta,\alpha\times\beta,\alpha^\beta,\psi_{\delta}(\gamma)|\alpha,\beta,\gamma\in C_n^v(x),\gamma<x,\delta<\omega\}</math>
# <math>C^v(x)=\bigcup_{n<\omega}C_n^v(x)</math>
# <math>\psi_v(x)=\min\{\alpha<\Omega_{v+1}|\alpha\notin C^v(x)\}</math>

可以看到和 BOCF 的定义大差不差，唯一的区别是乘法和乘方的引入。因而操作规则无太大差异，除了 <math>\psi_v(X+1)=\psi_v(X)^{\psi_v(X)^{\psi_v(X)^{\cdots}}}</math>。此处不再赘述。

MOCF 的 <math>\psi(\Omega_\omega)</math> 也是 BO。

==== 枚举 ====
参见词条 [[BOCF VS MOCF]]。

=== BO之后 ===
<math>\psi(\Omega_{\omega})</math> 之后，googologist 们实际上已经不再关注其数学定义，因此这里只介绍操作规则。

BOCF 中，我们对每个后继序数 <math>\alpha+1</math> 对应的 <math>\Omega_{\alpha+1}</math> 都定义出 <math>\psi_{\alpha}</math> 函数满足 <math>\psi_{\alpha}(0)=\Omega_{\alpha}</math> 和 <math>\psi_{\alpha}(X+1)=\psi_{\alpha}(X)\times\omega</math>。MOCF 中则是 <math>\psi_{\alpha}(0)=\Omega_{\alpha}\uparrow\uparrow\omega</math> 和 <math>\psi_{\alpha}(X+1)=\psi_{\alpha}(X)\uparrow\uparrow\omega</math>。如果 β 是个极限序数，则没有对应的 <math>\psi</math> 函数。

那么，对于类似 <math>\Omega_{\Omega^{\Omega}}</math> 或 <math>\Omega_{\Omega_3\times3}</math> 的东西，又要如何处理呢？答案是把下标也看做一个运算，如 <math>\Omega_\Omega</math> 被看做Ω<sub>Ω</sub>。展开过程中找最右侧的 <math>\Omega_\alpha</math> 时找的是下标的 <math>\Omega</math> 而非整体的 <math>\Omega_\Omega</math>。换句话说，“找最右侧的 <math>\Omega_\alpha</math>”本身就要求 α 一定小于 <math>\Omega</math>。

以下是补充的操作规则：

<math>\psi(X\sim\Omega_{\alpha+1})[m]=\underbrace{\psi(X\sim\psi_\alpha(X\sim\psi_\alpha(X\sim\psi_\alpha(X\sim\cdots}_{m~layers}))))</math>，α 为任意序数，~ 代表 + 或 × 或 ^ 或下标。

<math>\psi(X\sim\Omega_\beta)[m]=\psi(X\sim\Omega_{\beta[m]})</math>，如果 β 是极限序数。

这套规则可以一直运用到 <math>\psi(\Omega_{\Omega_{\Omega_{\cdots}}})</math>，这个序数称为 [[EBO]]。如果想要继续前进，就需要新的非递归序数了，它们会给出它们对应的折叠规则。具体则需要参见对应词条。

那么在这里，我们实际上可以说，OCF 本身是一个和[[增长层级]]类似的“壳子”，它们接受对应的非递归序数，然后输出大的递归序数。那么，为什么 OCF 没有像增长层级（如 FGH）一样占据 googology 的所有空间呢？有两方面原因。

第一方面，OCF 没有像增长层级一样具有非常明确的转化规则。googology 社区有一个“俗话”——1000 个人有 1001 种 [[递归马洛序数|Mahlo]] OCF。这种共识的缺乏是致命的。

第二方面，对于目前的 googology 爱好者来说，构造非递归序数的难度和构造其他类型序数记号，如 [[Beklemishev's Worm|Worm]] 型记号，相比，在难度上拉不开差距。不像 FGH 加序数记号对传统数阵记号的“降维打击”。而且，googology 爱好者普遍没有很强的数理逻辑或序数分析基础，难以理解和运用学界所构造的大可数序数。

但我还是希望，伴随着 googology 爱好者水平不断提高，有一天 OCF 加大非递归序数会占据 googology 的主流，而 Worm 型记号会像曾经的数阵记号一样被边缘化。如果是这样，那对于 googology 来说，就是不亚于 2014 年的大飞跃发展了。

== 定义 ==

=== MOCF ===
令 <math>\Omega_\alpha=\omega_\alpha^{\rm CK},\Omega_0=\omega</math>。

<math>\alpha</math> 的递归共尾度 <math>\mathrm{cf}(\alpha)</math> 定义为 <math>\alpha</math> 的递归的基本列的最小长度。

==== 含第一个非递归序数的 MOCF ====
含第一个非递归序数 <math>\Omega</math> 的 MOCF <math>\psi(\alpha)</math> 定义为利用 <math>0,1,\omega,\Omega</math>，所有的 <math>\psi(\beta)</math> 以及序数加法、乘法、乘方运算，经过任意有限次运算所不能构建的最小序数。特别地，上述定义中的 <math>\beta</math> 满足 <math>\beta<\alpha</math>，且是能够在有限次运算之中通过 <math>0,1,\omega</math> 进行加法、乘法、乘方运算，以及将这些序数放到 MOCF 之中所得到的序数。

以上的定义描述了含 <math>\Omega</math> 的 MOCF 的行为，其集合论定义可以表述如下：

# <math>C^0(\alpha)=\{0,1,\omega,\Omega\}</math>
# <math>C^{n+1}(\alpha)=\{\gamma+\delta,\gamma\cdot\delta,\gamma^\delta,\psi(\eta)|\gamma,\delta,\eta\in C^n(\alpha),\eta<\alpha)\}</math>
# <math>C(\alpha)=\bigcup_{n<\omega}C^n(\alpha)</math>
# <math>\psi(\alpha)=\min\{\beta|\beta\notin C(\alpha)\}</math>

==== 含自然数下标的 MOCF ====
含有 <math>\Omega_n</math> 的 MOCF 标准形式定义为：

# 如果 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，且各 <math>\alpha_i</math> 均为标准形式，则 <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> 也是标准形式。
# 如果 <math>\alpha<\Omega_n,\Omega_n^\beta>\beta</math>，且 <math>\alpha,\beta</math> 均为标准形式，则 <math>\Omega_n^\beta\cdot\alpha</math> 为标准形式。
# 如果 <math>\alpha\in C_n(\alpha)</math>，则 <math>\psi_n(\alpha)</math> 为标准形式。

含有自然数下标的 MOCF <math>\psi(\alpha)</math> 的基本列定义为：

# 若 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，则 <math>\mathrm{cf}(\alpha_1+\alpha_2+\cdots+\alpha_n)=\mathrm{cf}(\alpha_n)</math> 且 <math>(\alpha_1+\alpha_2+\cdots+\alpha_n)[\eta]=\alpha_1+\alpha_2+\cdots+\alpha_n[\eta]</math>
# <math>\mathrm{cf}(\psi_n(0))=\omega</math>，且 <math>\psi_n(0)[0]=\Omega_n,\psi_n(0)[n'+1]=\Omega_n^{\psi_n(0)[n']}</math>
# <math>\mathrm{cf}(\psi_n(\alpha+1))=\omega</math>，且 <math>\psi_n(\alpha+1)[0]=\psi(\alpha),\psi_n(\alpha+1)[n'+1]=\psi_n(\alpha)^{\psi_n(\alpha+1)[n']}</math>
# <math>\mathrm{cf}(\Omega_n)=\Omega_n</math>，且 <math>\Omega_n[\eta]=\eta</math>
# 若 <math>\mathrm{cf}(\alpha)\geqslant\omega</math>，则 <math>\mathrm{cf}(\Omega_n^\alpha)=\mathrm{cf}(\alpha)</math> 且 <math>(\Omega_n^\alpha)[\eta]=\Omega_n^{\alpha[\eta]}</math>
# 若 <math>\mathrm{cf}(\beta)\geqslant\omega</math>，则 <math>\mathrm{cf}(\Omega_n^\alpha\cdot\beta)=\mathrm{cf}(\beta)</math> 且 <math>(\Omega_n^\alpha\cdot\beta)[\eta]=\Omega_n^\alpha\cdot\beta[\eta]</math>
# <math>\mathrm{cf}(\Omega_n^\alpha\cdot(\beta+1))=\mathrm{cf}(\Omega_n^\alpha)</math>，且 <math>\Omega_n^\alpha\cdot(\beta+1)[\eta]=\Omega_n^\alpha\cdot\beta+\Omega^{\alpha[\eta]}</math>
# 若 <math>\mathrm{cf}(\alpha)=\Omega_n,m\leqslant n</math>，则 <math>\mathrm{cf}(\psi_m(\alpha))=\mathrm{cf}(\alpha)</math> 且 <math>\psi_n(\alpha)[\eta]=\psi_n(\alpha[\eta])</math>
# 若 <math>\mathrm{cf}(\alpha)=\Omega_{n+1},m\leqslant n</math>，则 <math>\mathrm{cf}(\psi_m(\alpha))=\omega</math> 且 <math>\psi_m(\alpha)[n']=\psi_m(\alpha[\gamma[n']])</math>，其中 <math>\gamma[0]=0,\gamma[n'+1]=\psi_n(\alpha[\gamma[n']])</math>

含有自然数下标的 MOCF <math>\psi_n(\alpha)</math> 定义为利用所有小于 <math>\Omega_n</math> 的序数、所有自然数下标的 <math>\Omega_m</math>，所有自然数下标的 <math>\psi_m(\beta)</math> 以及序数加法、乘法、乘方运算，经过任意有限次运算所不能构建的最小序数。特别地，上述定义中的 <math>\beta</math> 满足 <math>\beta<\alpha</math>，且是能够在此前的运算之中得到的序数。

以上的定义描述了含自然数下标的 MOCF 的行为，其集合论定义可以表述如下：

# <math>C_n^0(\alpha)=\{\xi|\xi<\Omega_n\}\cup\{\Omega_{n'}|n'\in\mathbb{N}\}</math>
# <math>C_n^{m+1}(\alpha)=\{\gamma+\delta,\gamma\cdot\delta,\gamma^\delta,\psi_{n'}(\eta)|\gamma,\delta,\eta\in C_n^m(\alpha),n'\in\mathbb{N},\eta<\alpha)\}</math>
# <math>C_n(\alpha)=\bigcup_{m\in\mathbb{N}}C_n^m(\alpha)</math>
# <math>\psi_n(\alpha)=\min\{\beta|\beta\notin C_n(\alpha)\}</math>

==== 含序数下标的 MOCF ====
含有 <math>\Omega_\mu</math> 的 MOCF 标准形式定义为：

# 如果 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，且各 <math>\alpha_i</math> 均为标准形式，则 <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> 也是标准形式。
# 如果 <math>\alpha<\Omega_\mu,\Omega_\mu^\beta>\beta</math>，且 <math>\alpha,\beta,\mu</math> 均为标准形式，则 <math>\Omega_\mu^\beta\cdot\alpha</math> 为标准形式。
# 如果 <math>\alpha\in C_\mu(\alpha)</math>，则 <math>\psi_\mu(\alpha)</math> 为标准形式。

含有序数下标的 MOCF <math>\psi(\alpha)</math> 的基本列定义为：

# 若 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，则 <math>\mathrm{cf}(\alpha_1+\alpha_2+\cdots+\alpha_n)=\mathrm{cf}(\alpha_n)</math> 且 <math>(\alpha_1+\alpha_2+\cdots+\alpha_n)[\eta]=\alpha_1+\alpha_2+\cdots+\alpha_n[\eta]</math>
# <math>\mathrm{cf}(\psi_\nu(0))=\omega</math>，且 <math>\psi_\nu(0)[0]=\Omega_n,\psi_\nu(0)[n+1]=\Omega_\nu^{\psi_\nu(0)[n]}</math>
# <math>\mathrm{cf}(\psi_\nu(\alpha+1))=\omega</math>，且 <math>\psi_\nu(\alpha+1)[0]=\psi(\alpha),\psi_\nu(\alpha+1)[n+1]=\psi_\nu(\alpha)^{\psi_\nu(\alpha+1)[n]}</math>
# <math>\mathrm{cf}(\Omega_{\mu+1})=\Omega_{\mu+1}</math>，且 <math>\Omega_n[\eta]=\eta</math>
# 若 <math>\mathrm{cf}(\alpha)\geqslant\omega</math>，则 <math>\mathrm{cf}(\Omega_\mu^\alpha)=\mathrm{cf}(\alpha)</math> 且 <math>(\Omega_\mu^\alpha)[\eta]=\Omega_\mu^{\alpha[\eta]}</math>
# 若 <math>\mathrm{cf}(\beta)\geqslant\omega</math>，则 <math>\mathrm{cf}(\Omega_\mu^\alpha\cdot\beta)=\mathrm{cf}(\beta)</math> 且 <math>(\Omega_\mu^\alpha\cdot\beta)[\eta]=\Omega_\mu^\alpha\cdot\beta[\eta]</math>
# <math>\mathrm{cf}(\Omega_\mu^\alpha\cdot(\beta+1))=\mathrm{cf}(\Omega_\mu^\alpha)</math>，且 <math>\Omega_\mu^\alpha\cdot(\beta+1)[\eta]=\Omega_\mu^\alpha\cdot\beta+\Omega^{\alpha[\eta]}</math>
# 若 <math>\mathrm{cf}(\alpha)=\Omega_\mu,\mu\leqslant\nu</math>，则 <math>\mathrm{cf}(\psi_\mu(\alpha))=\mathrm{cf}(\alpha)</math> 且 <math>\psi_\nu(\alpha)[\eta]=\psi_\nu(\alpha[\eta])</math>
# 若 <math>\mathrm{cf}(\alpha)=\Omega_{\mu+1},\mu\leqslant\nu</math>，则 <math>\mathrm{cf}(\psi_\mu(\alpha))=\omega</math> 且 <math>\psi_\mu(\alpha)[n]=\psi_\mu(\alpha[\gamma[n]])</math>，其中 <math>\gamma[0]=0,\gamma[n+1]=\psi_\nu(\alpha[\gamma[n]])</math>

含有序数下标的 MOCF <math>\psi_\nu(\alpha)</math> 定义为利用所有小于 <math>\Omega_\nu</math> 的序数、所有自然数下标的 <math>\Omega_\mu</math>，所有自然数下标的 <math>\psi_\mu(\beta)</math> 以及序数加法、乘法、乘方运算，经过任意有限次运算所不能构建的最小序数。特别地，上述定义中的 <math>\beta</math> 满足 <math>\beta<\alpha</math>，且是能够在此前的运算之中得到的序数。

以上的定义描述了含序数下标的 MOCF 的行为，其集合论定义可以表述如下：

# <math>C_\nu^0(\alpha)=\{\xi|\xi<\Omega_\nu\}\cup\{\Omega_{\mu}|\mu\in\mathbb{N}\}</math>
# <math>C_\nu^{m+1}(\alpha)=\{\gamma+\delta,\gamma\cdot\delta,\gamma^\delta,\psi_\mu(\eta)|\gamma,\delta,\eta\in C_\nu^m(\alpha),\mu\in\mathbb{N},\eta<\alpha)\}</math>
# <math>C_\nu(\alpha)=\bigcup_{m\in\mathbb{N}}C_\nu^m(\alpha)</math>
# <math>\psi_\nu(\alpha)=\min\{\beta|\beta\notin C_\nu(\alpha)\}</math>

=== BOCF ===
含有 <math>\Omega_\mu</math> 的 BOCF 标准形式定义为：

# 如果 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，且各 <math>\alpha_i</math> 均为标准形式，则 <math>\alpha=\alpha_1+\alpha_2+\cdots+\alpha_n</math> 也是标准形式。
# 如果 <math>\mu</math>，则 <math>\Omega_\mu</math> 为标准形式。
# 如果 <math>\alpha\in C_\mu(\alpha)</math>，则 <math>\psi_\mu(\alpha)</math> 为标准形式。

含有序数下标的 BOCF <math>\psi(\alpha)</math> 的基本列定义为：

# 若 <math>\alpha_1\geqslant\alpha_2\geqslant\cdots\geqslant\alpha_n</math>，则 <math>\mathrm{cf}(\alpha_1+\alpha_2+\cdots+\alpha_n)=\mathrm{cf}(\alpha_n)</math> 且 <math>(\alpha_1+\alpha_2+\cdots+\alpha_n)[\eta]=\alpha_1+\alpha_2+\cdots+\alpha_n[\eta]</math>
# <math>\psi(0)=1</math>
# <math>\mathrm{cf}(\psi_{\nu+1}(0))=\mathrm{cf}(\Omega_{\nu+1})</math>，且 <math>\psi_{\nu+1}(0)[\eta]=\eta</math>
# 若 <math>\mathrm{cf}(\nu)\geqslant\omega</math>，则 <math>\mathrm{cf}(\psi_\nu(0))=\mathrm{cf}(\nu)</math>，且 <math>\psi_\nu(0)[\eta]=\psi_{\nu[\eta]}(0)</math>
# <math>\mathrm{cf}(\psi_\nu(\beta+1))=\omega</math>，且 <math>\psi_\nu(\beta+1)[0]=0,\psi_\nu(\beta+1)[n+1]=\psi_\nu(\beta+1)[n]+\psi_\nu(\beta)</math>
# 若 <math>\mathrm{cf}(\beta)\in\{\omega\}\cap\{\Omega_{\mu+1}|\mu<\nu\}</math>，则 <math>\mathrm{cf}(\psi_\nu(\beta))=\mathrm{cf}(\beta)</math>，且 <math>\psi_\nu(\beta)[\eta]=\psi_\nu(\beta[\eta])</math>
# 若 <math>\mathrm{cf}(\alpha)=\Omega_{\mu+1},\mu\geqslant\nu</math>，则 <math>\mathrm{cf}(\psi_\nu(\beta))=\omega</math> 且 <math>\psi_\nu(\beta)[n]=\psi_\nu(\beta[\gamma[n]])</math>，其中 <math>\gamma[0]=\Omega_\mu,\gamma[n+1]=\psi_\mu(\alpha[\gamma[n]])</math>

其集合论定义可以表述如下：

# <math>C_\nu^0(\alpha)=\{\xi|\xi<\Omega_\nu\}</math>
# <math>C_\nu^{m+1}(\alpha)=\{\gamma+\delta,\psi_\mu(\eta)|\gamma,\delta,\eta\in C_\nu^m(\alpha),\mu\in\bold{Ord},\eta<\alpha)\}</math>
# <math>C_\nu(\alpha)=\bigcup_{m\in\mathbb{N}}C_\nu^m(\alpha)</math>
# <math>\psi_\nu(\alpha)=\min\{\beta|\beta\notin C_\nu(\alpha)\}</math>

[[分类:记号]]
[[分类:入门]]

序数

2025-07-27T04:54:16Z

Zhy137036：

'''序数'''是自然数的推广。

=== 直观理解 ===
顾名思义，序数是用来排序的号码。最小的序数是 0，因而我们从 0 开始排序。这只是一个很简单的排序，还没有超过自然数的范畴。

现在考虑对这个集合 <math>\{ 1/2,3/4,7/8,\ldots \} \cup \{1\}</math>，按照＜来排序：
{| class="wikitable"
|+
!号码
!元素
|-
|1/2
|0
|-
|3/4
|1
|-
|7/8
|2
|-
|……
|……
|-
|1
|？
|}
注意到当我们为 1/2,3/4,7/8,…… 这些元素排序时，已经用尽了全部的自然数。但我们又要为 1 编号。1 大于前面的所有元素，因此，1 的号码需要是一个大于全体自然数的东西。它依然是序数（因为我们定义序数就是为了处理这种情况），我们给它命名为 ω。

想象一下我们在此基础上又要给 <math>\{3/2,7/4,15/8,\ldots\}\cup\{2\}</math> 编号。因此我们还需要越来越多的大于ω的序数。随着“编号游戏”的对象愈发复杂，我们所需要的序数也愈发庞大，复杂，单纯靠直观理解已经难以为继，因此我们需要看以下的内容。

=== 数学定义 ===
序数是在∈序上[[良序]]的传递集（传递集即满足每个元素都是自身的子集）。如：

<math>0=\varnothing=\{\}</math>

<math>1=\{ 0\}</math>

<math>2=\{0,1\}</math>

<math>3=\{0,1,2\}</math>

<math>1048576=\{0,1,2,3,...,1048575\}</math>

==== 序数的后继 ====
序数 <math>\alpha</math> 的'''后继'''被定义为 <math>\alpha+1=\alpha\cup \{\alpha\}</math>。它也是所有'''序数运算'''的基础。

如 <math>2+1=2\cup\{2\}=\{0,1\}\cup\{2\}=\{0,1,2\}=3</math>，<math>n+1=n\cup\{n\}=\{0,1,2,3,...,n\}</math>。

==== 有限序数与超限序数 ====
所有自然数都是有限序数。

大于任意有限序数的序数称作'''超限序数'''（或无限序数）。

==== 极限序数 ====
不是 0 且'''不是任何序数的后继'''的序数被称为'''极限序数'''。（0 有时也被视为极限序数）

即序数 <math>\lambda</math> 是极限序数要满足“不存在某个序数 <math>\alpha</math> 使得 <math>\lambda=\alpha +1</math>”。

如果 <math>\lambda</math> 是极限序数，那么 <math>\lambda=\sup\{\alpha|\alpha < \lambda\}</math>。

<math>\omega</math> 被定义为全体自然数的集合，<math>\omega=\mathbb{N}=\{0,1,2,3,...\}</math> 既是第一个超限序数，也是第一个极限序数。

==== 基本列 ====
如果序数 <math>\alpha</math> 是一个极限序数，则它的基本列 <math>\langle \alpha[n] \rangle </math> 是一个递增的序数列，并且满足其上确界为 <math>\alpha</math>。即 <math>\alpha={\rm sup}\{\alpha[n]|n\in \mathbb{N}\}={\rm sup}\{\alpha[0],\alpha[1],\alpha[2],...\}</math>。

注意到一个极限序数具有多种基本列。因此为了方便运用和理解，我们需要一套标准基本列系统来给极限序数一个唯一的基本列。

很遗憾的是，不存在一个通用的基本列系统来为所有序数指定标准基本列。因此，我们只能借助[[序数记号]]来为它极限之下的极限序数指定标准基本列。

==== 递归序数与非递归序数 ====

===== 递归序数 =====
一个序数 <math>\alpha</math> 被称为递归序数，当且仅当存在一个图灵机（或等效的可计算函数，或图灵完备的计算机语言），它能计算出一个良序关系 <math>\prec</math>，使得这个良序关系的序型与 <math>\alpha</math> 同构。

直观来讲，递归序数都是可以“自下而上”得到的序数。

所有递归序数的集合也是一个序数，记为 <math>\omega_1^{\rm CK}</math>（又作 <math>\Omega</math>，[[CKO]]）

<math>\omega_1^{\rm CK}=\{0,1,...,\omega,...,\omega^2,...,\omega^\omega,...,\varepsilon_0,...,\varphi(1,0,0),...,\psi(\Omega_{\omega}),...\}</math>

由于图灵机的总数是可数无穷多的，因此 <math>\Omega</math> 依然是一个可数序数。

===== 非递归序数 =====
不是递归序数的序数被称为非递归序数。

最小的非递归序数就是所有递归序数的集合 <math>\omega_1^{\rm CK}</math>。

==== 可数序数与不可数序数 ====
如果一个序数与有限基数或 <math>\aleph_0</math> 等势，则它是可数序数。如 <math>0,1,2,\omega,\varepsilon_0,\psi(\Omega_{\omega}),Y(1,3),\Omega,I,\psi_{\alpha}(\alpha_{\omega}),\omega_1^L</math> 等等都是可数序数。

不是可数序数的序数是不可数序数，如 <math>\omega_1</math>。

=== 序数的运算 ===

==== 序数加法 ====
<math>\alpha+0=\alpha</math>

<math>\alpha+(\beta+1)=(\alpha+\beta)+1</math>

<math>\alpha+\beta=\bigcup_{\gamma <\beta}(\alpha +\gamma)</math>，如果 <math>\beta</math> 是极限序数。

序数加法不具有交换律，但具有结合律。即

<math>\alpha+\beta\ne\beta+\alpha,(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)</math>

例：<math>1+\omega=\bigcup_{\gamma <\omega}(1 +\gamma)=\{1+0,1+1,1+2,...\}={\rm sup}\{1,2,3,...\}=\omega\ne \omega+1</math>

==== 序数乘法 ====
<math>\alpha\times0=0</math>

<math>\alpha\times(\beta+1)=(\alpha\times\beta)+\alpha</math>

<math>\alpha\times\beta=\bigcup_{\gamma <\beta}(\alpha \times\gamma)</math>，如果 <math>\beta</math> 是极限序数。

序数乘法不具有交换律和右分配律，但具有结合律和左分配律。即

<math>1.\alpha\times\beta\ne\beta\times\alpha,(\alpha\times\beta)\times\gamma=\alpha\times(\beta\times\gamma)</math>

<math>2.(\alpha+\beta)\times\gamma\ne (\alpha\times\gamma)+(\beta\times\gamma), \alpha\times(\beta+\gamma)=(\alpha\times\beta)+(\alpha\times\gamma)</math>

例：

<math>\begin{align} (\omega+1)\times\omega&=\bigcup_{\gamma <\omega}((\omega+1) \times\gamma)\\&=\{(\omega+1)\times0,(\omega+1)\times1,(\omega+1)\times2,...\}\\&=\{0,\omega+1,\omega+(1+\omega)+1,\omega+(1+\omega)+(1+\omega)+1,...\}\\&={\rm sup}\{ 0,\omega+1,\omega\times2+1,\omega\times3+1,...\}=\omega^2 \\&\ne\omega\times(\omega+1)=\omega^2+\omega \end{align}</math>

'''Q:'''为什么不是<math>\omega^2+1</math>？

A: 我们知道<math>\omega^2+1=\omega^2\cup\{\omega^2\}=\{0,1,2,...,\omega,\omega+1,...,\omega\times2,...,\omega\times3,...,\omega^2\}</math>

而 <math>\bigcup_{\gamma <\omega}(\omega\times\gamma +1)</math> 中显然没有任何一个元素能够达到或是超过 <math>\omega^2</math>，因此它们的上确界也不会超过 <math>\omega^2</math>。

其实也可以换一个方向思考：既然 <math>{\rm sup}\{ \omega,\omega\times2,\omega\times3,...\}=\omega^2</math>

而 <math>{\rm sup}\{ 0,\omega+1,\omega\times2+1,\omega\times3+1,...\}</math> 中从小到大排列的每一项都比前者小，因此也不会超过 <math>\omega^2</math>。

==== 序数的指数运算 ====
<math>\alpha^0=1</math>

<math>\alpha^{\beta+1}=\alpha^\beta\times\alpha</math>

<math>\alpha^\beta=\bigcup_{\gamma <\beta}(\alpha^\gamma)</math>，如果 <math>\beta</math> 是极限序数。

序数的指数不具有对底数乘法的分配律，但指数加法具有对底数的分配律。即

<math>(\alpha\times\beta)^\gamma\ne\alpha^\gamma\times\beta^\gamma,\alpha^{\beta+\gamma}=\alpha^\beta\times\alpha^\gamma</math>

例：

<math>\begin{align} (2\times3)^\omega &=6^\omega=\bigcup_{\gamma <\omega}(6^\gamma)=\{6^0,6^1,6^2,... \}={\rm sup}\{1,6,36,... \}=\omega \\&\ne 2^\omega\times3^\omega=\bigcup_{\gamma <\omega}(2^\gamma)\times\bigcup_{\gamma <\omega}(3^\gamma)=\omega\times\omega=\omega^2 \end{align}</math>

<math>\varepsilon_0</math> 是第一个满足 <math>\omega^\alpha=\alpha</math> 的不动点。

<math>\omega^{\varepsilon_0}=\bigcup_{\gamma <\varepsilon_0}(\omega^\gamma)={\rm sup}\{1,\omega,\omega^2,...,\omega^\omega,...,\omega^{\omega^\omega},...\}=\varepsilon_0</math>

<math>\varepsilon_0\times\omega=\omega^{\varepsilon_0}\times\omega=\omega^{\varepsilon_0+1}</math>

=== 形式化定义 ===
'''序数和序数类'''

一个集合 <math>\alpha</math> 称为序数，当且仅当它满足以下条件：

* 传递性： <math>\alpha</math> 的每个元素都是其子集（<math>\forall\beta\in\alpha,\beta\subseteq\alpha</math>）
* 全序性：<math>\alpha</math> 上的关系 <math>\in</math> 是全序关系（<math>\forall\beta,\gamma\in\alpha,(\beta\in\gamma)\lor(\beta=\gamma)\lor(\beta\ni\gamma)</math>）
* 良基性：每个非空子集 <math>S\subseteq\alpha</math> 有最小元（<math>\exists\beta\in S(\forall\gamma\in S,\beta\notin\gamma)</math>）

等价地，序数可定义为良序集的序型，即与某个良序集同构的最小序数。

序数类是所有序数的总体，是一个真类，即：<math>\bold{On}\equiv\{\alpha|\alpha\text{ 是序数}\}</math>

其中，序数的成员关系满足以下性质：

* 三歧性：<math>\forall\alpha,\beta\in\bold{On},(\alpha\in\beta)\lor(\alpha=\beta)\lor(\alpha\ni\beta)</math>
* 传递性：<math>((\alpha\in\bold{On})\land(\beta\in\alpha))\rightarrow(\beta\in\bold{On})</math>
* 良序性：On 上的关系 ∈ 是良序的，即每个非空子类有最小元

'''后继序数和极限序数'''

一个序数 <math>\alpha</math> 称为后继序数，当且仅当存在序数 <math>\beta</math> 使得 <math>\alpha=\beta+1</math>（<math>\alpha\text{ 是后继序数}\Longleftrightarrow\exists\beta\in\bold{On}(\alpha=\beta+1)</math>）

一个序数 <math>\alpha</math> 称为后继序数，当且仅当不存在序数 <math>\beta</math> 使得 <math>\alpha=\beta+1</math>（<math>\alpha\text{ 是极限序数}\Longleftrightarrow\neg\exists\beta\in\bold{On}(\alpha=\beta+1)</math>）

'''递归函数'''

一个部分函数 <math>f:\omega\rightarrow\omega</math> 称为递归函数，当且仅当存在图灵机 <math>M</math> 满足：对任意 <math>n\in\omega</math>，

* 若 <math>n\in\text{dom}(f)</math>，则 <math>M</math> 在输入 <math>n</math> 时会在有限步内停机，并输出 <math>f(n)</math>；
* 若 <math>n\notin\text{dom}(f)</math>，则 <math>M</math> 在输入 <math>n</math> 时永不停机。

定义所有递归函数的类为 <math>\bold{Rec}_\text{f}</math>。

'''超限递归'''

设 <math>\beta</math> 是一个序数，<math>f:\omega\rightarrow\omega</math> 是一个递归函数。通过超限递归定义一个函数 <math>F:\bold{On}\rightarrow\bold{On}</math>，满足：

* 对后继序数 <math>\alpha=\gamma+1</math>，定义 <math>F(\alpha)=f(\langle\gamma,F(\gamma)\rangle)</math>；
* 对极限序数 <math>\alpha</math>，定义 <math>F(\alpha)=\sup\{F(\gamma)|\gamma<\alpha\}</math>。

定义 <math>F_f</math> 是由 <math>f</math> 定义的超限递归函数。

称 <math>\alpha</math> 是 <math>f</math> 相对于 <math>\beta</math> 的序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math>，使得 <math>\alpha=F(\beta)</math>（即 <math>\alpha</math> 是通过 <math>f</math> 在 <math>b</math> 处的超限递归生成的序数），其中 <math>F</math> 是通过 <math>f</math> 定义的超限递归函数。

称 <math>\alpha</math> 是递归在 <math>\beta</math> 上的序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math> 和序数 <math>\gamma<\beta</math>，使得 <math>\alpha=F_f(\gamma)</math>。

'''递归序数和非递归序数'''

一个序数 <math>\alpha</math> 称为递归序数，当且仅当存在递归函数 <math>f\in\bold{Rec}_\text{f}</math> 和序数 <math>\beta</math>，使得 <math>\alpha</math> 是 <math>f</math> 相对于 <math>\beta</math> 的序数（<math>\alpha\text{ 是递归序数}\Longleftrightarrow\exists f\in\bold{Rec}_\text{f}\ \exists\beta\in\bold{On}(\alpha=F_f(\beta))</math>）

递归序数类是所有递归序数的总体：<math>\bold{Rec}\equiv\{\alpha|\alpha\text{ 是递归序数}\}</math>

一个序数 <math>\alpha</math> 称为非递归序数，当且仅当它不是递归序数，即 <math>\alpha\text{ 是非递归序数}\Longleftrightarrow\alpha\in\bold{On}\land\alpha\notin\bold{Rec}</math>（<math>\alpha\text{ 是非递归序数}\Longleftrightarrow\neg\exists f\in\bold{Rec}_\text{f}\ \exists\beta\in\bold{On}(\alpha=F_f(\beta))</math>）

'''容许序数'''

一个序数 <math>\alpha</math> 称为容许序数，当且仅当构造宇宙 <math>L_\alpha</math> 满足 Kripke-Platek 集合论的公理。等价地，<math>\alpha</math> 是容许的当且仅当对任何递归在 <math>\alpha</math> 上的函数 <math>F:L_\alpha\rightarrow L_\alpha</math>，其定义域和值域都属于 <math>L_\alpha</math>（即 <math>\alpha</math> 对递归封闭）。

<math>\alpha\text{ 是容许序数}\Longleftrightarrow L_\alpha\vDash\bold{KP}</math>

'''Church-Kleene 序数（[[CKO]]）'''

<math>\omega_\alpha^\text{CK}</math> 序数通过超限递归定义：

* <math>\omega_0^\text{CK}=\omega</math>
* 对后继序数 <math>\alpha=\beta+1</math>，<math>\omega_\alpha^\text{CK}=\sup\{\alpha\in\bold{On}|\alpha\text{ 是递归在 }\omega_\beta^\text{CK}\text{ 上的序数}\}</math>
* 对极限序数 <math>\alpha</math>，<math>\omega_\alpha^\text{CK}=\sup\{\omega_\beta^\text{CK}|\beta<\alpha\}</math>

第一个非递归序数 <math>\omega_1^\text{CK}</math> 是所有递归序数的最小上界（即上确界），即：<math>\omega_1^\text{CK}=\sup\{\alpha\in\bold{On}|\alpha\in\bold{Rec}\}</math>，它是可数的最小非递归序数。

'''序数的基本列'''

对极限序数 <math>\lambda</math>，其基本列定义为递增序列 <math>\langle\lambda[\xi]\rangle_{\xi<\mu}</math>（<math>\mu</math> 为序数），满足： <math>\forall\xi<\mu,\lambda[\xi]<\lambda</math> 且 <math>\sup\{\lambda[\xi]|\xi<\mu\}=\lambda</math>。

若 <math>\lambda</math> 是正则序数（<math>\text{cf}(\lambda)=\lambda</math>），则 <math>\mu=\lambda</math>；若 <math>\lambda</math> 是奇异序数（<math>\text{cf}(\lambda)<\lambda</math>），则 <math>\mu=\text{cf}(\lambda)</math>。

[[分类:入门]]

[[分类:集合论相关]]

2025-07-24T12:40:39Z

Zhy137036：扽西内容来自Phyrion

用户讨论:Zhy137036

2025-07-10T09:10:56Z

Zhy137036：Zhy137036移动页面用户讨论:Zhy123456至用户讨论:Zhy137036，覆盖重定向：恢复

== 拜谢 ==

测试一下讨论页（） [[用户:Phyrion|Phyrion]]（[[用户讨论:Phyrion|留言]]） 2025年7月9日 (三) 20:58 (CST)

:拜谢 [[用户:Zhy137036|Zhy137036]]（[[用户讨论:Zhy137036|留言]]） 2025年7月9日 (三) 21:01 (CST)

用户:Zhy137036

2025-07-10T09:10:18Z

Zhy137036：Zhy137036移动页面用户:Zhy123456至用户:Zhy137036覆盖重定向，不留重定向：恢复

修格式可以找我，但不保证一定会修（

<math>\varepsilon_0</math> 以下的证明可以找我，但不保证会证（

用户讨论:Zhy137036

2025-07-10T09:09:04Z

Zhy137036：Zhy137036移动页面用户讨论:Zhy137036至用户讨论:Zhy123456：怎么改页面的标题