Circle函数

Circle 函数是 Harvey Friedman 提出的一个快速增长的函数。

定义

由平面上 n 个不相交的圆（可能外离或内含）组成的一个有限序列 $\{C_1,C_2,\cdots ,C_n\}$，记为 n 圆组。

将并集 $C_a\cup C_{a+1}\cup \cdots \cup C_{b-1}\cup C_b$ 记作 $C_{[a,b]}$。

给定一个正整数 k，如果存在满足 “$k\le i<j\le \frac{n}{2}$，且存在把 $C_{[i,2i]}$ 变成 $C_{[j,2j]}$ 的子集的同胚拓扑变换” 的 $(i,j)$ 对，那么称这样的 n 圆组为 k-好的。

我们定义如下的 Circle 序列：

$\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(k)$ 定义为所有不是 k-好的 n 圆组中 n 的最大值。

解释

对于平面上任何圆的集合 S，我们可以自然地将 S 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。

如果顶点 v 对应于圆 C，则 v 的子圆将对应于 C 中包含的 S 中的圆，中间没有中间圆。当且仅当对应的顶点 v₁ 是 v₂ 的后代时，圆 C₁ 才会包含在圆 C₂ 中。

对于任何一对圆的集合 S₁ 和 S₂ 使用相应的森林 F₁ 和 F₂，当且仅当存在 F₁ 的嵌入时，S₁ 才会同胚到 S₂ 到 F₂。

因此，我们可以将 $\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(k)$ 的定义重新表述为：

最大的 n，使得存在一个森林 F，其中 n 个顶点标记为 1 到 n，满足以下条件：F_i 是 F 的子林，由标记为 i 到 2i 的顶点组成（如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先）。那么对于任何 $k\le i<j\le \frac{n}{2}$，不存在 F_i 到 F_j 的嵌入。

取值

Friedman 指出，$\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(k)$ 一定是有限的，但我们对其具体取值仍了解不多。我们有 $\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(1)=1$ 以及$\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(2)\ge 13$。

Circle 函数的 FGH 增长率是 ${\epsilon }_0$，这意味着命题“$\mathrm{C}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{l}\mathrm{e}(k)$ 是否有限”不可能在 PA 中证明。