Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
The proof of compactness and completeness of $\mathscr{FOL}$ (with Hilbert system) used Zorn's lemma. And Zorn's lemma is equivalent to the Axiom of choice in $ZF$.
So my question is can they be proved without Zorn's lemma, or is first-order logic incompact and incomplete consistent with $ZF$ without AC?
The answer is that it is consistent that completeness and compactness of FOL fail in some models of ZF, and that they are provable from a slightly weakened choice principle which is The Boolean Prime Ideal theorem (and its many many useful equivalences).
The compactness theorem for FOL is equivalent to the completeness theorem for FOL in ZF. Both are equivalent to the Boolean Prime Ideal theorem, which in turn is equivalent to many more useful principles such as the ultrafilter lemma, and Tychonoff theorem for Hausdorff spaces.
There are models in which all these fail, so it is consistent indeed. For example, all the above imply that every set can be linearly ordered. In models where some sets cannot be linearly ordered they fail.
One example is a model in which there is a countable collection of pairs whose product is empty. Indeed if every set could be linearly ordered, the union of these pairs could have been linearly ordered and we could fix one ordered and choose the minimal element from every pair, and the product would not be empty then.
One can directly prove this as a compactness argument. Let $S$ be the union of all the pairs. Let $T$ be the theory which states that the universe is linearly ordered, and for every $s\in S$ we add a constant $c_s$ and the axiom which says that $c_s\neq c_t$ whenever $t\neq s$. Every finite fragment of the theory is consistent, simply because a finite set of axioms would correspond to a finite collection of the pairs which can be linearly ordered without any use of the axiom of choice (and the existence of a model implies consistency, it's the other direction which requires choice). However the entire theory does not have a model because a model of the theory would have to be a linear ordering of $S$ which, as we remarked above, is contradictory to the fact that the pairs have an empty product.
I should also remark that for a countable, or generally well-orderable language (including variables and what have you) the compactness theorem is true in ZF.
As it turns out, the compactness and completeness theorems are weak versions of AC. See here.
