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)?

up vote 23 down vote accepted

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 Łoś 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. "Łoś’ 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
  • 1
    @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

To supplement the other answers with some references at a more introductory level:

  • [1, p.109]: “In ZF, the Compactness Theorem (CTh) is a weakening of AC. ZF does not prove CTh, since there are models of ZF in which $\mathcal{P}(\mathbb{R})$ cannot be totally ordered. Also, ZF+CTh does not prove AC, or even that $\mathbb{R}$ can be well-ordered. Working in ZF, one can prove that CTh is equivalent to the Propositional Compactness Theorem, and to the Completeness Theorem. Also, in ZF, one can prove the Compactness and Completeness Theorems in the case that $\mathcal{L}$ is well-ordered;”

  • [2, Thm. I.15.13 on p.90] is the completeness theorem proved from AC+ (Def. I.3.3, p.19: “every set can be well-ordered”). Below Thm, I.15.13, a comment reads “It is known that the Completeness Theorem is not provable in ZF [...]. However, the Completeness Theorem is provable in ZF$^-$-P in the case that $\mathcal{L}$ can be well-ordered (in particular, when $\mathcal{L}$ is countable).”

    Note that, in ZF, AC+ is equivalent to the axiom of choice [2, Thm. I.12.1 on p.68].

  • [3, p.144]: “We may then state the Gödel Completeness Theorem as $$ \forall\, X\; (CON(X) \leftrightarrow \exists\, \mathfrak{M}\; (\mathfrak{M} \models X)) $$ and prove it within ZF (AC can be avoided here since the language is countable).”

  • [4, p.24]: In the course of proving results leading to the compactness theorem: “Note: If the vocabulary of $\mathcal{L}$ is finite or denumerable, then Zorn's lemma (and the axiom of choice) can be avoided in the usual way by enumerating the formulae in $F_{\mathcal{L} }$.”

[1] Kenneth Kunen, The foundations of mathematics, College Publications, 2009 (revised ed. 2012)

[2] Kenneth Kunen, Set theory, College Publications, 2011 (revised ed.2013)

[3] Kenneth Kunen, Set theory: An introduction to independence proofs, North Holland, 1980

[4] Albert C. Leisenring, Mathematical logic and Hilbert's $\varepsilon$-symbol, MacDonald Technical & Scientific, 1969

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.