0
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ The title and body of your question say different things. $\endgroup$ Nov 22, 2020 at 14:32
  • $\begingroup$ I think I corrected the title. $\endgroup$
    – Jack
    Nov 22, 2020 at 14:34
  • 1
    $\begingroup$ Yep, that's better. $\endgroup$ Nov 22, 2020 at 14:35
  • $\begingroup$ I mean, the type of arbitrarily long decreasing chain is an obvious giveaway. $\endgroup$
    – Asaf Karagila
    Nov 22, 2020 at 14:37
  • $\begingroup$ Do you know the theorem that $\omega$-saturated models realize types in $\omega$-many free variables? $\endgroup$ Nov 22, 2020 at 14:38

3 Answers 3

3
$\begingroup$

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\}$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.