[FOM] From Compactness to Completeness

Stephen G Simpson simpson at math.psu.edu
Tue Dec 28 10:29:17 EST 2010

It is provable in RCA_0 that the following are pairwise equivalent.
1. The completeness theorem for countable languages.
2. The compactness theorem for countable languages.
3. WKL_0, i.e., RCA_0 + Weak K"onig's Lemma.
However, full K"onig's Lemma is equivalent over RCA_0 to the much stronger
system ACA_0.
A reference is Section IV.3 of my book Subystems of Second Order

Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University
foundations of mathematics, recursion theory, mathematical logic

T.Forster at dpmms.cam.ac.uk writes:
 > I think if the language is countable you don'tneed KL, surely?

More information about the FOM mailing list