Franklin's Notes

Theories of order

In first-order logic , the theory of partial order has the language $\mathscr{L}={\leq}$ and the following three axioms:

1. $(\forall xyz)((x\leq y\land y\leq z)\rightarrow x\leq z)$
2. $(\forall xy)((x\leq y \land y\leq x)\rightarrow x\equiv y)$
3. $(\forall x)(x\leq x)$

Every model of this theory consists of $\langle A,\leq\rangle$, where $A$ is a set partially ordered by $\leq$. The theory of total order (linear order, simple order) has the following additional axiom:

4. $(\forall xy)(x\leq y\lor y\leq x)$

which states, in plain English, that any two elements of the order are comparable - one must be greater than or equal to the other. Additional axioms may be added to place further restrictions on the types of orders under consideration. For instance, the theory of dense total orders has the following additional axioms:

5. $(\forall xy)(x < y \rightarrow (\exists z)(x<z\land z<y))$
6. $(\exists xy)(x\not\equiv y)$

where $x<y$ is shorthand for $x\leq y \land x\not\equiv y$.

There is no theory of well-orders . One of the exercises from Chang and Kiesler listed here is to show that the models $\langle \omega,\leq\rangle$ and $\langle \omega+\omega^d+\omega,\leq\rangle$ are elementarily equivalent. Thus, if the former is a model of any theory, so is the latter, and vice versa. But the former is a well-order and the latter is not, meaning that there cannot exist a theory whose models are precisely the well-ordered total orders. In fact, we can go even further with the following exercise from Chang and Kiesler:

Exercise 1. (Chang and Kiesler) Let $\mathfrak{A}=\langle A,\leq,...\rangle$ be an infinite model such that $\leq$ well-orders $A$. Show that there is a model $\mathfrak{A}'=\langle A',\leq',...\rangle$ such that $\leq'$ does not well-order $A'$.

Solution. We will use what Chang and Kiesler call the "method of diagrams". Let $\mathfrak{A}^\ast$ be the expansion on $\mathfrak{A}$ to a larger language in which one constant element is added for each element of $A$ that is not already the interpretation of a constant, so that each element is the interpretation of exactly one constant. Further, let $c_0,c_1,c_2,...$ be a new set of constant symbols not already used in the new language, and let $\Delta$ be the set of sentences Let $\Sigma$ be the set of sentences that are true in $\mathfrak{A}'$. Then every finite subset of $\Sigma\cup\Delta$ is consistent, for each finite subsets only contains at most finitely many sentences in the form $c_{i+1}<c_i$, and if there are exactly $n$ such sentences, the constants used in these sentences can be consistently interpreted as elements of some finite suborder of $A$ of length $2n$. This means, by the compactness theorem, that $\Sigma\cup\Delta$ has a model. Let $\mathfrak{A}'$ be the reduct of this model to the original language without added constant symbols. This model is elementarily equivalent to $\mathfrak{A}$, but it is not well-ordered, because its elements corresponding to the interpretations of the constant symbols $c_i$ in the expanded model form an infinite descending chain. $\blacksquare$




back to home page