Axiomatising Wellorder

Question

It may be of use to recall what a strict total order is; namely a binary relation satisfying irreflexivity, transitivity and totality, as formalised below: $$\forall x(\neg P_{1}(x,x))$$ $$\forall x \forall y \forall z((P_{1}(x,y) \land P_{1}(y,z)) \to P_{1}(x,z))$$ $$\forall x \forall y (P_{1}(x,y) \lor x \dot{=}y \lor P_{1}(y,z))$$

Furthermore, a well-order is a strict total order, $\mathcal{A}=\langle A; <;-\rangle $ for which there is no infinite sequence $\{x_{j}\}_{j \in \mathbb{N}}$ of elements in $A$, such that $x_{j+1}<x_{j}$ for all $j \in\mathbb{N}$.

Now, what I want to show is:

Well-order is not axiomatizable.

My idea so far has been to suppose that $\Gamma$ axiomatizes the class of well-orderings, add countably many constants $c_{j}$ and show that $\Gamma \cup \{c_{j+1}<c_{j}:j\in\mathbb{N}\}$ has a model. However, I find it difficult to follow through on the last step, namely show that $\Gamma \cup \{c_{j+1}<c_{j}:j\in\mathbb{N}\}$, which is why I ask for help from this forum.

Answer 1

You are almost there.

Suppose $\Gamma$ is a set of first-order sentences with a non-logical binary relation symbol $P$ such that, for every $n$, there is a model of $\Gamma$ in which $P$ is a well-order on at least $n$ elements of the domain.

If this supposition doesn't hold, i.e. if for any set of sentences $\Gamma$ there is a $n$ such that models of $\Gamma$ can't have well-orderings longer than $n$, that already means that there is no general theory $\Gamma$ whose models of its relation symbol are just the well-orderings (finite and infinite). So grant the supposition.

Then add new constants $c_i$ (distinct for every natural nuumber $i$), and consider the theory $\Gamma^+$ which is $\Gamma$ plus every $P(c_{j + 1}, c_j)$. Any finite selection of $\Gamma^+$'s axioms has a model, given our supposition. [There will be $n$ constants $c_j$ featured; take a model where $P$ is a well-order on at least $n$ elements, and then use the $c_j$ to name $n$ elements in the right order.] So by compactness $\Gamma^+$ has a model. But this model will have an infinite downward $P$-chain, so isn't well-ordered. So the reduct of this model to the original language withough the added constants will be a non-well-ordered model of $\Gamma$. So $\Gamma$ can't be a theory whose models for its binary relation $P$ are all and only the well-orderings.

Answer 2

Another method, which may be slightly simpler, is to use ultraproducts and Los theorem, if you have studied about them.

Note that $\cal N=\langle\Bbb N,<\rangle$ is a strict well-order. Suppose that it was axiomatizable then every ultraproduct of well-orders would be a well-order. Consider any free ultrafilter on $\Bbb N$, $\cal U$ then the structure: $$\cal M=N^\Bbb N/U$$

Should be a well-order as well, since by Los theorem both $\cal N$ and $\cal M$ have the same first-order theory. However it is not hard to find a decreasing sequence in $\cal M$. Such sequence, for example, is letting $f_0$ to be the identity function, and $f_{n+1}(k)=f_n(k-1)$ (and $0$ for $k=0$).