Proof that a well-ordering is $\omega$-saturated only if it is finite

Question

I wanna prove that an infinite well-ordering is not $\omega$-saturated. How can I do this? Does the proof involve Lowenheim-Skolem theorem?

Answer 1

As indicated in Noah's and Atticus's answers, and my comment, it's probably best to understand this fact as an application of the theorem that $\omega$-saturated models realize all consistent types in $\omega$-many free variables, so an $\omega$-saturated infinite linear order realizes the type of a countable descending sequence. But in this answer, I'll try to explain how you could answer the question without using the more general theorem.

Let $(M;<)$ be an infinite $\omega$-saturated linear order. We would like to show that $M$ is not a well-order. To do that, we would like to build an infinite descending chain in $M$. Let's try to do this by induction. We start by picking an element $a_0$. Then, having chosen $a_n$, we pick some $a_{n+1}<a_n$.

There's an obvious problem with this strategy: What ensures that there is some $a_{n+1}<a_n$? That is, if we accidentally pick $a_n$ to be the least element of the order, we get stuck. Saturation is no help: if $a_n$ is the least element of $M$, then $M\models \forall x\, \lnot (x < a_n)$, so the formula $x<a_n$ is just inconsistent.

Ok, so instead let's pick our sequence by induction, making sure to never pick the least element. But now what ensures that there is some $a_{n+1}<a_n$ which is not the least element? If $a_n$ has only one element below it in the order, we again get stuck. Clearly, we're in trouble if we ever pick an element $a_n$ with only finitely many elements below it in the order.

New idea: Make sure that each element of the sequence has infinitely many elements below it. So we start by picking an element $a_0$ with infinitely many elements below it. Then, having chosen $a_n$ with infinitely many elements below it, we pick some $a_{n+1}<a_n$ such that $a_{n+1}$ has infinitely many elements below it. But what ensures that there is some $a_{n+1}<a_n$ with infinitely many elements below it? Now saturation is comes into play: This condition amounts to realizing a certain type. Details after the break.

---

For each natural number $n>0$, let $\varphi_n(x)$ be the formula $$\exists y_1\dots\exists y_n\,(y_1<y_2<\dots<y_n < x).$$ Let $\Phi(x)$ be the partial type $\{\varphi_n(x)\mid n\in \mathbb{N}\}.$ This partial type says "$x$ has infinitely many elements below it".

We construct a descending sequence $(a_n)_{n\in \mathbb{N}}$ from $M$ by induction, ensuring that each $a_n$ realizes $\Phi(x)$.

In the base case, we show that $\Phi(x)$ is consistent by compactness: Given any finite subset $\{\varphi_n\mid 1\leq n\leq N\}$, we can pick any $N+1$ elements of $M$, listed in increasing order $b_1<\dots<b_{N+1}$ (here we use the fact that $M$ is infinite). Then taking $x = b_{N+1}$, the elements $b_i$ serve as witnesses for the variables $y_i$ in the formulas $\varphi_n$ with $n\leq N$. Since $\Phi(x)$ is consistent and $M$ is $\omega$-saturated, we can find $a_0\in M$ realizing $\Phi(x)$.

Now suppose by induction that we have picked $a_n$ realizing $\Phi(x)$. We show that the partial type $\Phi(x)\cup \{x<a_n\}$ is consistent by compactness: Given any finite subset $\{\varphi_n\mid 1\leq n\leq N\}$, recall that $a_n$ satisfies $\varphi_{N+1}$. So we can find $b_1<\dots<b_{N+1}<a_n$ in $M$. Then taking $x = b_{N+1}$, we have $x < a_n$, and the elements $b_i$ serve as witnesses for the variables $y_i$ in the formulas $\varphi_n$ with $n\leq N$. Since $\Phi(x)\cup \{x<a_n\}$ is consistent and $M$ is $\omega$-saturated, we can find $a_{n+1}\in M$ realizing $\Phi(x)\cup \{x<a_n\}$.

Answer 2

A useful fact is that an $\aleph_0$-saturated structure realizes any (partial) type in $\omega$-many variables with parameters from a finite set. Ie, if $\mathfrak{M}$ is an $\aleph_0$-saturated $\mathcal{L}$-structure, $A\subseteq M$ is a finite subset, and $\Sigma(v_i)_{i\in\omega}$ is a finitely satisfiable set of $\mathcal{L}_A$ formulas in $\omega$-many free variables, then $\Sigma(v_i)_{i\in\omega}$ is realized in $\mathfrak{M}$. See eg here for a proof. (The analogous result holds for all infinite cardinals.)

This fact allows us to show your result. Let $(M,\leqslant)$ be an $\aleph_0$-saturated well-order, and consider the collection of formulas $\Sigma(v_i)_{i\in\omega}=\{v_i>v_j\}_{i<j\in\omega}$; in other words, $\Sigma(v_i)_{i\in\omega}$ expresses that the $v_i$ form a strictly descending chain. Since well orders are total orders, if $M$ is infinite then $\Sigma(v_i)_{i\in\omega}$ is finitely satisfiable, and hence by $\aleph_0$-saturation is satisfied by elements $m_0>m_1>\dots$ of $M$. But now the set $\{m_i\}_{i\in\omega}$ is a subset of $M$ without a least element, contradicting that $<$ is a well-order.

Answer 3

The class of well-orderings has a very nice property: it's exactly the class of structures which $(i)$ satisfy a particular first-order theory (the theory of linear orders) and $(ii)$ do not have a certain countable "bad configuration." Re: $(ii)$, the relevant "bad configuration" is:

An infinite descending sequence.

The "saturation slogan" is, "all possible configrations exist." Of course it's more complicated than that - how much saturation you have determines the size of the conigurations the slogan applies to - but the basic idea is sound. This suggests the following line of attack: show that in an infinite $\omega$-saturated linear order, the countable "bad configuration" above must occur. This will be a corollary of a more general fact:

Suppose $\mathcal{M}$ is $\omega$-saturated and $p$ is a finitely satisfiable $\omega$-type over $\mathcal{M}$. Then $p$ is realized in $M$.