查看“︁基于翻转性质的大数函数Flip(n,a)”︁的源代码

Kirby 描述了一个独立于 PA 的命题“翻转性质”<ref name=":0">Kirby L A S. Flipping properties in arithmetic[J]. The Journal of Symbolic Logic, 1982, 47(2): 416-422.</ref>。本条目介绍基于翻转性质的函数<math>\mathrm{Flip}(n,a)</math> .

=== 翻转性质 ===
'''定义 1'''. 设 X 为自然数的有限集，<math>\langle A_n\rangle</math>为 X 的子集构成的一个有限序列。若将<math>\langle A_n\rangle</math>中的某些元素替换成其在 X 上的补集（也可以不替换任何元素），则得到的新序列称为<math>\langle A_n\rangle</math>的翻转。

'''定义 2'''. 对<math>\langle A_n\rangle</math>尽可能长地递归定义序列<math>\{\alpha_i\}</math>如下：

# <math>\alpha_0</math>为<math>A_0</math>的最小值；
# <math>\alpha_{n+1}</math>为大于<math>\alpha_{n}</math>，且是所有<math>A_{j}</math>的共同元素中的最小数(<math>j<\alpha_n </math>)。

序列<math>\{\alpha_i\}</math>称为<math>\langle A_n\rangle</math> 的梯子。

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

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

Kirby 给出了如下定理<ref name=":0" />：

# 命题“对于任意的 z 和任意的 a ，存在 b 使得 [a,b] 为z-可翻转的”独立于 [[皮亚诺公理体系|PA]]。
# 对于任意给定的 n ，命题“对于任意的 a ，存在 b 使得 [a,b] 为n-可翻转的”在 PA 中可证。

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

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

<math>\mathrm{Flip}(n,a)</math>定义为满足命题“ [a,b] 为 n-可翻转的”最小 b 。

根据 Kirby 的工作，可以得到如下的独立性结果：<math>\mathrm{Flip}(n,a)</math>的完全性等价于 PA 的一致性。

我们猜想<math>\mathrm{Flip}(n,n)</math>是一个增长率为<math>\varepsilon_0</math>的函数。
{{默认排序:相关问题}}
[[分类:记号]]