Circle函数：修订间差异

2025年8月20日 (三) 16:11的最新版本

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₁ 是 v₂ 的后代时，圆 C₁ 才会包含在圆 C₂ 中。

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

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

最大的 n，使得存在一个森林 F，其中 n 个顶点标记为 1 到 n，满足以下条件：F_i 是 F 的子林，由标记为 i 到 2i 的顶点组成（如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先）。那么对于任何 $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)$ 是否有限”不可能在 PA 中证明。

参考资料

↑ Friedman, H. M. (2000). Enormous integers in real life. (EB/OL). https://bpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf

[1] Friedman, H. M. (2000). Enormous integers in real life. (EB/OL). https://bpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf

[1]

@@ 第1行： / 第1行： @@
-'''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>
+'''Circle 函数'''是 Harvey Friedman 提出的一个快速增长的函数。<ref>Friedman, H. M. (2000). Enormous integers in real life. (EB/OL). https://bpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf</ref>
-== 定义 ==
+=== 定义 ===
-由平面上n个不相交的圆（可能外离或内含）组成的一个有限序列<math>\{C_1,C_2,\cdots,C_n\}</math>，记为 '''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>。
-给定一个正整数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-好''' 的。
+给定一个正整数 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序列'''：
+我们定义如下的 '''Circle 序列'''：
-<math>\mathrm{Circle}(k)</math> 定义为所有不是 k-好 的n圆组中n的最大值。
+<math>\mathrm{Circle}(k)</math> 定义为所有不是 k-好的 n 圆组中 n 的最大值。
-=== 解释 ===
+==== 解释 ====
-对于平面上任何圆的集合 <math>S</math>，我们可以自然地将 <math>S</math> 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。
+对于平面上任何圆的集合 S，我们可以自然地将 S 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。
-如果顶点 <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>中。
+如果顶点 v 对应于圆 C，则 v  的子圆将对应于 C 中包含的 S 中的圆，中间没有中间圆。当且仅当对应的顶点 v<sub>1</sub> 是 v<sub>2</sub> 的后代时，圆 C<sub>1</sub> 才会包含在圆 C<sub>2</sub> 中。
-对于任何一对圆的集合<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>。
+对于任何一对圆的集合 S<sub>1</sub> 和 S<sub>2</sub> 使用相应的森林 F<sub>1</sub> 和 F<sub>2</sub>，当且仅当存在 F<sub>1</sub> 的嵌入时，S<sub>1</sub> 才会同胚到 S<sub>2</sub> 到 F<sub>2</sub>。
-因此，我们可以将<math>\mathrm{Circle}(k)</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>的嵌入。
+最大的 n，使得存在一个森林 F，其中 n 个顶点标记为 1 到 n，满足以下条件：F<sub>i</sub> 是 F 的子林，由标记为 i  到 2i 的顶点组成（如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先）。那么对于任何 <math>k\leq i<j\leq \frac{n}{2}</math>，不存在 F<sub>i</sub> 到 F<sub>j</sub> 的嵌入。
-== 取值 ==
+=== 取值 ===
-Friedman指出，<math>\mathrm{Circle}(k)</math> 一定是有限的，但我们对其具体取值仍了解不多。我们有<math>\mathrm{Circle}(1)=1</math>以及<math>\mathrm{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>，这意味着命题“<math>\mathrm{Circle}(k)</math> 是否有限”不可能在 [[皮亚诺公理体系|PA]] 中证明。
 == 参考资料 ==
+{{默认排序:相关问题}}
 [[分类:记号]]