Circle函数：修订间差异

2025年7月17日 (四) 13:57的版本

Circle函数，是Harvey Friedman提出的一个快速增长的函数。^[1]

定义

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

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

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

我们定义如下的Circle序列：

$C i r c l 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}$ 。

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

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

取值

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

Circle函数的FGH 增长率是 $ε_{0}$ ，这意味着命题“ $C i r c l e (k)$ 是否有限”不可能在皮亚诺公理体系中证明。

参考资料

↑ FRIEDMAN H M. Enormous integers in real life〔J〕. Manuscript, dated June 1, 2000: 10-11.

[1] FRIEDMAN H M. Enormous integers in real life〔J〕. Manuscript, dated June 1, 2000: 10-11.

[1]

@@ 第1行： / 第1行： @@
-Circle函数是Harvey Friedman提出的一个快速增长的函数
+'''Circle函数'''，是Harvey Friedman提出的一个快速增长的函数。<ref>[https://bpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf FRIEDMAN H M. Enormous integers in real life〔J〕. Manuscript, dated June 1, 2000: 10-11.]</ref>
 == 定义 ==
-由平面上n个不相交的圆(可能外离或内含)组成了一个序列<math>\{C_1,C_2,\cdots,C_n\}</math>.把并集<math>C_a\cup C_{a+1}\cup\cdots C_{b-1}\cup C_b</math>记作<math>C_{[a,b]}</math>.给定一个正整数k，如果存在满足“<math>k\leq i<j\leq n/2</math>,且存在把<math>C_{[i,2i]}</math>变成<math>C_{[j,2j]}</math>的子集的同胚拓扑变换”的<math>(i,j)</math>对，那么称这样的n圆组为“k-好”的。我们定义如下的Circle序列：Circle(k)定义为所有不是“k-好”的n圆组中n的最大值。
+由平面上n个不相交的圆（可能外离或内含）组成的一个有限序列<math>\{C_1,C_2,\cdots,C_n\}</math>，记为 '''n 圆组'''。
-=== 森林解释 ===
+将并集 <math>C_a\cup C_{a+1}\cup\cdots \cup C_{b-1}\cup C_b</math> 记作 <math>C_{[a,b]}</math>。
-对于平面上任何圆的集合 ''S''，我们自然可以将其 ''S'' 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。如果顶点 ''v'' 对应于圆 ''C''，则 ''v'' 的子圆将对应于 ''C'' 中包含的 ''S'' 中的圆，中间没有中间圆。当且仅当对应的顶点<math>v_1</math>是<math>v_2</math>的后代时，圆<math>C_1</math>才会包含在圆<math>C_2</math>中。
-对于任何一对圆的集合<math>S_1</math>和<math>S_2</math>使用相应的森林<math>F_1</math>和<math>F_2</math>，当且仅当存在<math>F_1</math>的嵌入时，<math>S_1</math>才会同胚到<math>S_2</math>到<math>F_2</math>.
+给定一个正整数k，如果存在满足 “<math>k\leq i<j\leq \frac{n}{2}</math>，且存在把<math>C_{[i,2i]}</math>变成<math>C_{[j,2j]}</math>的子集的同胚拓扑变换” 的<math>(i,j)</math>对，那么称这样的n圆组为 '''k-好''' 的。
-因此，我们可以将 Circle（''k''） 的定义改写为最大的 ''n''，使得存在一个森林 ''F''，其中 ''n'' 个顶点标记为 1 到 ''n''，满足以下条件：<math>F_i</math>是F的子林，由标记为i到2i的顶点组成(如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先)。那么对于任何<math>k\leq i<j\leq n/2</math>，不存在<math>F_i</math>到<math>F_j</math>的嵌入。
+我们定义如下的'''Circle序列'''：
+<math>\mathrm{Circle}(k)</math> 定义为所有不是 k-好 的n圆组中n的最大值。
+=== 解释 ===
+对于平面上任何圆的集合 <math>S</math>，我们可以自然地将 <math>S</math> 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。
+如果顶点 <math>v</math> 对应于圆 <math>C</math>，则 <math>v</math> 的子圆将对应于 <math>C</math> 中包含的 <math>S</math> 中的圆，中间没有中间圆。当且仅当对应的顶点<math>v_1</math>是<math>v_2</math>的后代时，圆<math>C_1</math>才会包含在圆<math>C_2</math>中。
+对于任何一对圆的集合<math>S_1</math>和<math>S_2</math>使用相应的森林<math>F_1</math>和<math>F_2</math>，当且仅当存在<math>F_1</math>的嵌入时，<math>S_1</math>才会同胚到<math>S_2</math>到<math>F_2</math>。
+因此，我们可以将<math>\mathrm{Circle}(k)</math>的定义重新表述为：
+最大的<math>n</math>，使得存在一个森林 <math>F</math>，其中 <math>n</math> 个顶点标记为 1 到 <math>n</math>，满足以下条件：\(F_{i}\) 是 <math>F</math> 的子林，由标记为 <math>i</math> 到 <math>2i</math> 的顶点组成（如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先）。那么对于任何<math>k\leq i<j\leq \frac{n}{2}</math>，不存在\(F_{i}\)到<math>F_j</math>的嵌入。
 == 取值 ==
-Friedman指出，Circle(k)一定是有限的，但我们对其具体取值仍了解不多。我们有<math>Circle(1)=1</math>以及<math>Circle(2)\geq 13</math>.
+Friedman指出，<math>\mathrm{Circle}(k)</math> 一定是有限的，但我们对其具体取值仍了解不多。我们有<math>\mathrm{Circle}(1)=1</math>以及<math>\mathrm{Circle}(2)\geq 13</math>。
+Circle函数的[[FGH]][[增长率]]是<math>\varepsilon_0</math>，这意味着命题“<math>\mathrm{Circle}(k)</math>是否有限”不可能在[[皮亚诺公理体系]]中证明。
-Circle函数的[[FGH]][[增长率]]是<math>\varepsilon_0</math>.
+== 参考资料 ==
 [[分类:记号]]