Two questions about the first order theory of well ordered sets.

Question

Consider the class of well-orderings $W$. Although that class is not first-order axiomatizable, it has an associated first order theory $Th(W)$. Is it finitely axiomatizable? I conjecture that, in addition to the axioms for linear orders, all you need are the axiom that there is a minimum element, and that every element except the last if there is one has an immediate successor. Is this true, or do you need a bit more, or in fact do you need infinitely more?

My second question is, can someone exhibit a model of the first-order theory of well ordered sets that is not itself a well-ordering?

Answer 1

Re: the second question there's a very concrete example: a standard exercise using Ehrenfeucht-Fraisse games is to show that $\mathbb{N}\equiv\mathbb{N}+\mathbb{Z}$. In particular, since $\mathbb{N}$ is a well-ordering, we have $\mathbb{N}+\mathbb{Z}\models Th(W)$.

• Here "$\mathbb{N}+\mathbb{Z}$" is shorthand for any linear order consisting of an initial segment isomorphic to $\mathbb{N}$, a final segment isomorphic to $\mathbb{Z}$, and nothing else. For an explicit example, we could consider $(\mathbb{N}\times\{0\})\cup(\mathbb{Z}\times\{1\})$ ordered by setting $(a,b)\trianglelefteq (c,d)$ iff $b<d$ or $b=d$ and $a\le c$.

---

Re: the first question, your guess is correct: any linear order with a least element and such that all but possibly one element has a successor is a model of $Th(W)$. This can be proved via Ehrenfeucht-Fraisse games as well, and of course yields many more concrete examples of non-well-ordered models of $Th(W)$, but is significantly more complicated.

Answer 2

Concerning the second question : take $(\omega, <)$, which is a well ordering.

In an elementary extension $\mathcal{M}$ of $\omega$, you can realize the (partial) type $\pi(\bar{x}) = \{x_m < x_n \ \big| \ m > n \in \omega\}$ since $\pi(\bar{x})$ is finitely satisfiable in $\omega$.

Hence, $\mathcal{M}$ is not well ordered despite being a model of $Th(W)$.

Answer 3

Regarding first question, an (infinite) axiomatization of $Th(W)$ seems to be given by :

• Axioms of linear orders

• An axiom scheme : for every first order formula $\varphi(x)$, the axiom $$\exists x \ \varphi(x) \to \big(\exists x \ (\varphi(x) \wedge \ \forall y \ \varphi(y) \to x \leqslant y ) \big) $$

These axioms imply that all elements but eventually one have an immediate successor, but the converse doesn't hold : consider $\mathbb{N} + \mathbb{Z} \times \mathbb{N}$. The set of non zero elements without immediate predecessor is definable, and does not have a minimum.