AOCF

Arai's Ordinal Collapse Function（AOCF）是一种类序数坍缩函数。

系统与公理

${\mathrm{\Sigma }}_{N+2}^1-\text{AC+BI}$ 表示一个二阶算术系统，它由 ​​${\mathrm{\Pi }}_{\mathrm{1}}^{\mathrm{1}}\mathrm{-}\mathrm{C}{\mathrm{A}}_{\mathrm{0}}\mathrm{+}\mathrm{B}\mathrm{I}$​​ 加入公理 ​​${\mathrm{\Sigma }}_{N+2}^1-\text{AC}$​​ 得到：$\mathrm{\forall }n\mathrm{\exists }XF(n,X)\to \mathrm{\exists }Y\mathrm{\forall }nF(n,Y_n)$，其中 $F(n,X)$ 是任意的 ​​${\mathrm{\Pi }}_{N+2}^1$-公式。

${\mathrm{\Sigma }}_{N+2}^1-\text{DC+BI}$ 表示一个二阶算术系统，它由 ​​${\mathrm{\Pi }}_{\mathrm{1}}^{\mathrm{1}}\mathrm{-}\mathrm{C}{\mathrm{A}}_{\mathrm{0}}\mathrm{+}\mathrm{B}\mathrm{I}$​​ 加入公理 ​​${\mathrm{\Sigma }}_{N+2}^1-\text{DC}$​​ 得到：$\mathrm{\forall }n\mathrm{\forall }X\mathrm{\exists }YF(n,X,Y)\to \mathrm{\forall }{X}_0\mathrm{\exists }Y\mathrm{\forall }n[Y_0=X_0\wedge F(n,Y_n,Y_{n+1})]$，其中 $F(n,X,Y)$ 是任意的 ${\mathrm{\Pi }}_{N+1}^1$​​-公式，$m\in Y_n\Rightarrow (n,m)\in Y$，且 $(\cdot ,\cdot )$ 是一个双射配对函数。容易看出，公理中的公式 $F$ 可以是 ${\mathrm{\Sigma }}_{N+2}^1$-公式。

集合论 ​​$\mathrm{K}\mathrm{P}\omega +{\mathrm{\Pi }}_N-\text{Collection}+(V=L)$ 的公理由 ​​$\mathrm{K}\mathrm{P}\omega$​​（带无穷公理的 Kripke-Platek 集合论）的公理加上以下公理组成：

• 可构成公理 ​​$V=L$

• ${\mathrm{\Pi }}_N-\text{Collection}$ 公理​​：对于任意 ​​${\mathrm{\Pi }}_N$-公式 $A(x,y)$，$\mathrm{\forall }x\in a\mathrm{\exists }yA(x,y)\to \mathrm{\exists }b\mathrm{\forall }x\in a\mathrm{\exists }y\in bA(x,y)$

• ${\mathrm{\Sigma }}_N-\text{Separation}$ 公理：对于任意 ​​${\mathrm{\Sigma }}_N$-公式 $\phi (x)$，$\mathrm{\exists }y\mathrm{\forall }x(x\in y\to x\in a\wedge \phi (x))$
• ${\mathrm{\Delta }}_{N+1}-\text{Separation}$ 公理：对于任意 ​​${\mathrm{\Sigma }}_{N+1}$​​-公式 $\phi (x)$ 和 $\psi (x)$，$\mathrm{\forall }x\in a(\phi (x)\to \mathrm{\neg }\psi (x))\to \mathrm{\exists }y\mathrm{\forall }x(x\in y\to x\in a\wedge \phi (x))$
• ${\mathrm{\Sigma }}_{N+1}-\text{Replacement}$ 公理：如果 $\mathrm{\forall }x\in a\mathrm{\exists }!y\phi (x,y)$，那么存在一个函数 $f$，其定义域 $\mathrm{d}\mathrm{o}\mathrm{m}(f)=a$，使得 $\mathrm{\forall }x\in a\phi (x,f(x))$ 对每个 ​​${\mathrm{\Sigma }}_{N+1}$​​-公式 $\phi (x,y)$ 成立。

${\mathrm{\Pi }}_N-\text{Collection}$ 公理​​

引理 2.1

引理 2.1​​ $\mathrm{K}\mathrm{P}\omega +{\mathrm{\Pi }}_N-\text{Collection}$ 可证以下每一条：

1. ${\mathrm{\Sigma }}_N-\text{Separation}$
2. ${\mathrm{\Delta }}_{N+1}-\text{Separation}$
3. ${\mathrm{\Sigma }}_{N+1}-\text{Replacement}$

