[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
Arithmetic.
Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University
http://www.math.psu.edu/simpson/
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