燃烧数阅读报告

· · 个人记录 

1 Introduction

一个众所周知的数学谜题，我们有两条不均匀绳子，每条能烧一个小时，我们要怎么烧45min?正确答案是烧一号绳子的两端和二号绳子的一端。在一号绳子烧完时点二号绳子的另一端。

基于这个谜题，我们定义了 $F \subset Q$ 为所有像这样能被表示出来的数的集合。正式地，我们{定义} $x~y=(x+y+1)/2$ for $x,y \in R$，递归地，我们{定义} $0 \in F$，以及 $x~y \in F$，当 $|y-x|<1$。组合意义为，x为点绳子左侧的时间，而y为点该绳右侧的时间。注意到这样只允许两端烧并不会失去一般性，因为我们可以先让其两端同时开烧，再在烧完时拿另一个绳子两端同时开始烧，因此我们有 x+1=(x~x)~(x~x)。每个 $z \in F$ 都是一个非负dradic(二元)有理数，这意味着其分母为2的幂。
我们可能有多种方案得到同一个数，例如 3/4~3/4 = 1/2~1 = 5/4。注意区分表示(representation)和数本身。表示为一个用0和~连接的代数式，这并不都是合法的，因为可能不满足 $|y-x|<1$ 的条件。
5/4有两种不同表示法，
T1="(0~(0~0))~(0~(0~0))"
T2="(0~0)~((0~0)~(0~0))"
他们对应的树表示[注:注意到~是二元运算符，故可以以叶子(自动)为0的二叉树来表示]在图形1中给出(必要时，我们以引号区分数和表示)。一般而言，我们以大写字母指代一种表示，而以小写字母指代数。{定义}v(T)为表示T对应的数，并{定义} h(T)为T树表示的树高，例如h("0")=0,而h("0~0")=1，5/4的两种表示的高都为3，而11/8则有高为3和4的表示。
我们有 $v(T) = \sum_{x}{2^{-depth(x)-1}}$，求和指标遍历了每个 T的树表示 中的内部(非0/非叶子)点。
存在无限多的燃烧数小于1。事实上，小于1的燃烧数恰为 {1-2^{-n}|n\in N}，以 0 \in F,1-2^{-(n+1)}=0~(1-2^{-n}) 给出，这个序列converge(收敛?)到1，而1本身也是燃烧数，因为 1=1/2~1/2.

1.1 Our results. 依我们所言，燃烧数集合 $F$ 和序数、证明理论、计算理论和快速增长函数(事实上，是比阿克曼(Ackermann)函数增长得快多了的函数)相关，在这篇论文中我们将证明：

Theorem 1.1. 燃烧数集合F以R上定义的"<"作为序时，是良序的(well-ordered)，且有order type(序数的阶?)为ε0

Theorem 1.2. 燃烧数的密度增长得相当快，使g(n)为[n,+inf)内连续燃烧数间的最大间隙，那么有 g(n)^{-1} >= F_{ε0}(n-7) forall n>=8，其中 F_{x} 表示快速增长层级(fast-growing hierarchy)[是一类基数下标的函数]。

Peano Arithmetic. 一些关于皮亚诺算数公理结构的叙述...

Theorem 1.3.
(1)PA 不能证明真论断 "对于每个n\in N都存在一个最小燃烧数大于n"
(2)PA 不能证明真论断 "对于每个燃烧数 x \in F 都有一个最大高度的表示 h_{max}(x)"
(3)考虑一个算法 "M(x):return x<0?(-x):(M(x-M(x-1))/2)"，M在所有实数停机[终止]。但PA并不能证明"M在所有自然数停机"。

论文结构.一些结构简述...

2 Basic Results

观察2.1. 设x<=y且y-x<1，使z=x~y，那么x+1/2<=z<x+1，且有y<z.

[证明.x+1/2=(x+x+1)/2<=(x+y+1)/2<(x+x+1+1)/2=x+1，且有(x+y+1)/2>(y+y)/2=y]

Lemma 2.2. 设z \in F 且有 m \in (0,1].存在至少一个燃烧数属于 (z+1-2m,z+1-m]。