​证明 我们将证明对于 ${\mathrm{\Sigma }}_N$-公式 $\phi \equiv \mathrm{\exists }y\theta (x,y)$（其中 $\theta$ 是 ${\mathrm{\Pi }}_{N-1}$-公式），集合 $\{x\in a:\phi (x)\}$ 存在。由逻辑知，$\mathrm{\forall }x\in a\mathrm{\exists }y(\mathrm{\exists }z\theta (x,z)\to \theta (x,y))$ 成立。应用 ${\mathrm{\Pi }}_N-\text{Collection}$，我们可以找到一个集合 $b$，使得 $\mathrm{\forall }x\in a\mathrm{\exists }y\in b(\phi (x)\to \theta (x,y))$。换句话说，$\{x\in a:\phi (x)\}=\{x\in a:\mathrm{\exists }y\in b\theta (x,y)\}$。

${\mathrm{\Delta }}_{N+1}-\text{Separation}$ 可以从 ${\mathrm{\Sigma }}_N-\text{Separation}$ 推得，证明方法参见文献 [3] 第 17 页定理 4.5（∆-分离公理）。

${\mathrm{\Sigma }}_{N+1}-\text{Replacement}$ 可以从 ${\mathrm{\Delta }}_{N+1}-\text{Separation}$ 推得，证明方法参见文献 [3] 第 17 页定理 4.6（Σ-替代公理）。

□

引理 2.1 的一些解释

Q: collection是 任意x∈A存在y φ(x,y)→存在B 任意x∈A 存在y∈B φ(x,y) 并不能够保证B里面没有多余的元素 所以真的能推出separation吗？collection并不能够保证没有多余的元素 只能保证想要的元素都在里面

A: 应用Πn-Collection后得到的集合b确实可能包含多余的元素（即，对于某些x ∈ a，b中可能包含y使得θ(x, y)不成立，但这些y不影响最终的集合等价性）。给定Σn公式φ(x) ≡ ∃y θ(x, y)，其中θ是Π_{n-1}公式。通过逻辑等价，有∀x ∈ a ∃y (φ(x) → θ(x, y))。应用Πn-Collection后，存在集合b，使得∀x ∈ a ∃y ∈ b (φ(x) → θ(x, y))。这导致{x ∈ a : φ(x)} = {x ∈ a : ∃y ∈ b θ(x, y)}。分析φ(x)的真假行为：如果φ(x)为真​​：则存在y使得θ(x, y)成立，因此∃y ∈ b θ(x, y)也为真（因为b包含了必要的见证y）；如果φ(x)为假​​：则对所有y，θ(x, y)都不成立，因此∃y ∈ b θ(x, y)也为假（即使b中有多余的y，但θ(x, y)对这些y都不成立）。因此，φ(x)为真当且仅当∃y ∈ b θ(x, y)为真，这意味着：$\{x\in a:\varphi (x)\}=\{x\in a:\mathrm{\exists }y\in b\theta (x,y)\}$。等价性成立，无论b中是否有多余元素。多余元素不影响集合定义，因为集合只关心是否存在y ∈ b满足θ(x, y)，而不关心b中是否有不相关的y。

Q: ∏ncoll+Δ0sep→∑nsep?所以{x∈a 存在y∈b θ(x,y)}为什么不需要∏_(n-1)-sep?

