查看“︁AOCF”︁的源代码

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

=== 系统与公理 ===
<math>\Sigma_{N+2}^1-\text{AC+BI}</math> 表示一个二阶算术系统，它由 <math>\rm \Pi_1^1-CA_0+BI</math> 加入公理 <math>\Sigma_{N+2}^1-\text{AC}</math> 得到：<math>\forall n \exists X F(n,X) \rightarrow \exists Y \forall n F(n,Y_n)</math>，其中 <math>F(n,X)</math> 是任意的 <math>\Pi_{N+2}^1</math>-公式。

<math>\Sigma_{N+2}^1-\text{DC+BI}</math> 表示一个二阶算术系统，它由 <math>\rm \Pi_1^1-CA_0+BI</math> 加入公理 <math>\Sigma_{N+2}^1-\text{DC}</math> 得到：<math>\forall n \forall X \exists Y F(n,X,Y) \rightarrow \forall X_0 \exists Y \forall n [Y_0 = X_0 \land F(n,Y_n,Y_{n+1})]</math>，其中 <math>F(n,X,Y)</math> 是任意的 <math>\Pi_{N+1}^1</math>-公式，<math>m \in Y_n \Rightarrow (n,m) \in Y</math>，且 <math>(\cdot,\cdot)</math> 是一个双射配对函数。容易看出，公理中的公式 <math>F</math> 可以是 <math>\Sigma_{N+2}^1</math>-公式。

集合论 <math>{\rm KP}\omega+\Pi_N-\text{Collection}+(V=L)</math> 的公理由 <math>{\rm KP}\omega</math>（带无穷公理的 Kripke-Platek 集合论）的公理加上以下公理组成：

* 可构成公理 <math>V=L</math>

* <math>\Pi_N-\text{Collection}</math> 公理：对于任意 <math>\Pi_N</math>-公式 <math>A(x,y)</math>，<math>\forall x \in a \exists y A(x,y) \rightarrow \exists b \forall x \in a \exists y \in b A(x,y)</math>

* <math>\Sigma_N-\text{Separation}</math> 公理：对于任意 <math>\Sigma_N</math>-公式 <math>\varphi(x)</math>，<math>\exists y \forall x (x \in y \rightarrow x \in a \land \varphi(x))</math>
* <math>\Delta_{N+1}-\text{Separation}</math> 公理：对于任意 <math>\Sigma_{N+1}</math>-公式 <math>\varphi(x)</math> 和 <math>\psi(x)</math>，<math>\forall x \in a (\varphi(x) \rightarrow \neg\psi(x)) \rightarrow \exists y \forall x (x \in y \rightarrow x \in a \land \varphi(x))</math>
* <math>\Sigma_{N+1}-\text{Replacement}</math> 公理：如果 <math>\forall x \in a \exists !y \varphi(x,y)</math>，那么存在一个函数 <math>f</math>，其定义域 <math>\mathrm{dom}(f)=a</math>，使得 <math>\forall x \in a \varphi(x,f(x))</math> 对每个 <math>\Sigma_{N+1}</math>-公式 <math>\varphi(x,y)</math> 成立。

=== <math>\Pi_N-\text{Collection}</math> 公理 ===

==== 引理 2.1 ====
'''引理 2.1''' <math>{\rm KP}\omega+\Pi_N-\text{Collection}</math> 可证以下每一条：

# <math>\Sigma_N-\text{Separation}</math>
# <math>\Delta_{N+1}-\text{Separation}</math>
# <math>\Sigma_{N+1}-\text{Replacement}</math>

'''证明''' 我们将证明对于 <math>\Sigma_N</math>-公式 <math>\varphi \equiv \exists y \theta(x,y)</math>（其中 <math>\theta</math> 是 <math>\Pi_{N-1}</math>-公式），集合 <math>\{ x \in a : \varphi(x) \}</math> 存在。由逻辑知，<math>\forall x \in a \exists y (\exists z \theta(x,z) \rightarrow \theta(x,y))</math> 成立。应用 <math>\Pi_N-\text{Collection}</math>，我们可以找到一个集合 <math>b</math>，使得 <math>\forall x \in a \exists y \in b (\varphi(x) \rightarrow \theta(x,y))</math>。换句话说，<math>\{ x \in a : \varphi(x) \} = \{ x \in a : \exists y \in b \theta(x,y) \}</math>。

