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)?
[Math] Is the compactness theorem (from mathematical logic) equivalent to the Axiom of Choice
axiom-of-choicefirst-order-logicmodel-theory
Related Solutions
Consider the axioms $A$ for an ordered field; they are satisfied, most familiarly, by $\Bbb Q$ and $\Bbb R$ with their usual arithmetic operations and linear orders. Now add a constant symbol $c$, and for each positive integer $n$ let $\sigma_n$ be the sentence $$0<c\;\land\;\underbrace{c+c+\ldots+c}_{n\text{ times}}\le 1\;.$$
To find a model for any finite subset $F$ of $T=A\cup\{\sigma_n:n\in\Bbb Z^+\}$, start with $\Bbb Q$ with its usual operations and order, let $m=\max\{n\in\Bbb Z^+:\sigma_n\in F\}$, and interpret $c$ as $1/m$. This model satisfies every sentence in $A\cup\{\sigma_n:1\le n\le m\}$ and hence every sentence in $F$. In other words, $T$ is finitely consistent: this simply means that every finite subset of $T$ is consistent. (Actually, what I’ve really shown here is that $T$ is finitely satisfiable: every finite subset of it has a model. To say that $T$ is finitely consistent is, propertly speaking, to say that every finite subset of it is consistent, meaning that a contradiction cannot be derived from any finite subset of $T$. In this context the two are equivalent.)
Now consider the entire set $T$ of sentences. There is no way to interpret $c$ in either $\Bbb Q$ or $\Bbb R$ so as to get a model of the theory $T$, because neither $\Bbb Q$ nor $\Bbb R$ contains a positive number $r$ such that $nr\le 1$ for all positive integers $n$. Any object simultaneously satisfying $\sigma_n$ for all $n\in\Bbb Z^+$ must be a positive infinitesimal, something that doesn’t exist in the standard rational or real numbers. None the less, the compactness theorem assures us that $T$ does have a model: there is some ordered field that does contain at least one positive infinitesimal. This is by no means obvious, and actually constructing such a field is a non-trivial task, so in this case the compactness theorem is giving us a non-trivial conclusion for a very small amount of work.
Added: The compact theorem can also sometimes be used in reverse, so to speak. The simplest case of the infinite Ramsey theorem says:
Let $G$ be the infinite graph whose vertex set is $\Bbb N$ and that has an edge joining $m$ and $n$ whenever $m,n\in\Bbb N$ with $m\ne n$. (In other words, $G$ is the complete graph on $\omega$ vertices.) Color each edge of $G$ either red or blue. Then there is an infinite $A\subseteq\Bbb N$ such that all of the edges joining vertices in $A$ are the same color.
There is a very easy proof of this result using a free ultrafilter. We can use that easy result and the compactness theorem to prove the corresponding finite Ramsey theorem:
For each $n\in\Bbb Z^+$ there is an $r(n)\in\Bbb Z^+$ such that if $m\ge r(n)$, and each edge of $K_m$, the complete graph on $m$ vertices, is colored either red or blue, then there is a set $A$ of $n$ vertices of $K_m$ such that all of the edges between vertices in $A$ are the same color. Such a set $A$ of vertices is said to be monochromatic.
Let $B$ and $R$ be $2$-place relation symbols, and consider the following sentences:
$$\left\{\begin{align*} &\forall x\Big(\lnot B(x,x)\land\lnot R(x,x)\Big)\\ &\forall x,y\Big(B(x,y)\leftrightarrow B(y,x)\Big)\\ &\forall x,y\Big(R(x,y)\leftrightarrow R(y,x)\Big)\\ &\forall x,y\Big(x\ne y\to B(x,y)\lor R(x,y)\Big)\\ &\forall x,y\Big(\lnot\big(B(x,y)\land R(x,y)\big)\Big) \end{align*}\right.\tag{1}$$
Any model of $(1)$ can be thought of as a complete graph with each edge colored either red or blue: $B(x,y)$ is then interpreted as ‘the edge between $x$ and $y$ is blue’, and $R(x,y)$ as ‘the edge between $x$ and $y$ is red’.
Now for each $m\in\Bbb Z^+$ let $\varphi_m$ be the sentence $$\exists x_1\exists x_2\dots\exists x_m\left(\bigwedge_{1\le i<k\le m}x_i\ne x_k\right)\;;$$ $\varphi_m$ says that there are at least $m$ vertices. Finally, let $\psi$ be the rather ugly sentence
$$\forall x_1\forall x_2\dots\forall x_n\left(\bigwedge_{1\le i<k\le n}x_i\ne x_k\to\bigvee_{{1\le i<j\le n}\atop{1\le k<\ell\le n}}\Big(B(x_i,x_j)\land R(x_k,x_\ell)\Big)\right)\;;$$
$\psi$ says that if $A$ is any set of $n$ distinct vertices, there are two pairs of vertices in $A$ such that one pair are joined by a blue edge and the other by a red edge.
Suppose that this version of the finite Ramsey theorem is false. Then there is some $n\in\Bbb Z^+$ such that for all $m_0\in\Bbb Z^+$ there is an $m\ge m_0$ such that the edges of $K_m$ can be colored red and blue in such a way that no set of $n$ vertices of $K_m$ is monochromatic. This means that every finite subset of the axioms in $(1)$, $\psi$, and the sentences $\varphi_m$ is satisfiable. The compactness theorem then says that $(1)$, $\psi$, and the sentences $\varphi_m$ are all simultaneously satisfiable. But any model of this set of sentences would be a complete graph with infinitely many vertices (because of the $\varphi_m$) whose edges have been colored blue and red in such a way that no set of $n$ vertices is monochromatic (because of $\psi$). This contradicts the infinite Ramsey theorem, showing that the finite Ramsey theorem must be true.
This probably seems very roundabout, but once one is accustomed to using the compactness theorem, the argument is very straightforward and might intelligibly be shortened to this:
Suppose that there is some $n$ for which the finite Ramsey theorem fails. Then there are arbitrarily large counterexamples, complete graphs with red and blue edges in which no set of $n$ vertices is monochromatic. By compactness there is an infinite counterexample, contradicting the infinite Ramsey theorem.
I should probably mention that the finite Ramsey theorem can be proved directly in a way that actually gives a crude bound on $r(n)$. This proof isn’t particularly hard, but for someone already familiar with free ultrafilters and compactness arguments it’s a little harder than the argument given above.
From the top of my head, some "big" equivalents to the axiom of choice.
- Every commutative ring with a unity has a maximal ideal.
- Every surjection has an injective inverse.
- Every free abelian group is projective.
- Every divisible abelian group is injective.
- Skolem-Lowenheim theorems in model theory.
- Every two cardinals are comparable. This is used often in "hiding" where we have two sets and we know that one necessarily injects into the other.
- Every spanning set includes a basis (which is stronger than just the existence of a basis).
- Every set is included in $L[A]$ for some $A$. Where $L[A]$ is a model of $\sf ZFC$. This can be used to prove certain things in set theory.
There are many many many more, and one can scrounge through Rubin & Rubin Equivalents of the Axiom of Choice II to find many of them including proofs.
Best Answer
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.