On the Ramseyan Factorization Theorem

摘要

We study, in the context of reverse mathematics, the strength of Ramseyan factorization theorem (RF_k~s), a Ramsey-type theorem used in automata theory. We prove that RF_k~s is equivalent to RT_2~2 for all s, k ≥ 2, k ∈ ω over RCA_0. We also consider a weak version of Ramseyan factorization theorem and prove that it is in between ADS and CAC.