证明.取z_n=z+1-2^{-n} for n\in N,故有z_0=z,z_{n+1}=z~z_n \in F，而 z_n 中恰好一个在该区间内。[只需证明 2^{-n} 中至少一个在 [m,2m)中，构造性的取 n=ceil(log2(m)),那么由于log2(m)<=ceil(log2(m))<log2(m)+1,就有m<=2^n<2m]

[
无穷Ramsey定理知识补充

{定义}集合S在I内的分割是一个集合P={X_i|i\in I}，满足∪_{i\in I}X_i=S，且\any i\neq j,i,j\in I,有X_i∩X_j=∅
对集合A和自然数n，{定义}[A]^n={X\subseteqA | |X|=n}为A的n元子集族。
若{X_i}是[A]^n的一个分割，若有某个i满足[H]^n\subseteq X_i，{则称}H\subseteq A为此分割的齐性集。

例如：若分割为{{{x,y}|xy为偶数},{{x,y}|xy为奇数}}，则所有偶自然数集合是此分割的齐性集，所有奇自然数集合也如此。

无穷Ramsey定理.设 $n,k$ 为自然数，A为可以从子集中选择元素的无限集，则[A]^n的每个分割X_i(I取[1,k]∩N)都有一个无穷齐性集。
另一种表述形式.设 $n,k$ 为自然数，A为可以从子集中选择元素的无限集，对每个[A]^n->I的映射F，都存在一个无限集合H使得F([H]^n)全都相等。

证明.对n进行归纳，考虑n=1时，必有分割中一个集合为无穷集，取齐性集为该集合即可。下面假设定理对1和n成立，只需证明定理对n+1也成立。
对每个a\in A,定义F_a(S) (|S|=n)为F(S∪{a}),记H_a^{A'}为对集合A'应用在n上的归纳假设得到的无穷齐性集。考虑定义无穷序列{a},
a_1=choose(A),a_2=choose(H_a1^A),a_3=choose(H_a2^{H_a1^A})...，故我们构造了一个可数无穷集，使得每个数和其后任何n个元素组成的集合映射的值都相等，设其为G(i)
对G(i)应用n=1的归纳假设，即可得出有无穷集使得G(i)也全相同。
]

Lemma 2.3. 集合F是关于实数上的"<"关系是良序的，也就是说F的每个非空子集都有最小元素。

证明.使用反证法，考虑一个子集 G \subseteq F 使其没有最小元素.[由于任两个实数都能进行比较，这样就说明对每个元素必然有一个比其更小的元素在G中]每个这样的子集必然包含一些无穷递降链S=(z_1>z_2>z_3>...)(原文注:为了避免使用选择公理，我们可以以某种具体方法对z_i进行选择，例如选择G∩[0,z_{i-1})中分母最小的数中分子最小的)，[我们考虑F中这样的递降链，]每个这样的递降链都收敛到实数上的一个极限[有界递减数列有极限]，设L是**F中**这些极限的集合，L必有最小元，因为若L中有无穷递降链，则其极限必然也属于L[例如，我们可以按对角线法从每个取l_i的第i项z构成一个S,以使其极限属于L]，设S_0是这么一个收敛到L中最小元l_0的递降链。

注意到S_0中没有0，设z_i=x_i~y_i,其中x_i<=y_i.我们可以不失一般性地假设(使用无穷Ramsey定理,必要时取S_0的一个无穷子集)，{x_i}是单调升，单调降或者常数序列，若x_i是单调降序列，由观察2.1，x_i+1/2<=z_i，又有x_i也在F中，则l_0的最小性不成立。否则y_i必为递降序列，设y*满足x_1~(y*)=l_0，那么由于x不降，x_1~y_i \le x_i~y_i = z_i，故有lim x_1~y_i<=l_0，即lim y_i<=y*，又由于y*<l_0，故lim y_i<l_0，和l_0最小的假设矛盾。

给定一个R的良序子集G(以"<"为序)，{定义}ord(G)为G对应的ordinal(序数?)，Lemma2.3引出了确定ord(F)的问题，而我们将要在之后证明ord(F)=ε0.

给出r\in R,我们{定义}ord(r)为ord(F∩[0,r))，与之相对的，给出一个可数序数α<ord(F)，我们{定义}fus(α)为那个唯一的元素z，使得ord(z)=α。例如，ord(0)=0,ord(1/2)=1,ord(3/4)=2,ord(1)=ω,ord(9/8)=ω+1，与之相对的有fus(ω)=1，以及fus(ω+1)=9/8.

Lemma 2.4. F是封闭的，也就是说若z_1<z_2<...是F中收敛到z的序列，那么z\in F。

证明.令L是所有题设上升序列收敛到的z组成的集合，使得z\not\in F。使用反证法，假设L非空，令l=inf L[inf:下确界]，由Lemma 2.3，必有l\in L。设z_i=x_i~y_i[z_1=0时我们去掉z_1]，像上一个证明一样，我们可以不失一般性地假设{x_i}以及{y_i}都是不减的.[y_i递减或者x_i递减会依次造成类似于上个证明中讨论的两种矛盾]令x=lim x_i以及y=lim y_i，根据"~"运算的连续性，我们有l=x~y。根据观察2.1我们有l-1<=x<=l-1/2<l，因此由于l是最小的，我们有x\in F。如果x>l-1，那么y<l，于是因为l最小，y也在F中，故而l=x~y也在F中；而若x=l-1，那么l就为(x~x)~(x~x)，同样在F中，和假设矛盾。

因此，我们可以看出F中存在两种非零燃烧数：后继型(successors)和极限型(limits)，它们恰好对应小于ord(F)的后继型和极限型非零序数.
给出一个二元(dradic)分数r=p/q，其中p为奇数而q=2^n，我们{定义}e(r)=n，并称其为r的指数.

观察2.5. 令r_1=(p-1)/q，以及r_2=p/q为两个二元分数(不必最简)，其中q=2^n，那么每个二元分数r_1<r<r_2都满足e(r)>n.

观察2.6. 令x,y,z为二元分数，并满足z=x~y，假设1<=e(x)<=e(y)，那么如果e(x)<e(y)则e(z)=e(y)+1，如果e(x)=e(y)则e(z)<=e(x).

Corollary(推论) 2.7.对每个z的表示T，我们有h(T)\ge e(z)[证明.考虑每次增加一层最多只能增加r指数的1]

Lemma 2.8. 令T为z的一个树表示，使得h(T)=n，那么有z'=z+2^{-(n+1)} \in F且其有一个高为n+1的树表示.

证明.对n归纳，若n=0,则T="0"且z=0,因此z'=1/2=0~0.假设结论对n-1成立，令T="T_1~T_2"为一个高度为n的表示，那么h(T_1),h(T_2)\le n-1，且至少一次取等。不妨假设T_1取等[树的子节点可交换]，设x=v(T_1)以及y=v(T_2)，那么我们有|y-x|<1，且e(x),e(y)\le n-1，因此事实上|y-x|\le 1-2^{-(n-1)}，因此由于归纳假设，x'=x+2^{-n}有一个T'表示，使得h(T')=n，而且我们有|y-x|<1，因此"T'~T_2"是一个z'的合法表示.

