Franklin's Notes


Definability in total orders

This note is dedicated to my explorations of specific questions of definability relating to theories of total orders taking the form $\langle A,\leq\rangle$ in first-order logic . Here are some questions that I have not yet figured out how to answer:

We can build up a sequence of formulas $\varphi_n(v,w), \psi_n(v)$ to help us define elements of ordinals. Let's construct these formulas recursively as follows:






In plain English, these formulas can be interpreted as follows:

However, in a total order $\langle A,\leq\rangle$ in which $A$ happens to be an ordinal, these statements have more meaningful interpretations. We can show that $\varphi_1(v,w)$ states that $v$ is the smallest multiple of $\omega$ after $w$, and $\varphi_2(v,w)$ states that $v$ is the smallest multiple of $\omega^2$ after $w$, and in general, $\varphi_n(v,w)$ states that $v$ is the smallest multiple of $\omega^n$ after $w$. Similarly, $\psi_n(v)$ states that $v$ is either a multiple of $\omega^{n+1}$ or the first element of the order.

Therefore, if $A$ has an element corresponding to the ordinal $\omega^k$ for some $k$, this element is definable by the following statement:



...which states that $v$ is the smallest multiple of $\omega^k$ after the first element in the order. Additionally, if the element corresponding to some arbitrary ordinal $\alpha$ is definable, then the element corresponding to $\alpha+\omega^k$ for any $k$ is definable, since it may be similarly defined as the smallest multiple of $\omega^k$ greater than $\alpha$. Thus, recursively, we may define the elements corresponding to any finite sums of ordinals taking the form $\omega^k$. These are precisely the ordinals less than $\omega^\omega$! Hence, we have the following theorem:

Theorem 1. If $\langle A,\leq\rangle$ is a model of a total order and $A'\subset A$ is an initial segment of $A$ which is well-ordered , then any element of $A'$ corresponding to an ordinal less than $\omega^\omega$ is definable.

This also gives rise to the following result:

Theorem 2. If $\langle A,\leq\rangle$ is a model of a total order which contains an undefinable element, then at least one of the following must be true:
1. $\mathbb Z$ can be embedded in $A$
2. $\omega^\omega$ is the order type of an initial segment of $A$
3. $(\omega^\omega)^d$ is the order type of a final segment of $A$

Proof. Suppose $a\in A$ is an undefinable element. If the initial segment ${x\in A: x\leq a}$ is well-ordered, then it contains an initial segment isomorphic to $\omega^\omega$, as per the previous theorem. If it is not well-ordered, it must contain some infinitely descending sequence of elements, meaning that $\mathbb N^d$ can be embedded among the elements of $A$ less than or equal to $a$.

Now let us apply the same reasoning to the dual order of $A$. Note that every element definable in the dual order is definable in the original order, and vice versa. Hence, either the dual order contains an initial segment isomorphic to $\omega^\omega$, in which case $A$ contains a final segment isomorphic to $(\omega^\omega)^d$, or the set of elements less than or equal to $a$ in the dual order is not well-ordered, in which case $\mathbb N$ can be embedded among the elements of $A$ greater than or equal to $a$.

If $\mathbb N^d$ can be embedded among the elements less than or equal to $a$, and $\mathbb N$ can be embedded among those greater than or equal to $a$, then $\mathbb Z$ can be embedded in $A$. Hence, if cases $(2)$ and $(3)$ fail, then $(1)$ must hold, and we have the desired result. $\blacksquare$

The above proof implicitly uses the Axiom of Choice, but it suffices to assume that $A$ is a well-orderable set rather than assuming the Axiom of Choice in general.

Conjecture. $\omega^\omega\cdot 2$ is the first ordinal ordering which has undefinable elements.

model-theory

order-theory

definability

back to home page