A: 在证明中，集合{x ∈ a : ∃y ∈ b θ(x, y)}的形成并不显式需要Π_{n-1}-Separation。这是因为：公式ψ(x) ≡ ∃y ∈ b θ(x, y)具有有界量词（y ∈ b），且b是集合。θ是Π_{n-1}公式，因此ψ(x)在计算复杂度上是Σ_n公式（因为∃y ∈ b将复杂度提升至Σ_n，但有界量化）。在KPω + Πn-Collection的背景下，这个集合的形成可以通过现有公理（Δ0-Separation和Πn-Collection）完成，无需更强分离。具体形成方式：由于b是集合，我们可以考虑笛卡尔积a × b（在KP中，Δ0-Separation保证a × b存在）。定义关系：$R=\{(x,y)\in a\times b:\theta (x,y)\}$。R的形成需要分离公理，但θ是Π_{n-1}公式，因此R的定义依赖于公式的复杂度。如果n = 1，θ是Δ0，则R可直接由Δ0-Separation形成。如果n > 1，则我们需要确保分离复杂度可处理。在KP中，Πn-Collection结合Δ0-Separation足以证明Σn-Separation（包括此步骤）。标准证明使用复杂度归纳：基始n=0：Σ0-Separation是Δ0-Separation，已包含在KP中；归纳步n>0：假设较低复杂度分离（如Σ_{k}-Separation for k < n）可用，则Σn-Separation可证。对于ψ(x) ≡ ∃y ∈ b θ(x, y)：它等价于{x ∈ a : ∃y (y ∈ b ∧ θ(x, y))}。由于y的量化有界于b，并且θ是Π_{n-1}，这个公式的复杂度受限于Σn。使用Δ0-Separation和集合a × b，我们可以间接定义R（必要时通过有界量词处理），然后投影得到域：$\{x\in a:\mathrm{\exists }y\in b\theta (x,y)\}=\text{dom}(R)$。在KP中，给定集合R（有序对的集合），dom(R)可以通过Δ0-Separation定义，因为量词"∃y ∈ b"有界，"θ(x, y)"的复杂度由Πn-Collection和较低分离处理。因此，在KPω + Πn-Collection中，集合{x ∈ a : ∃y ∈ b θ(x, y)}可以直接形成，无需额外Π_{n-1}-Separation。证明中的步骤是自洽的。

Q: 将y∈b变成x θ(x,y)然后将没有θ(x,y)的y变成0 然后再删掉0? 问题来了 我们无法保证没有添加新的元素的 所以如此收集也是有问题

A: 这个方法在理论上是可行的，但并不必要，原因如下：在集合论中，这种方法类似于使用替代公理（Replacement）定义一个部分函数：如果θ(x, y)成立，则映射y到x；否则映射到0。然后，移除0元素即可得到所需集合。但这需要显式的分离公理来形成中间集合（如{x : θ(x, y)}或{y : not θ(x, y)}），并可能引入复杂性。更重要的是，在KPω + Πn-Collection框架下，原有的证明已经通过有界量词和等价性简化了问题，无需此额外步骤。引入0或默认值反而可能增加不必要的复杂度。

引理 2.1.a ${\mathrm{\Sigma }}_2-\text{Collection}$ 可证 ${\mathrm{\Pi }}_1-\text{Separation}$

证明 给定集合  A  和  ${\mathrm{\Pi }}_1$- 公式 $\psi (x)\equiv \mathrm{\forall }y\phi (x,y)$，其中 $\phi$ 是 ${\mathrm{\Delta }}_0$。目标是证明集合 $S=\{x\in A:\mathrm{\forall }y\phi (x,y)\}$ 存在。

$\psi (x)$ 的否定是 $\mathrm{\neg }\psi (x)\equiv \mathrm{\exists }y\mathrm{\neg }\phi (x,y)$，这是一个 ${\mathrm{\Sigma }}_1$-公式。定义 $T=\{x\in A:\mathrm{\exists }y\mathrm{\neg }\phi (x,y)\}$。这是 $S$ 的补集，因为 $S=\{x\in A:\mathrm{\forall }y\phi (x,y)\}=A\setminus \{x\in A:\mathrm{\exists }y\mathrm{\neg }\phi (x,y)\}=A\setminus T$。因此，如果 $T$ 存在，则 $S=A\setminus T$ 可以通过差集得到。令 $\theta (x,y)\equiv \mathrm{\neg }\phi (x,y)$，$\theta$ 是 ${\mathrm{\Delta }}_0$。应用 ${\mathrm{\Sigma }}_1-\text{Collection}$：考虑类，对每个 $x\in A$，如果 $\mathrm{\exists }y\theta (x,y)$，则存在这样的 $y$。${\mathrm{\Sigma }}_1\text{-Collection}$ 保证：存在集合 $C$，使得对所有 $x\in A$，如果 $\mathrm{\exists }y\theta (x,y)$，则存在 $y\in C$ 使得 $\theta (x,y)$ 成立。由 ${\mathrm{\Delta }}_0\text{-Separation}$，集合 $T$ 存在。因此差集 $S=A\setminus T=\{x\in A:x\notin T\}$，由 ${\mathrm{\Delta }}_0\text{-Separation}$，集合 $S$ 存在。

□

引理 2.1.b ${\mathrm{\Sigma }}_N\text{-Separation}$ 和 ${\mathrm{\Pi }}_N\text{-Separation}$ 等价。

