基于翻转性质的大数函数Flip(n,a)

Kirby 描述了一个独立于 PA 的命题“翻转性质”。本条目介绍基于翻转性质的函数$\mathrm{F}\mathrm{l}\mathrm{i}\mathrm{p}(n,a)$ .

翻转性质

定义 1. 设 X 为自然数的有限集，$⟨A_n⟩$为 X 的子集构成的一个有限序列。若将$⟨A_n⟩$中的某些元素替换成其在 X 上的补集（也可以不替换任何元素），则得到的新序列称为$⟨A_n⟩$的翻转。

定义 2. 对$⟨A_n⟩$尽可能长地递归定义序列$\{{\alpha }_i\}$如下：

1. ${\alpha }_0$为$A_0$的最小值；
2. ${\alpha }_{n+1}$为大于${\alpha }_n$，且是所有$A_j$的共同元素中的最小数($j<{\alpha }_n$)。

序列$\{{\alpha }_i\}$称为$⟨A_n⟩$ 的梯子。

定义 3. 定义集合 X 的可翻转性如下：

1. 称 X 是 0-可翻转的，如果 X 中的元素个数大于 1。
2. 称 X 是 (n+1)-可翻转的，如果 X 的任何子集序列都有一个翻转，其梯子为 n-可翻转的。

Kirby 给出了如下定理：

1. 命题“对于任意的 z 和任意的 a ，存在 b 使得 [a,b] 为z-可翻转的”独立于 PA。
2. 对于任意给定的 n ，命题“对于任意的 a ，存在 b 使得 [a,b] 为n-可翻转的”在 PA 中可证。

上述两个定理中的 [a,b] 为从 a 到 b 的闭区间。

大数函数

根据上述定理，定义如下的函数：

$\mathrm{F}\mathrm{l}\mathrm{i}\mathrm{p}(n,a)$定义为满足命题“ [a,b] 为 n-可翻转的”最小 b 。

根据 Kirby 的工作，可以得到如下的独立性结果：$\mathrm{F}\mathrm{l}\mathrm{i}\mathrm{p}(n,a)$的完全性等价于 PA 的一致性。

我们猜想$\mathrm{F}\mathrm{l}\mathrm{i}\mathrm{p}(n,n)$是一个增长率为${\epsilon }_0$的函数。