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_1$是$v_2$的后代时，圆$C_1$才会包含在圆$C_2$中。

对于任何一对圆的集合$S_1$和$S_2$使用相应的森林$F_1$和$F_2$，当且仅当存在$F_1$的嵌入时，$S_1$才会同胚到$S_2$到$F_2$。

因此，我们可以将$\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)$是否有限”不可能在皮亚诺公理体系中证明。