[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
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