Philosophy 版

发信人: robertfool (海螺), 信区: Philosophy
标  题: 什么是Reverse Math？
发信站: 逸仙时空 Yat-Sen Channel (Sat Dec  8 21:34:15 2012), 站内信件


（zz 说明: 原贴以回复形式首发于smth-BBS数学版，以为有些益处，
现单独做一帖，重发于SYSU-BBS数学版哲学版，及Lilac-BBS哲学版。Enjoy~~）

********

发信人: robertfool (海螺), 信区: Mathematics
标  题: Re: Reverse Mathematics是研究神马的？
发信站: 水木社区 (Wed Nov  7 11:53:46 2012), 站内

Reverse Math , 通常译作“反推数学”。

//

由Friedman，Simpson等人开创，与通常的由上至下的“证明未知定理”的想法不同

，
他们希望构建一些公理框架，对“已知的数学定理”进行“强弱”分类！

（他们的公理框架是“二阶算术的子系统--Subsystem of Z_2，
例如，RCA_0，WKL_0，ACA_0，ATR。。。）

//

事情的缘起和Idea:
我们知道，二阶算术系统Z_2可以表达绝大部分数学，但，他们提出疑问，
对于去证明某个具体的数学定理（如Ramsey定理，闭区间套定理，etc.）
有必要用到这么大的系统么？小一点的系统可以么？

（这里的“系统大小”，指的是里面含有的“论述集合存在的那些二阶公式”的多

少。）

于是，他们结合递归论(computability)的经验，
利用了公式的算术分层（Arithmetic Hierarchy)
构造了以上一些子系统，并严格证明了系统之间的大小关系。

如，RCA_0 << ACA_0 ，
即是说，至少有一条定理A，在ACA_0可以被证明，但在RCA_0中不能被证明。

//
进一步，他们希望能实现大抱负——分类所有的已知数学定理

（他们的注意力，主要在可数无穷的这类数学）

虽然不同门类有不同的数学定理，如泛函分析的，和组合数学的，看似八竿子打不

着，
但希望能把所有的数学定理在上述的框架中“论强弱排辈，各就其位；井然有序”

。

//
定理间的强弱可以从两个角度说，

一是定理所在的框架；（例如，两条定理，定理A，定理B）
如果定理A能在RCA_0中证出，同时，
定理B不能在RCA_0中证出，只能在更大的系统ACA_0中证出。
那么我们可以说“定理B比定理A，强！”

另一角度，是定理间的直接蕴涵关系。
先假定一个证明框架（通常制定最小的框架RCA_0）
over RCA_0，（即，在RCA_0框架内）
如果定理B 能证明出 定理A，同时，
定理A 不能证明出 定理B，
那么我们也可以说“定理B比定理A，强”

//
补充，和，或许大家想知道的
Ramsey's theorem在反推数学中的一点历史

Ramsey's theorem（RT)，特别是RT^2_2，在反推数学中有特殊地位，
自1970s'以来受广泛关注：

1970s'  Jockusch, 经典论文<Ramsey's theorem and recursion theory>掀开了研

究序幕
（当然细抠起来，前面还有一位Spencer(??))

论文最后，Jockusch留下问题，over RCA_0，
RT^2_2 是否能证出 ACA_0  ?

*

1994左右，Seetapun，牛津博士生(??)，发明一套新方案，否定的解决Jockusch上

述问题。

当时已经知道三个系统是严格相互包含的，即，
RCA_0   <<   WKL_0   <<   ACA_0

Seetapun的论文说，(RCA_0 + RT^2_2) 不足以证出ACA_0 系统，
很自然地，留下问题，它们足够证明WKL_0么？即
over RCA_0，
RT^2_2 是否能证出 WKL_0 ?

*

2010年，Liu Jiayi(刘嘉忆），中南大学本科生，他的论文否定的解决Seetapun的

问题。

//
再补充，
reverse math与computability（递归论，可计算理论）有种天然的联系。

（
如RCA_0系统，从递归论的角度看，
该系统证出的“东西”都是recursive（递归的，可计算的）。

更细致的描述，是，RCA_0系统的 \omega-model < M, S，+, *, 0,《 > 6项中的
第二项S，集合的域，
是“关于 join运算 封闭”和
“关于 图灵规约(Turing reducibility) 向前封闭”。
）

对反推数学的研究，目前基本是借助了递归论的工具。

//

因为反推数学的庞大想法，此领域有许多（甚至无尽?）的OpenQuestion。
但为研究人员感兴趣的，更多的是传统的组合算子（如RT，RRT，COH，WKL，等等）
与算术定理(Induction thoerem，Least number theorem，Bounded theorem等）；
部分研究人员也喜爱，从不同数学分支，或捕获或设计出新的组合算子，加以研究

。

//

提一句，个人看来，反推数学发展至今，与初创者想法已有不少相悖之处：
源于人们发现了愈来愈多的“强弱不能比较”“无法定位”的定理。
但，
这似乎更激发起研究者的探奇的热情(??) :-)

//
以上，是小生的一点粗陋理解，希望读后不至于更迷糊，希望能抛砖引玉；
也希望该领域愈发兴旺，促进与数学各分支的融合。

附，

标准参考书，Simpson, Subsystems of second order arithmetic
（Mileti似乎在准备一本新书）

活跃人员，Denis R. Hirschfeldt,
Theodore A. Slaman,
Richard Shore
C.T.Chong,
Yang Yue
Damir D.Dzhafarov，......
很多，挂一漏万。感兴趣的朋友顺藤摸瓜吧。

(最后的最后，从"零"开始的学习路径可能是：
数理逻辑 --> Computability (Soare 或 Cooper) --> Simpson
同时，找准问题，围绕其阅读最新的研究论文。)

(愿共勉，同进步。hoho~~）

(End)

--
※ 修改:·robertfool 于 Nov  7 14:30:32 2012
※ 来源:·水木社区 newsmth.net·[FROM: 113.111.199.*]

--

※ 来源:．逸仙时空 Yat-Sen Channel argo.sysu.edu.cn．[FROM: 113.111.212.126]
本文全文链接:
http://argo.sysu.edu.cn/bbscon?board=Philosophy&file=M.1354973655.A
※ 修改:·robertfool 于 Jan 22 19:46:03 修改本文·[FROM: 113.111.153.15]