证明 设 $\phi (x)$ 是 ${\mathrm{\Pi }}_N$-公式，$\mathrm{\neg }\phi (x)$ 是 ${\mathrm{\Sigma }}_N$-公式。由 ${\mathrm{\Sigma }}_N-\text{Separation}$，集合 $\{x\in A:\mathrm{\neg }\phi (x)\}$ 存在。则 $\{x\in A:\phi (x)\}=A\setminus \{x\in A:\mathrm{\neg }\phi (x)\}$，由 ${\mathrm{\Delta }}_0\text{-Separation}$，差集存在。类似，设 $\psi (x)$ 是 ${\mathrm{\Sigma }}_N$-公式，则 $\mathrm{\neg }\psi (x)$ 是 ${\mathrm{\Pi }}_N$。由 ${\mathrm{\Pi }}_N\text{-Separation}$，$\{x\in A:\mathrm{\neg }\psi (x)\}$ 存在，则 $\{x\in A:\psi (x)\}=A\setminus \{x\in A:\mathrm{\neg }\psi (x)\}$，由 ${\mathrm{\Delta }}_0\text{-Separation}$ 得到。因此，${\mathrm{\Sigma }}_N\text{-Separation}$ 和 ${\mathrm{\Pi }}_N\text{-Separation}$ 在 ${\mathrm{\Delta }}_0\text{-Separation}$ 的系统中等价。

□

引理 2.2 - 2.3

引理 2.2 对于每个 ${\mathrm{\Sigma }}_{N+1}^1$-公式 $F(n,a,Y)$，存在集合论语言中的一个 ${\mathrm{\Sigma }}_N$-公式 $A_{\mathrm{\Sigma }}(n,a,Y)$，使得对于定义的 $F_{\mathrm{\Sigma }}(n,a,Y):\iff \mathrm{\exists }d[Ad(d)\wedge Y\in d\wedge A_{\mathrm{\Sigma }}^d(n,a,Y)]$，下列等价关系在系统 $\mathrm{K}\mathrm{P}{\mathrm{l}}^{\mathrm{r}}$ 中可证：

$\mathrm{K}\mathrm{P}{\mathrm{l}}^{\mathrm{r}}⊢n,a\in \omega \wedge Y\subset \omega \to \{F^{set}(n,a,Y)\leftrightarrow F_{\mathrm{\Sigma }}(n,a,Y)\}$

引理 2.3 对于二阶算术语言中的每个句子 $A$，有：

${\mathrm{\Sigma }}_{N+2}^1\text{-DC}+\text{BI}⊢A\Rightarrow \text{KP}\omega +{\mathrm{\Pi }}_N\text{-Collection}+(V=L)⊢A^{set}$

证明 根据量词定理（定理 2.2），对于一个 ${\mathrm{\Pi }}_{N+1}^1$-公式 $F(n,X,Y)$（其中 $n\in \omega ,X\subset \omega$），其集合论翻译 $F^{set}(n,X,Y)$ 等价于一个 ${\mathrm{\Pi }}_N$-公式 $\phi (n,X,Y)$。现在只需证明如下结论：对于一个 ${\mathrm{\Pi }}_N$-公式 $\phi (n,X,Y)$，如果假设 $\mathrm{\forall }n\in \omega \mathrm{\forall }X\subset \omega \mathrm{\exists }Y\subset \omega \phi (n,X,Y)$ 成立且给定 $X_0\subset \omega$，那么存在一个函数 $f$ 满足 $\text{dom}(f)=\omega$ 且 $\mathrm{\forall }n\in \omega [f(0)=X_0\wedge \varphi (n,f(n),f(n+1))]$。

在 (V = L) 的可构造宇宙公理下，我们通过归纳法证明：对于任意的 $k\in \omega$，存在唯一的子集序列 $(Y_n{)}_{n<k}\subset \omega$ 使得 $\mathrm{\forall }n<k[\varphi (n,Y_n,Y_{n+1})\wedge \mathrm{\forall }Z{<}_L{Y}_{n+1}\mathrm{\neg }\varphi (n,Y_n,Z)]$ 成立。然后，利用 ${\mathrm{\Sigma }}_{N+1}-\text{Replacement}$，我们可以选取一个函数 $g$ 满足 $\text{dom}(g)=\omega$ 且 $\text{rng}(g)\subset {}^{<\omega }P(\omega )$，使得对于任意 $k\in \omega$，$g(k)$ 是那个唯一的序列 $(Y_n{)}_{n<k}\in {}^{k}P(\omega )$，并满足 $Y_0=X_0$。最后，定义函数 $f(n)=(g(n+1))(n)$ 即为所求的函数。

□

引入 $S_{{\mathbb{𝕀}}_N}$

(待补充)