# Is the compactness theorem (from mathematical logic) equivalent to the Axiom of Choice?

Or more importantly, is it independent of the axiom of choice. The compactness theorem states the given a set of sentences $T$ in a first order Language $L, T$ has a model iff every finite subset of $T$ has a model. So for any natural number $n, T(n)$ is a finite subset of $n$ sentences. Now if every finite subset has a model than adding a sentence $r$ to $T(n)$ gives us $T(n+1)$ which also has a model so there is some transfinite induction going on here when $T$ is countable. This seems to cry out for the application of Zorn's Lemma which is equivalent to the axiom of choice. So to summarize, is the compactness theorem consistent with ~AC (the negation of the axiom of choice which is independent of ZF set theory)?

-

What Qiaochu writes is true.

The compactness theorem for first-order logic is equivalent (in $\sf ZF$) to the completeness theorem, as well to the ultrafilter lemma, and several other interesting principles. The proof is due to Henkin [1], but I could not find the paper online, the proof appears in [2, Theorem 2.2].

It should be remarked that if we assume that both the compactness theorem holds, and Los theorem's hold, then we can prove the axiom of choice holds [4]. Therefore we have to be extra careful when we prove the compactness theorems using ultrafilters.

The ultrafilter lemma was proved to be independent from the axiom of choice (i.e. it cannot prove full choice) in 1965. In fact it is consistent that the axiom of countable choice fails, but the ultrafilter lemma holds (see [3], [2, Theorem 5.21]. Interestingly, this was about a decade after it was known that the ultrafilter lemma and the compactness theorem are equivalent.

To slightly generalize on Qiaochu's last point, if $\cal L$ is a well-orderable language (i.e. the cardinality of the language is an ordinal) then we can prove the compactness theorem for $\cal L$ without using the axiom of choice at all. The problem begins when the languages are not well-ordered. While it may seem strange, remember that if you use a language which includes a constant for every real number, then you can no longer prove that the language is well-orderabe.

Bibliography.

1. Henkin, Leon. "Metamathematical theorems equivalent to the prime ideal theorems for Boolean algebras." Bull. Amer. Math. Soc 60 (1954): 387-388.
2. Jech, Thomas J. The Axiom of Choice. Courier Dover Publications, 2008.
3. Halpern, James D., and Azriel Lévy. "The Boolean prime ideal theorem does not imply the axiom of choice." Proc. of Symposium Pure Math. of the AMS. Vol. 13. (1971): 83-134.
4. Howard, Paul E. "Los' theorem and the Boolean prime ideal theorem imply the axiom of choice." Proceedings of American Math. Society 49 (1975): 426-428.
-
Great answer, Mr Karagila! That exactly what I was looking for. – Mr X Jun 13 '13 at 5:02

In general, the compactness theorem is equivalent to the ultrafilter lemma, which is known to be strictly weaker than the axiom of choice (so is consistent with its negation) but independent of ZF. The models the compactness theorem asserts exist can be constructed using ultraproducts.

Over a countable alphabet, the compactness theorem is provable in ZF. This is because it can be proven from the completeness theorem, which over a countable alphabet is also provable in ZF.

-
The provability in ZF of the Compactness Theorem for theories over a countable alphabet seems not so clear. – André Nicolas May 26 '13 at 4:01
@André: in fact Wikipedia (en.wikipedia.org/wiki/…) asserts that compactness and completeness over a countable alphabet are equivalent over $\text{RCA}_0$ to the weak König lemma, which is provable in ZF. – Qiaochu Yuan May 26 '13 at 4:19
There's a small problem in using ultraproducts per se, because we usually think about Los theorem to finish the proof, but BPI+Los can prove AC. So we really can't use it. – Asaf Karagila May 28 '13 at 4:55
@Asaf: oh, interesting. Then I don't actually know what the proof that the ultrafilter lemma implies the compactness theorem looks like. – Qiaochu Yuan May 28 '13 at 5:11
Incidentally, I had this conversation two days ago with someone. Although he argued that it seems unlikely that compactness is provable from ultrafilters. It made me look st the proof Jech has in his book, but that one is quite messy and goes brought completeness first. (Jech also defines a notion of binary mess, and it is a mess!) – Asaf Karagila May 28 '13 at 6:08