Is every complete consistent theory satisfiable in ZF?

Question

It is well-known that the compactness theorem for FOL is equivalent to the Boolean Prime Ideal Theorem over ZF, so it is a weak choice principle.

The whole strength of BPIT in the proof of compactness is used in extending a consistent theory to a complete consistent theory. In fact, it is not hard to see that BPIT is equivalent to „every consistent theory can be extended to a complete consistent theory“.

But what if the theory in question is already complete?

Question: does ZF prove that every complete consistent first order theory has a model?

When building a Henkin model, one seemingly has to first Skolemize the theory. In general it is not possible to complete that theory again, even when one has started with a complete theory:

Suppose we live in a model of ZF where there is a collection $\mathcal X$ of nonempty finite sets without a choice function. Consider the language which has a constant $c_x^X$ and unary relation symbol $U_X$ for each $x\in X\in\mathcal X$. Let $T^\prime$ be the theory which says that members of $U_X$ are exactly the $c^X_x$ for $x\in X$. Clearly this has a model so extends to some complete theory $T$. But from any completion of a Skolemization, one can read off a choice function for $\mathcal X$ by asking which one of the $c^X_x$ is the chosen witness of $\exists y U_X(y)$. So such a thing cannot exist.

Answer 1

Note: This answer has been subsumed by my more recent answer. But I've left this older post up (it actually contains two separate answers) since there may be some independent interest in it, and there are also comments here that wouldn't make any sense on the other answer.

But the other answer is better; it fully resolves the status in ZF of the statement "Every complete consistent first-order theory has a model."

---

This older post contains two answers.

Both solutions show that ZF is consistent with the statement "there is a first-order theory that is complete and consistent but that has no model." The old method (based on ultrapowers) finds a model of ZF + DC, not just ZF, but it requires a large cardinal assumption. The new method (based on forcing) doesn't need any large cardinal assumption, but it just produces a model of ZF (not DC, as far as I know).

---

** OLD ANSWER 2 ** (No large cardinal required)

We'll give a consistent extension of ZF (without the axiom of choice) in which there is a first-order theory that is complete and consistent but that has no model.

Specifically, work in ZF + "there is a set $I$ that cannot be linearly ordered" (this is known to be consistent relative to ZF).

For convenience, we'll assume the existence of a transitive set $M$ which contains $I$ as a member and which is a model of ZF. But an examination of the proof will show that $M$ only needs to satisfy finitely much of ZF, so a transitive model $M$ that makes the proof go through provably exists.

Note that $M$ satisfies "$I$ cannot be linearly ordered" (since any linear ordering of $I$ in $M$ would be a linear ordering of $I$ in V).

Consider the partial ordering $\scr P$ of all finite sequences of pairwise distinct members of $I,$ ordered by inclusion. This partial ordering belongs to $M,$ and forcing over it would add a counting of $I.$ We'll consider this notion of forcing over $M,$ but we won't actually pass to a generic extension $M[G].$

In V, define the language $\mathscr L$ to consist of:

• a two-place relation symbol $\in;$

and

• a constant symbol $\mathbf c$ for each $c\in M.$