Lemma 2.9. 令T为z的一个树表示，使得h(T)=n>0，那么有z'=z-2^{-(n+1)} \in F且其有一个至少高为n-1的树表示，以及一个至多高为n的树表示(可能重复).

证明.对n归纳，若n=1有T="0~0"，且z=1/2，那么z'=0.假设结论对n-1成立，令T="T_1~T_2"为一个高度为n的表示，那么h(T_1),h(T_2)\le n-1，且至少一次取等。不妨假设T_1取等，设x=v(T_1)以及y=v(T_2)，同Lemma 2.8有|y-x|\le 1-2^{-(n-1)}，由归纳假设，x'=x-2^{-(n-1)}有两个表示(可能重复)T'和T''，使得h(T')\ge n-2，以及h(T'')\le n-1，我们我们有|y-x'|<1，那么"T'~T_2"和"T''~T_2"即为所求。否则我们就有y-x'=1，因此z'=y=x'+1，故"(T'~T')~(T'~T')"和T_2即为所求，因为前一棵至少高为n，而后一棵树至多高n-1.

观察Lemma 2.8，它揭示了每个燃烧数都有一个最大高度的表示，因为否则我们就能在F中构造无穷递降序列[若不存在这样的最大高度，则存在一个无穷递增的序列h_1<h_2<...，使得每个数都能成为该数的高度，那么其对应的z'就是无穷递减序列]。给定z\in F，{定义}hmx(z)为所有满足v(T)=z的树的h(T)最大值。

Lemma 2.10. 令z\in F 是一个满足hmx(z)>e(z)的燃烧数，那么其必为极限型。

证明.假设其为一个后继型，令z'\in F为其前驱，令n=hmx(z)，由Lemma 2.9我们有z''=z-2^{-n} \in F，因此z''\le z'<z，因为e(z'')=n[n=hmx(z)>e(z),二元分数性质]，由观察2.5，我们有e(z')\ge n，又由Lemma 2.9，我们有z'''=z'+2^{-(n+1)}\in F，而且由观察2.5，我们有z'''<z，与假设矛盾.

由"~"运算的连续性，如果x,y,z\in F，并且满足z=x~y，x,y中的一个是极限型，则z也是极限型。下面证明反方向也是正确的。

Lemma 2.11. 令z>1为一个极限型燃烧数，那么z可被写成x~y，其中x,y\in F，并且x,y中至少一个是极限型。(原文注:Lemma 2.11,2.15,2.16和推论2.17在本文中的其他部分中不会被用到)

证明.令{z_i}为收敛到z的上升无限数列，令z_i=x_i~y_i，不失一般性地假设{x_i}和{y_i}都是不降序列[同Lemma 2.4中的证明]。至少一个这样的序列是上升序列，令x=lim x_i,y=lim y_i，由Lemma 2.4我们有x,y\in F，如果x,y<z我们有z=x~y。否则，假设x=z-1，而y=z，那么z=(x~x)~(x~x)，由观察2.6和Lemma 2.10，在这种情况下x~x是极限型[由推论2.7有hmx(x)>=e(x)，而hmx(x~x)=hmx(x)+1>e(x)，而由观察2.6，若e(x)>0，e(x~x)<=e(x)，即hmx(x~x)>e(x~x)，而若e(x)=0则有e(x~x)=1，但是由于z>1，于是x>0，故hmx(x)不可能为0]。

因为F是良序的，故F中每个元素都有一个后继，{记}x的后继为s(x)，此外若x\not\in F，我们定义s(x)为大于x的最小燃烧数.

Lemma 2.12. 令z\in F为一个hmx(z)=n的燃烧数，那么s(z)=z+2^{-(n+1)}，并且hmx(s(z))=n+1.

证明.我们已经知道z'=z+2^{-(n+1)}\in F，由推论2.7我们有e(z)\le n，因此e(z')=n+1.使用反证法，存在一些燃烧数z''\in(z,z')，令m为其可能树表示的最小高度，选取这些数中最小树表示为m的最小数作为z''，由推论2.7和观察2.5我们有m\ge e(z'') \ge n+2.因此，由Lemma 2.9和观察2.5，存在一个z'''\in F∩[z,z'')并有一个高为至少n+1和一个高为至多m的表示.若z'''>z则已经和m最小或者z''最小矛盾，否则z'''=z,这就和hmx(z)=n矛盾，这样我们就用反证法证明了s(z)=z'，而若hmx(z')>n+1，使用Lemma 2.9即可导出矛盾。

推论2.13. 令z\in F有hmx(z)=n，那么接下来ω个燃烧数是z+2^{-n}-2^{-(n+m)}，其中m=1,2,3,...[数列求和]

Lemma 2.14. 令z=p/q \in F是一个后继型燃烧数，且p为奇数，那么其前驱为z'=(p-1)/q.

证明.由Lemma 2.10我们有hmx(z)=e(z)=n，其中q=2^n.因此由Lemma 2.9我们可知z'\in F，令z''为z的前驱，并使用反证法假设z'<z''<z，利用观察2.5和Lemma 2.12将可以导出矛盾[由观察2.5,hmx(z'')\ge e(z'')>n，而这样hmx(z)就必须大于n+1]

Lemma 2.15. 令z\in F是一个极限型燃烧数，使m=e(z)，那么对于所有n\in N有z_n=z-2^{-(m+n)}\in F.

证明.给定n，假设z_n\not\in F，因为F是封闭的，那么必然存在最大元素z'\in F∩[0,z_n).[注意到z_n\not\in F，所以不可能有递增数列收敛到z_n]令z''=s(z')，因为z是极限型，我们定有z_n<z''<z，由对z_n和z的观察2.5，我们有e(z'')>e(z_n)，但是z''是后继型元素，因此根据对z'和z''的Lemma 2.14和观察2.5，我们有e(z_n)>e(z'')，与假设矛盾。

