关于Erds-Moser定理的研究(英文)  

Some Results on Erds-Moser Theorem

作　　者：康孝军[1,2] 

机构地区：[1]中山大学逻辑与认知研究所 [2]中山大学哲学系

出　　处：《逻辑学研究》2013年第1期39-48,共10页Studies in Logic

摘　　要：本文主要研究Erds-Moser定理。在简单介绍了反推数学的一些基础知识后,首先研究了Erds-Moser定理的证明论强度:存在一个可计算的二元二染色函数使得任何无穷Σ02集合都不是该函数的传递集,同时存在一个可计算的二元二染色函数使得每一个该函数的无穷传递集都是超免疫的。其次,我们进一步考虑了稳定性Erds-Moser定理,证明了在二阶算术子系统RCA0下稳定性Erds-Moser定理是不可证的并且对每一个可计算的稳定性二色二阶函数,我们构造了一个φ'可计算的无穷传递集。In this paper, we get some results on Erd6s-Moser theorem. After briefly intro- ducing some basic knowledge about reverse mathematics, we first investigate the strength of ErdOs-Moser theorem. There is a computable function f ： [ω] 2 → 2 such that no infinite Eo set is transitive for f. There is a computable function f ： [ω]2→ 2 such that every infinite transitive set for f is hyperimmune. Then we study the strength of stable Erdos-Moser theo- rem. We show that RCAo does not imply stable Erdos-Moser theorem and we also prove that t there exists a Ф -computable mflnite transitive set S for each given stable computable function f ： [ω] 2→ 2 by direct construction.

关 键 词：定理 稳定性 基础知识 函数 子系统 染色 二元 证明 

分 类 号：B81[哲学宗教—逻辑学]