<math>\Delta_{N+1}-\text{Separation}</math> 可以从 <math>\Sigma_N-\text{Separation}</math> 推得，证明方法参见文献 [3] 第 17 页定理 4.5（∆-分离公理）。

<math>\Sigma_{N+1}-\text{Replacement}</math> 可以从 <math>\Delta_{N+1}-\text{Separation}</math> 推得，证明方法参见文献 [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)为真，这意味着：<math>\{x \in a : \phi(x)\} = \{x \in a : \exists y \in b \theta(x, y)\}</math>。等价性成立，无论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存在）。定义关系：<math>R = \{ (x, y) \in a \times b : \theta(x, y) \}</math>。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（必要时通过有界量词处理），然后投影得到域：<math>\{x \in a : \exists y \in b \theta(x, y)\} = \text{dom}(R)</math>。在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''' <math>\Sigma_2-\text{Collection}</math> 可证 <math>\Pi_1-\text{Separation}</math> 

'''证明''' 给定集合  A  和  <math>\Pi_1</math>- 公式 <math>\psi(x) \equiv \forall y \varphi(x,y)</math>，其中 <math>\varphi</math> 是 <math>\Delta_0</math>。目标是证明集合 <math>S = \{x \in A : \forall y \varphi(x,y)\}</math> 存在。

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

□

'''引理 2.1.b''' <math>\Sigma_N\text{-Separation}</math> 和 <math>\Pi_N\text{-Separation}</math> 等价。

'''证明''' 设 <math>\varphi(x)</math> 是 <math>\Pi_N</math>-公式，<math>\neg \varphi(x)</math> 是 <math>\Sigma_N</math>-公式。由 <math>\Sigma_N-\text{Separation}</math>，集合 <math>\{x \in A : \neg \varphi(x)\}</math> 存在。则 <math>\{x \in A : \varphi(x)\} = A \setminus \{x \in A : \neg \varphi(x)\}</math>，由 <math>\Delta_0\text{-Separation}</math>，差集存在。类似，设 <math>\psi(x)</math> 是 <math>\Sigma_N</math>-公式，则 <math>\neg \psi(x)</math> 是 <math>\Pi_N</math>。由 <math>\Pi_N\text{-Separation}</math>，<math>\{x \in A : \neg \psi(x)\}</math> 存在，则 <math>\{x \in A : \psi(x)\} = A \setminus \{x \in A : \neg \psi(x)\}</math>，由 <math>\Delta_0\text{-Separation}</math> 得到。因此，<math>\Sigma_N\text{-Separation}</math> 和 <math>\Pi_N\text{-Separation}</math> 在 <math>\Delta_0\text{-Separation}</math> 的系统中等价。

□

==== 引理 2.2 - 2.3 ====
'''引理 2.2''' 对于每个 <math>\Sigma^1_{N+1}</math>-公式 <math>F(n, a, Y)</math>，存在集合论语言中的一个 <math>\Sigma_N</math>-公式 <math>A_\Sigma(n, a, Y)</math>，使得对于定义的 <math>F_\Sigma(n, a, Y) :\Leftrightarrow \exists d[Ad(d) \land Y \in d \land A_\Sigma^d(n, a, Y)]</math>，下列等价关系在系统 <math>\rm KPl^r</math> 中可证：

<math>{\rm KPl^r} \vdash n, a \in \omega \land Y \subset \omega \to \{F^{set}(n, a, Y) \leftrightarrow F_\Sigma(n, a, Y)\}</math>

'''引理 2.3''' 对于二阶算术语言中的每个句子 <math>A</math>，有：

<math>\Sigma^1_{N+2}\text{-DC} + \text{BI} \vdash A \Rightarrow \text{KP}\omega + \Pi_N\text{-Collection} + (V = L) \vdash A^{set}</math>

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

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

□

==== 引入 <math>S_{\mathbb{I}_N}</math> ====
''(待补充)''