Can first-order logic compactness theorem be used to prove extensibility of every partial ordering to a linear ordering?

254 Views Asked by At

So, assume there is a set $X$ with some partial ordering on it.

Surely, we can consider a signature $\sigma$ that has $=, <$ and a constant $c_x$ for every $x \in X$. We can then consider a theory $T$ consisting of formulas of the form $c_x = c_x$ for all $x \in X$ as well as $c_x < c_y$ for those $x, y \in X$ for which there is corresponding ordering. Clearly, $X$ (along with the natural interpretation of $=, <$ and constants) is a model for such theory.

What do we do next? Let's add a formula $\varphi$ stating that every pair of elements is comparable. It's easy to show that any finite subset $U$ of formulas of $T \cup \{ \varphi \}$ is consistent (since the subset of $X$ corresponding to the constants mentioned in formulas in $U$ is finite, and extending the partial ordering to a linear ordering, which is trivial on finite sets, would yield a model of $U$). Thus, by the compactness theorem, $T \cup \{ \varphi \}$ itself is consistent and thus has a model $M$.

The remaining step is unclear to me, though. Clearly, $X \subset M$ (as there must be an element for every constant), but showing that $X$ can, in fact, be equal to $M$ and still be a model, is not obvious to me. I even tried to tighten the requirements for the theory by considering only normal models (thus $M$ is also normal), but it doesn't help much — it's obvious that one can just remove the excessive elements, but how to prove this rigorously?