Lemma 2.16. 假设 z\in F是极限型燃烧数，那么hmx(z)>e(z).

证明.令n=e(z)，考虑到(in light of)推论2.7和Lemma 2.12，这已经足够我们接下来证明存在燃烧数z'\in (z,z+2^{-(n+1)}).若z=1我们有z'=9/8\in F.否则考虑Lemma 2.11，我们有z=x~y，其中y是一个极限型.定义n_1=e(x)，以及n_2=e(y).

先假设n_1\le n_2，那么n\le n_2+1.因为|y-x|<1，我们事实上有|y-x|\le 1-2^{-n_2}，由structural induction(结构归纳?)[这里的意思也许是设z为所有不满足题设的数中最小的一个，由良序性我们可以这么假设]我们可以假设存在一个燃烧数y'\in (y,y+2^{-(n_2+1)})，这样z'=x~y'就是合法的，并且它小于z+2^{-(n_2+2)}\le z+2^{-(n+1)}.

否则，我们有n_1>n_2，并且x就是一个后继型[x是极限型的情况交换x,y即可].在这种情况下我们有n=n_1+1，并且|y-x|\le 1-2^{-n_1}，由Lemma 2.10我们有hmx(x)=n_1，因此由Lemma 2.8有x+2^(n_1+1) \in F，并且由Lemma 2.15我们有y'=y-2^{-(n_1+2)} \in F，那么z'=x'~y' \in F，并且z'=z+2^{-(n_1+3)}=z+2^{-(n+2)}.