(Every sentence in $\scr L$ is, of course, a sentence in the language of forcing over $M\text{.}$ $\scr L$ just doesn't include a symbol for the generic filter.)

Let $T$ be the theory of all sentences in the language $\scr L$ that, according to $M,$ are forced to be true by the empty condition in $\scr P$ (or, equivalently, by all conditions in $\scr P).$

Clearly $T$ is consistent.

We claim that $T$ is complete. If not, there is some sentence $\varphi$ in $\scr L$ and there are conditions $p, q\in\scr P$ such that, in $M,$ $p\Vdash\varphi$ and $q\Vdash\neg\varphi.$ (Recall that $\varphi$ is a sentence about a hypothetical generic extension $M[G],$ but $\varphi$ doesn't reference $G$ at all, just members of $M.)$ Without loss of generality we can assume that $p$ and $q$ are of the same length (if not, simply extend the shorter one). We can find an automorphism in $M$ of $\scr P$ mapping $p$ to $q$ (the axiom of choice isn't needed for this because it only involves rearranging finitely many members of $I.)$ Since $\varphi$ doesn't mention the generic filter, it follows that $p\Vdash\varphi$ iff $q\Vdash\varphi,$ contradicting our assumption.

So $T$ is complete and consistent. Suppose that $T$ has a model $\langle M'; E\rangle,$ aiming at a contradiction.

The empty condition forces $\text{''}\omega\text{ can be mapped onto }\mathbf I\text{'',}$ so it forces the statement $\text{''}\mathbf I$ can be linearly ordered." It follows that $M'\models\text{''}\mathbf I$ can be linearly ordered."

We can conclude that, in V, there is a linear ordering of the $M'\text{-members}$ of the $M'\text{-interpretation}$ of $\mathbf I.$ [Note that the $\omega$ of $M'$ may be nonstandard (according to V) and may not even be countable (again according to V), but that's OK — its ordering is still a linear ordering (in V), which is sufficient.]

But, in V, $I$ can be embedded one-to-one in the set of $M'\text{-members}$ of the $M'\text{-interpretation}$ of $\mathbf I$ (map each $i\in I$ to the interpretation of $\mathbf i$ in $M'.)$

It follows that $I$ can be linearly ordered in V, which is a contradiction.

Therefore $T$ can't have a model.

---

** OLD ANSWER 1 ** (Large cardinal assumption required)

Using a large cardinal assumption, we'll give a consistent extension of ZF + DC (without the full axiom of choice) in which there is a first-order theory that is complete and consistent but that has no model.

Specifically, work in ZF + DC + "$\aleph_1$ is a measurable cardinal" + "every ultrafilter on $\omega$ is principal". (This theory certainly follows from the very strong theory ZF + AD + DC; a non-principal ultrafilter on $\omega$ would be a set of reals that's not Lebesgue measurable and also doesn't have the property of Baire. But the theory is much weaker than that; I think it's equiconsistent with ZFC + the existence of a measurable cardinal.)

Let $\mathscr U$ be a countably complete non-principal ultrafilter on $\aleph_1.$ Let $\mathrm{HC}$ be the collection of hereditarily countable sets; this set is transitive, and it contains every countable ordinal and every subset of $\omega.$

Define the language $\mathscr L$ to consist of:

• a two-place relation symbol $\in;$

and

• a constant symbol $\mathbf f$ for each function $f\colon\aleph_1\to \mathrm{HC}.$

Consider the theory $T$ consisting of all sentences $\varphi(\mathbf{f_1},\dots,\mathbf{f_n})$ in the language $\mathscr L$ such that the set $$\{\alpha\lt\omega_1 \mid \mathrm{HC}\models \varphi(f_1(\alpha),\dots,f_n(\alpha))\}$$ belongs to the ultrafilter $\mathscr U.$

(Note that the Fundamental Theorem of Ultrapowers can fail in the absence of the axiom of choice, but $T$ is the set of all sentences that would hold in the ultrapower $\mathrm{HC}^{\aleph_1}/\mathscr U$ if the Fundamental Theorem of Ultrapowers were true.)

You can check that the theory $T$ is both complete and consistent. Suppose, aiming at a contradiction, that $T$ has a model $M.$

For any $x\in\mathrm{HC},$ let $c_x\colon\aleph_1\to\mathrm{HC}$ be the constant function whose value is always $x.$ Define an elementary embedding $i\colon\mathrm{HC} \prec M$ by setting $i(x)$ equal to the interpretation in $M$ of the constant symbol $\mathbf{c_x}.$

We claim that the natural numbers of $M$ are all standard. Let $e$ be any member of $M$ such that $M\models e\lt\omega$. Then $\{X\subseteq\omega \mid M\models e\in i(X)\}$ is an ultrafilter on $\omega.$ But any such ultrafilter must be principal, so $e$ must be a standard natural number.

$\mathrm{HC}$ satisfies "Every ordinal is countable," so $M$ must also satisfy "Every ordinal is countable" (since the two models satisfy the same first-order sentences).

But now consider the identity function $\mathrm{id}$ on $\aleph_1.$ The interpretation in $M$ of the constant symbol $\mathbf{id}$ is, according to $M,$ an ordinal, so it must be countable according to $M.$ In other words, $M\models$ "there is a function mapping $\omega$ onto $\mathbf{id}\text".$

Since the $\omega$ of $M$ is standard, this yields (in the universe) a function mapping $\omega$ onto $\{x\in M \mid M\models x\in \mathbf{id}\}.$

And this gives a contradiction: $\{x\in M \mid M\models x\in \mathbf{id}\}$ is uncountable (in the universe), since $i$ restricted to $\omega_1$ is a 1-1 map from $\omega_1$ to $\{x\in M \mid M\models x\in \mathbf{id}\}.$

So $T$ can't have a model.

Answer 2

Note: This is intended to replace my earlier (less complete) answer. But I've left the older answer up since there may be some independent interest in it, and there are also comments there that wouldn't make any sense on this new answer.

The answer below is better in that it fully resolves the status in ZF of the statement "Every complete consistent first-order theory has a model."

---

Theorem (ZF): The statement "Every complete consistent first-order theory has a model" is equivalent over ZF to the Boolean Prime Ideal Theorem (BPIT).

It's sufficient to show the implication from left to right, since BPIT is known to be equivalent to the statement "Every consistent first-order theory has a model."

So assume that every complete consistent first-order theory has a model. We'll show that BPIT holds by proving the following equivalent statement: Every proper filter over a set $I$ can be extended to an ultrafilter over $I.$ ("Proper" here means that the empty set does not belong to the filter.)

First, however, we'll prove a lemma (in ZF, without using the axiom of choice):

Lemma (ZF): Every proper filter on a countable Boolean algebra can be extended to an ultrafilter.

Proof of Lemma: Let $B$ be a countable Boolean algebra, and let $\scr F$ be a proper filter on $B.$

Let $b_0, b_1, b_2, \dots\;$ be an enumeration of the non-zero members of $B.$

Define $\scr E$ to be $\{x\in B \mid x' \not\in \scr F\}.$ Clearly we have that $\scr F \subseteq \scr E$ and $0 \not\in\scr E.$

Note that the complement of $\scr E$ is closed under join: If $a$ and $b$ are not in $\scr E,$ then $a'$ and $b'$ are in $\scr F,$ so their meet $a'\cdot b'$ is in $\scr F,$ and it follows that $a+b$ is not in $\scr E.$

Define a sequence of members of $B$ by induction, as follows: $$\begin{align} u_0 &= 1; \\ u_{n+1} &= \begin{cases} u_n\cdot b_n, &\text{ if }u_n\cdot b_n \in \scr E,\\ u_n\cdot b_n\hspace{1px}', &\text{ otherwise}. \end{cases} \end{align}$$

You can see by induction that each $u_n$ belongs to $\scr E.$ (Clearly $u_0\in\scr E.$ For the induction step, assume $u_n\in\scr E.$ Then we have $u_n\cdot b_n + u_n\cdot b_n\hspace{1px}' = u_n,$ which is in $\scr E.$ So, by the closure under join of the complement of $\scr E,$ at least one of $u_n\cdot b_n$ and $u_n\cdot b_n\hspace{1px}'$ must be in $\scr E.$ It follows that $u_{n+1}\in\scr E.)$

So $u_0 \geq u_1 \geq u_2 \geq \dots,$ and no $u_n$ is equal to $0.$

You can check that $\{x\in B \mid (\exists n)(x \geq u_n)\}$ is an ultrafilter on the Boolean algebra $B.$ $\tag*{$\blacksquare$}$

Now that the lemma is proven, assume that every complete consistent first-order theory has a model, and let $D$ be a proper filter over a set $I.$ We'll show that $D$ can be extended to an ultrafilter.

For convenience, we'll assume the existence of a transitive set $M$ which contains $2^I$ and $D$ as members and which is a model of ZF. But an examination of the proof will show that $M$ only needs to satisfy finitely much of ZF, so a transitive model $M$ of enough of ZF to make the proof go through provably exists.

Consider the partial ordering $\scr P$ of all finite sequences of pairwise distinct members of $2^I,$ ordered by inclusion. This partial ordering belongs to $M,$ and forcing over it would add a counting of $2^I.$ We'll consider this notion of forcing over $M,$ but we won't actually pass to a generic extension $M[G].$

In V, define the language $\mathscr L$ to consist of:

• a two-place relation symbol $\in;$

and

• a constant symbol $\hat c$ for each $c\in M.$

(Every sentence in $\scr L$ is, of course, a sentence in the language of forcing over $M\text{.}$ $\scr L$ just doesn't include a symbol for the generic filter.)

Let $T$ be the theory of all sentences in the language $\scr L$ that, according to $M,$ are forced to be true by the empty condition in $\scr P$ (or, equivalently, by all conditions in $\scr P).$

Clearly $T$ is consistent.

We claim that $T$ is complete. If not, there is some sentence $\varphi$ in $\scr L$ and there are conditions $p, q\in\scr P$ such that, in $M,$ $p\Vdash\varphi$ and $q\Vdash\neg\varphi.$ (Recall that $\varphi$ is a sentence about a hypothetical generic extension $M[G],$ but $\varphi$ doesn't reference $G$ at all, just members of $M.)$ Without loss of generality we can assume that $p$ and $q$ are of the same length (if not, simply extend the shorter one). We can find an automorphism in $M$ of $\scr P$ mapping $p$ to $q$ (the axiom of choice isn't needed for this because it only involves rearranging finitely many members of $2^I).$ Since $\varphi$ doesn't mention the generic filter, it follows that $p\Vdash\varphi$ iff $q\Vdash\varphi,$ contradicting our assumption.

So $T$ is complete and consistent. It follows from our assumption that $T$ has a model $\langle M'; E\rangle$ (possibly not well-founded).

Let $S$ be $2^I;$ $\hat S$ is the constant symbol in the language of forcing for the power set of $I$ in the ground model. The sentence "There exists a one-to-one function mapping $\omega$ onto $\hat S\,$" is forced by the empty condition. It follows that the empty condition forces the sentence "$\hat S$ is a countable subset of the power set of $I,$ and $\hat S$ is a Boolean algebra under the operations of union, intersection, and complementation."

The empty condition also forces that $\hat D$ is a filter on the Boolean algebra $\hat S.$ It follows that the empty condition forces the sentence "There exists an ultrafilter on the Boolean algebra $\hat S$ that extends $\hat D."$

All these sentences that are forced by the empty condition are satisfied by the model $M'.$ So there is some $U\in M'$ such that $M'\models\;"U$ is an ultrafilter on the Boolean algebra $\hat S$ that extends $\hat D."$

Finally, we can see that, in V, the set $\{X\subseteq I \mid M'\;\models\hat X\in U\}$ is an ultrafilter on $I$ extending $D.$