推论2.17. z\in F是极限型燃烧数，当且仅当hmx(z)>e(z).

Algorithm 1 Finds min(F∩(r,+inf))
 1 procedure Succ(r)
 2  if (r<0) return 0
 3  mn=inf,y=r
 4  repeat
 5   x=Succ(2r-y-1)
 6   y=Succ(2r-x-1)
 7   mn=min(mn,x~y)
 8   y-=1/Denominator(y)
 9  until (y\le r-1/2)
10  return mn
Algorithm 2 Decides whether r\in F
 1 procedure IsFusible(r)
 2  if (r isn't a dyadic rational) return False
 3  return r==WeakSucc(r)
Algorithm 3 Finds min(F∩[r,+inf))
 1 procedure WeakSucc(r)
 2  if (r<=0) return 0
 3  mn=inf,y=r
 4  repeat
 5   x=WeakSucc(2r-y-1)
 6   if (x==2r-y-1) return r
 7   y=WeakSucc(2r-x-1)
 8   if (y==2r-x-1) return r
 9   mn=min(mn,x~y)
10   y-=1/Denominator(y)
11  until (y<r-1/2)
12  return mn

Lemma 2.18. 算法Succ,WeakSucc和IsFusible在所有有理数输入上终止，并且得出正确结果

证明.考虑算法Succ,给出r\in Q，令z=s(r),若r<1/2正确性显然，于是我们假设r\ge1/2.我们有z=x~y，其中x,y\inF，且满足r-1<x\le y\le r，并且y>r-1/2.我们将会说明算法尝试了所有的x和y的相关候选，以x的升序和y的降序，并且这样的候选是有限的.

在循环开始前(L4,函数第四行)满足这样的不变量:变量y要么为r，要么为一个小于r的燃烧数，并且若y<r则有变量mn存储了最小的燃烧数z>r，使其可表示为z=x'~y'，其中y<y'\le r。接着，在L5将x增加到下一个可能的候选，然后L6设置y，以最小化z'=x~y，并且z'>r.

L6不会将y增大到超过y_{old}，因为我们有2r-x-1<2r-(2r-y_{old}-1)=y_{old}，因此若y_{old}<r且y_{old}是燃烧数，那么(假设L6的递归调用返回正确结果)L6设定y为s(2r-x-1)\le y_{old}，而且像我们下面证明的这样，L6的递归调用不会返回大于r的值。

另外，根据Lemma 2.14，L8将后继型[因为y是某个Succ的返回值，故其必为某个后继型]燃烧数y替换为了其前驱，因此算法不会漏过任何备选.[之前减小了y的值，考虑L6开始时的x值,必然是一个使得x~y>r的最小x值，这可能将x调得过大，因此我们需要再调用一次Succ来获取y的新值，那么这就是\le y_{L5begin}的情况下最大可能的y值，因为x已经是可能的最小值了，而后面的用Succ更新y不会导致先前x的值不能用]

我们还需要证明L5和L6的递归调用返回正确值s(2r-y-1)和s(2r-x-1)，一旦我们证明这两个返回值小于z，就可以运用序数归纳法证明了[例如，假设最小的不能被正确返回的答案，然后这样递归返回的比其小的答案都是正确的].为此，首先注意到在循环开始时我们总是有y>r-1/2，这指示2r-y-1<r-1/2，因为每个长度为1/2的全非负区间都含有一个燃烧数[注意到若x\in F,s(x)\le x+1/2]，我们有s(2r-y-1)<r，因此由序数归纳法有L5返回值正确.

接着，注意到(recall that)在循环开头我们总有y\le r.因此在L5之后我们有x>2r-y-1 \ge r-1，设m=x+1-r，那么0<m<1.由窗口引理(Lemma 2.2)存在这样一个燃烧数在(x+1-2m,x+1-m]中.但是x+1-2m=2r-x-1，并且x+1-m=r，因此由序数归纳法有L6返回值正确，因为它正确地设置了y为s(2r-x-1)，其最多为r.

最后，循环必然在有限次后终止，否则我们就有一个无限递降燃烧数序列[考虑y形成的数列].

对于其他两个算法的证明是类似的，IsFusible的L1只是为了效率方面的考虑.
[
不会证明(类似的).
]
在算法Succ中，第一个备选的x~y不总是最优的，考虑r=33/16 \in F，它的后继是r+1/4096=8449/4096=(19/16)~(3969/2048)，但是Succ第一次尝试了r+1/2048=(9/8)~(2049/1024).

运行时间.我们将会证明对r\in N，算法Succ(r)有一个关于输入规模难以置信(incredibly)地巨大的运行时间.另一方面，我们无法排除对于WeakSucc和IsFusible关于输入规模为多项式级别的可能性，这两个算法在r\in N上跑得非常快[实测WeakSucc取r=21/10不加记忆化剪枝就已经很慢了(自家电脑上20s+,剪枝后0.1s)，但是在二元分数上好像跑得很快,没有测试过非燃烧数的较大二元分数,因为这种数很难找]

3. Background on ordinals

序数ε0是ω,ω^ω,ω^ω^ω,...的极限，每个小于其的序数α都能唯一地被表示为Cantor Normal Form(CNF,康托标准形式?)，即α=ω^α_1+...+ω^α_k,对某个k\ge 0，并且满足α>α_1\ge α_2 \ge ... \ge α_k，可供替代的，α也可以唯一写成带权CNF形式，即ω^α_1*n_1+...+ω^α_k*n_k，其中α>α_1>α_2>...>α_k，且n_i为正整数.

给定一个极限型序数[不为0且不为后继序数的序数]α<ε0，其canonical sequence(规范序列?) [α]_n(下标从1开始)是一个收敛到α的序列，它这么定义：对极限型β<ω^(α+1)我们令[ω^α+β]_n=ω^α+[β]_n,[ω^(α+1)]_n=ω^α*n，以及对极限型α我们有[ω^α]_n=ω^{[α]_n}.例如我们有[ω^(ω+2)*7]_5=ω^(ω+2)*6+ω^(ω+1)*5.