0

36

0

$$$$

この文書はAlweさんの企画された Mathematical Logic Advent Calendar 2023 の15日目の記事です。まだ日本語を使わなくてすみません🙏。

I learned the following argument from Garrett Ervin.

Increasing continuous elementary chain

An *elementary chain* a sequence $C=\{M_i:i<\alpha\}$ of models over a common first-order language $\mathcal{L}$, indexed by ordinals $i$ below $\alpha$, such that for all $i\le j<\alpha$, $M_i\preceq M_j$ is an elementary extension.

We say $C$ is *increasing* if for all $i$ such that $i+1<\alpha$, it holds that $M_i\subsetneqq M_{i+1}$ is a proper extension.

We say $C$ is *continuous* if for all limit ordinals $\beta<\alpha$, it holds that $M_\beta=\bigcup_{i<\beta}M_i$ is the union of its predecessors $\{M_i:i<\beta\}$.

Main theorem

Let $M$ be an arbitrary model of size $\aleph_0$ over a countable language. The following hold:

- If $\kappa$ is an infinite cardinal, and $\alpha$ is an ordinal such that $\alpha<\kappa^+$, then there exists an increasing continuous elementary chain $\{M_i:i<\alpha\}$ of elementary extensions $M_i\succeq M$ of size $\kappa$, such that the models $\{M_i:i<\alpha\}$ are all isomorphic.
- There exists an increasing continuous elementary chain $\{M_i:i<\omega_1\}$ of elementary extensions $M_i\succeq M$ of size $\aleph_0$, such that the models $\{M_i:i<\omega_1\}$ are all isomorphic.
- Assume $\textsf{CH}$ or $\textsf{PFA}$ . There exists an increasing continuous elementary chain $\{M_i:i<\omega_2\}$ of elementary extensions $M_i\succeq M$ of size $\aleph_1$, such that the models $\{M_i:i<\omega_2\}$ are all isomorphic.
- If $\kappa$ is an infinite cardinal such that $\kappa^{<\kappa}=\kappa$, then there exists an increasing continuous elementary chain $\{M_i:i<\kappa^+\}$ of elementary extensions $M_i\succeq M$ of size $\kappa$, such that the models $\{M_i:i<\kappa^+\}$ are all isomorphic.

Assuming $\textsf{GCH}$ , this holds for every regular cardinal $\kappa$.

In the cases (2), (3), and (4), the elementary chain $\{M_i:i<\kappa^+\}$ is maximal: The next model $M_{\kappa^+}=\bigcup_{i<\kappa^+}M_i$ always has size $\kappa^+$, so it cannot be isomorphic to the earlier models $M_i$ of size $\kappa$.

It is currently an open question whether case (3) always holds in $\textsf{ZFC}$.

The following lemma reveals the combinatorial content of the main theorem.

An *increasing continuous chain* of models $C=\{M_i:i<\alpha\}$ is defined similarly as an increasing continuous elementary chain, except for all $i\le j<\alpha$, we no longer require $M_i\preceq M_j$ to be an elementary extension, but we instead assume $M_i\subseteq M_j$ is some extension (where the inclusion $M_i\subseteq M_j$ respects the function, relation, and constant symbols from the language).

Given an infinite cardinal $\kappa$ and an ordinal $\alpha$, the following are equivalent:

- For any model $M$ of size $\aleph_0$ over a countable language, there exists an increasing continuous elementary chain $\{M_i:i<\alpha\}$ of elementary extensions $M_i\succeq M$ of size $\kappa$, such that the models $\{M_i:i<\alpha\}$ are all isomorphic.
- There exists an increasing continuous chain $\{(I_i,{<}):i<\alpha\}$ of linear orders $(I_i,{<})$ of size $\kappa$, such that the linear orders $\{(I_i,{<}):i<\alpha\}$ are all isomorphic.

1 ⇒ 2

Let $M=(\mathbb{Q},{<})$. Then the increasing continuous chain $\{M_i=(I_i,{<}):i<\alpha\}$ of linear orders is what we wanted.

To prove the implication (2 ⇒ 1), we need a theorem by Ehrenfeucht–Mostowski.

Skolem hull, see [1] §5.2

Every complete first-order theory $T$ has an extension $T^*$ into an expanded first-order language $\mathcal{L}(T^*)\supseteq\mathcal{L}(T)$, such that $|T^*|=|T|$, and $T^*$ has *built-in Skolem functions*: For every formula $\phi(v,\bar{w})$ in the language of $T^*$, there is a function symbol $f_\phi(\bar{w})$ such that $T^*$ contains the sentence $\forall\bar{w}[(\exists v\,\phi(v,\bar{w}))\rightarrow\phi(f_\phi(\bar{w}),\bar{w})]$.

For every complete first-order theory $T$ with infinite models and every linear order $(I,{<})$, there is a model $\mathfrak{C}$ of $T$ with a sequence $\{a_i:i\in I\}$ of *order indiscernibles*: For every two increasing sequences $i_1<\ldots< i_n$ and $j_1<\ldots< j_n$ in $I$ and every formula $\phi(x_1,\ldots,x_n)$, we have $\mathfrak{C}\vDash\phi[a_{i_1},\ldots,a_{i_n}]\leftrightarrow\phi[a_{j_1},\ldots,a_{j_n}]$.

Given a complete first-order theory $T$ with built-in Skolem functions, a model $\mathfrak{C}\vDash T$ with order indiscernibles $\{a_i:i\in I\}$, and a suborder $I_0\subseteq I$, the *Skolem hull* of $\mathbf{I}_0=\{a_i:i\in I_0\}$ is the $\mathcal{L}(T)$-submodel $\text{EM}(\mathbf{I}_0)\subseteq\mathfrak{C}$ with universe $\{f_\phi^{\mathfrak{C}}(\bar{a}):f_\phi\in \mathcal{L}(T),\bar{a}\subseteq\mathbf{I}_0\}$.

Ehrenfeucht–Mostowski, see [1] §5.2

Let $T$, $\mathfrak{C}\vDash T$, $\mathbf{I}=\{a_i:i\in I\}$, and $\text{EM}({\cdot})$ be as in the definition above. For any $\mathbf{I}_0,\mathbf{I}_1\subseteq\mathbf{I}$, the following hold:

- $\text{EM}(\mathbf{I}_0)$ is a model of $T$ of size $|\mathbf{I}_0|+|T|$, and an elementary submodel of $\mathfrak{C}$.
- If $\mathbf{I}_0\subseteq\mathbf{I}_1$, then $\text{EM}(\mathbf{I}_0)\preceq\text{EM}(\mathbf{I}_1)$.
- More generally, every $(I,<)$-order-preserving $f:\mathbf{I}_0\to\mathbf{I}_1$ extends uniquely into an elementary embedding $\bar{f}:\text{EM}(\mathbf{I}_0)\to\text{EM}(\mathbf{I}_1)$.
- If $f:\mathbf{I}_0\to\mathbf{I}_1$ is an $(I,{<})$-order-preserving bijection, then $f$ extends uniquely into an isomorphism $\bar{f}:\text{EM}(\mathbf{I}_0)\cong\text{EM}(\mathbf{I}_1)$.

2 ⇒ 1

Let $\text{ED}(M)=\{\phi(c_{m_1},\ldots,c_{m_n}):M\vDash\phi[m_1,\ldots,m_n]\}$ be the *elementary/complete diagram* of $M$, so that $\text{ED}(M)$ is a countable complete first-order theory extending the theory $\text{Th}(M)$ of $M$, and every model $N\vDash\text{ED}(M)$ admits an elementary embedding $j_{M,N}:M\to N$ (mapping $m\mapsto c_m^N$), such that if $j_{N,N'}:N\to N'$ is an elementary embedding between models of $\text{ED}(M)$, then $j_{N,N'}\circ j_{M,N}=j_{M,N'}$ (see [1] Lemma 2.3.3).

Let $T\supseteq\text{ED}(M)$ be a countable complete first-order extension (in an expanded language) with built-in Skolem functions, and let $\mathfrak{C}\vDash T$, $\mathbf{I}=\{a_i:i\in I\}$, and $\text{EM}({\cdot})$ be as in the Ehrenfeucht–Mostowski theorem, where $I=\bigcup_{i<\alpha}I_i$.

For every $i<\alpha$, let $\mathbf{I}_i=\{a_i:i\in I_i\}$, and let $M_i=\text{EM}(\mathbf{I}_i)$. We can check that $\{M_i:i<\alpha\}$ is the elementary chain that we wanted:

- By the Ehrenfeucht–Mostowski theorem part (2), $\{M_i:i<\alpha\}$ forms an $\mathcal{L}(T)$-elementary chain. So their reducts $\{M_i\upharpoonright\mathcal{L}(M):i<\alpha\}$ form an $\mathcal{L}(M)$-elementary chain.
- By the Ehrenfeucht–Mostowski theorem part (1), every model $M_i$ is a model of $\text{ED}(M)$ of size $\kappa$. So by identifying the model $M$ with its isomorphic image $M\cong j_{M,M_0}(M)\preceq M_0$, the properties of $\text{ED}(M)$ from before imply that $M\preceq M_i$ for all $i<\alpha$ under this identification.
- From the assumption that $\mathbf{I}$ is a sequence of order indiscernibles, one can prove that $\text{EM}(\mathbf{J})\cap\mathbf{I}=\mathbf{J}$ for all $\mathbf{J}\subseteq\mathbf{I}$. This implies that since $\{\mathbf{I}_i:i<\alpha\}$ is increasing, the chain $\{M_i:i<\alpha\}$ is also increasing.
- From the definition of Skolem hulls, one can prove that if $\{\mathbf{J}_i:i<\beta\}$ is a chain of subsets $\mathbf{J}_i\subseteq\mathbf{I}$ (such that $i\le j$ implies $\mathbf{J}_i\subseteq\mathbf{J}_j$), then $\bigcup_{i<\beta}\text{EM}(\mathbf{J}_i)=\text{EM}(\bigcup_{i<\beta}\mathbf{J}_i)$. This implies that since $\{\mathbf{I}_i:i<\alpha\}$ is continuous, the chain $\{M_i:i<\alpha\}$ is also continuous.
- By the Ehrenfeucht–Mostowski theorem part (4), since the linear orders $\{(I_i,{<}):i<\alpha\}$ are all isomorphic, the models $\{M_i:i<\alpha\}$ are also all isomorphic.

In light of the lemma from the previous section, the main theorem is equivalent to the following proposition:

Main proposition

- If $\kappa$ is an infinite cardinal, and $\alpha$ is an ordinal such that $\alpha<\kappa^+$, then there exists an increasing continuous chain $\{(I_i,{<}):i<\alpha\}$ of linear orders of size $\kappa$ which are all isomorphic.
- There exists an increasing continuous chain $\{(I_i,{<}):i<\omega_1\}$ of linear orders of size $\aleph_0$ which are all isomorphic.
- Assume $\textsf{CH}$ or $\textsf{PFA}$. There exists an increasing continuous chain $\{(I_i,{<}):i<\omega_2\}$ of linear orders of size $\aleph_1$ which are all isomorphic.
- If $\kappa$ is an infinite cardinal such that $\kappa^{<\kappa}=\kappa$, then there exists an increasing continuous chain $\{(I_i,{<}):i<\kappa^+\}$ of linear orders of size $\kappa$ which are all isomorphic.

In this section we will prove parts (1) and (2).

Note that in the notation above, we cannot have $\alpha>\kappa^+$, or else the increasing continuous property of the chain implies that $I_{\kappa^+}$ always has size $\kappa^+>\kappa$, so that $I_{\kappa^+}$ cannot be isomorphic to previous linear orders of size $\kappa$.

Main proposition part 1

Assume $\alpha<\kappa^+$. Let $\beta$ be a limit ordinal such that $\max\{\kappa,\alpha\}\le\beta<\kappa^+$. For $i<\alpha$, we can define the linear order

$$I_i=\beta\cup\{j+\tfrac{1}{2}:j< i\},$$

such that $(I_i,{<})$ is a well-order, and $\beta$ being a limit ordinal implies that $(I_i,{<})\cong(\beta,{<})$ for all $i<\alpha$. It is easy to check that $\{I_i:i<\alpha\}$ is an increasing continuous chain of linear orders of size $\kappa$ which are all isomorphic to $\beta$.

The next parts (2), (3), and (4) all concern the case $\alpha=\kappa^+$, so it is convenient to define a term for this case.

Robust linear order

We say that a linear order $(I,{<})$ of size $\kappa$ is *robust* if there exists an increasing continuous chain $\{(I_i,{<}):i<\kappa^+\}$ of linear orders which are all isomorphic to $(I,{<})$.

Do robust linear orders always exist in every infinite cardinality?

Main proposition part 2

We will show that $(\mathbb{Q},{<})$ is robust of size $\aleph_0$.

For $i<\omega_1$, we define the linear order

$$(I_i,{<})=\left((1+i)\times\mathbb{Q},{<}_{\text{lex}}\right).$$

This $I_i$ is constructed by replacing every point in the linear order $1+i$ with a copy of $\mathbb{Q}$. Then every $I_i$ is a dense linear order without endpoints of size $\aleph_0$, so by Cantor's back-and-forth method (see [1] Theorem 2.4.1), we get an isomorphism $(I_i,{<})\cong(\mathbb{Q},{<})$.

It's easy to see that $\{I_i:i<\omega_1\}$ forms an increasing continuous chain, witnessing robustness of $(\mathbb{Q},{<})$.

In this section we'll see that the Proper Forcing Axiom ($\textsf{PFA}$) implies a robust linear order of size $\aleph_1$.

Baumgartner, see [2] Corollary 8.3

A set of reals $X\subseteq\mathbb{R}$ is called *$\kappa$-dense* if for every nonempty open interval $U\subseteq\mathbb{R}$, there is $|X\cap U|=\kappa$.

Assume $\textsf{PFA}$. Every two $\aleph_1$-dense sets of reals $X$ and $Y$ are isomorphic.

Main proposition part 3, assuming PFA

Let $X$ be an $\aleph_1$-dense set of reals. We'll show that $(X,{<})$ is robust.

$\textsf{PFA}$ implies $|\mathbb{R}|=\aleph_2$ ([3] Theorem 31.23), so we can pick $\aleph_2$ many distinct reals $\{x_i\in\mathbb{R}:i<\omega_2\}$ that are not in $X$. For $i<\omega_2$, define

$$I_i=X\cup\{x_j:j< i\}.$$

Then every $I_i$ is $\aleph_1$-dense since $X\subseteq I_i$ is $\aleph_1$-dense and $|I_i|=\aleph_1$, and so Baumgartner's theorem implies $(I_i,{<})\cong (X,{<})$.

It's easy to see that $\{I_i:i<\omega_2\}$ is increasing continuous, which witnesses that $(X,{<})$ is robust of size $\aleph_1$.

I was given this argument in a Mathematics Stack Exchange answer by username Holo when I first asked about robust linear orders.

In an unpublished result , Itay Neeman has shown the consistency of “every two $\aleph_2$-dense sets of reals are isomorphic”.

In this section, we will prove part (4) of the main proposition:

Ervin

If $\kappa$ is an infinite cardinal such that $\kappa^{<\kappa}=\kappa$, then there exists a robust linear order of size $\kappa$.

The assumption that $\kappa^{<\kappa}=\kappa$ is equivalent to the assumptions that $\kappa$ is regular and $2^{<\kappa}=\kappa$.

The Continuum Hypothesis ($\textsf{CH}$) implies that $\kappa=\aleph_1$ satisfies this condition, and so part (3) of the main proposition follows. More generally, the Generalized Continuum Hypothesis ($\textsf{GCH}$) implies that every infinite cardinal $\kappa$ satisfies $2^{<\kappa}=\kappa$, which then implies there are robust linear orders of size any regular cardinal $\kappa$.

In the discussions below, we fix a regular cardinal $\kappa$ satisfying $2^{<\kappa}=\kappa$.

$(\mathcal{I},{<})$ and $\mathcal{J}$

$(2^\kappa,{<}_\text{lex})$ is the lexicographic ordering on binary strings of length $\kappa$.

Let $\mathcal{I}\subseteq2^\kappa$ be the set of all $x\in2^\kappa$ which are not eventually constant. The linear order $(\mathcal{I},{<})$ is the suborder of $(2^\kappa,{<}_\text{lex})$ induced by $\mathcal{I}$.

Define $\mathcal{J}\subseteq\mathcal{I}$ to be the set of all elements of $\mathcal{I}$ of the form $\sigma^\frown(01)^\kappa=\sigma0101\ldots$ for some $\sigma\in 2^{<\kappa}$.

Note that $|\mathcal{I}|=2^\kappa$ and $|\mathcal{J}|=2^{<\kappa}=\kappa$.

Saturation lemma part 1

Let $A,B\subseteq\mathcal{I}$ be two subsets of $\mathcal{I}$ such that $|A|<\kappa$, $|B|<\kappa$, and for all $a\in A$ and $b\in B$ there is $a< b$. Then there exists $c\in\mathcal{J}$ such that $a< c$ for all $a\in A$, and $c< b$ for all $b\in B$.

We can define a supremum $f=\sup(A)\in 2^\kappa$ recursively, such that for all $i<\kappa$, $f(i)\in 2$ is the smallest such that for all $a\in A$, there is $a\upharpoonright(i+1)\le_\text{lex}(f\upharpoonright i)^\frown f(i)$. It is not hard to show that for all $a\in A$, there is $a\le_\text{lex} f$, and for all $g<_\text{lex}f$ there exists some $a\in A$ such that $g<_\text{lex}a$.

We split into cases.

- If $f=\sup(A)\in A$, then for all $b\in B$, since $f< b$, we can pick some $\gamma_b<\kappa$ such that $f\upharpoonright\gamma_b< b\upharpoonright\gamma_b$. Then let $\gamma=\sup_{b\in B}\gamma_b$ so that $\gamma<\kappa$ by regularity, and we see that $g=(f\upharpoonright\gamma)(1)^\kappa$ satisfies $g\upharpoonright\gamma< b\upharpoonright\gamma$ for all $b\in B$.

Since $f\le g$, $f\in A\subseteq\mathcal{I}$, and $g\notin\mathcal{I}$, we have $f< g$, so that $f\upharpoonright\delta< g\upharpoonright\delta$ for some $\gamma\le\delta<\kappa$. Letting $c=(g\upharpoonright\delta)(01)^\kappa$, we have $f< c$, so that for all $a\in A$, $a\upharpoonright\delta\le f\upharpoonright\delta< c\upharpoonright \delta$, and for all $b\in B$, $c\upharpoonright\delta= g\upharpoonright\delta< b\upharpoonright\delta$. By $c\in\mathcal{J}$, we've seen that $c$ is what we wanted. - Similarly if $\inf(B)\in B$, then a desired $c\in \mathcal{J}$ exists.
- Assume $\sup(A)\notin A$ and $\inf(B)\notin B$.

First we can show that $f=\sup(A)$ is eventually constantly $0$. For every $a\in A$, fix $\gamma_a<\kappa$ such that $a\upharpoonright\gamma_a< f\upharpoonright\gamma_a$, and let $\gamma=\sup_{a\in A}\gamma_a<\kappa$ by regularity. Then $g=(f\upharpoonright\gamma)(0)^\kappa$ is such that $g\le f$, but $a< g$ for all $a\in A$. Since $f$ is a supremum, we must have $f=g$, and so $f$ is eventually constantly $0$ as claimed.

Similarly $h=\inf(B)$ is eventually constantly $1$.

From $A< B$ we know that $f\le h$. But since $f\ne h$, we have $f< h$. So we can fix some $\delta<\kappa$ such that $f\upharpoonright\delta< h\upharpoonright\delta$, $f=(f\upharpoonright\delta)(0)^\kappa$, and $h=(h\upharpoonright\delta)(1)^\kappa$. Then $c=(f\upharpoonright\delta)(01)^\kappa$ satisfies $f< c< h$ and $c\in\mathcal{J}$, so $c$ is what we wanted.

Saturation lemma part 2, see [1] Theorem 4.3.20

Define a linear order $(I,{<})$ of size $\kappa$ to be *saturated* if for every $A,B\subseteq I$ such that $|A|<\kappa$, $|B|<\kappa$, and $a< b$ for all $a\in A$ and $b\in B$, there exists $c\in I$ such that $a< c$ for all $a\in A$ and $c< b$ for all $b\in B$.

Every two saturated linear orders $(L,{<})$ and $(K,{<})$ of size $\kappa$ are isomorphic.

Let $L\sqcup K=\{x_i:i<\kappa\}$.

We can build a chain of partial isomorphisms $\{f_i:i<\kappa\}$ such that $\text{dom}(f_i)\subseteq L$ and $\text{img}(f_i)\subseteq K$ both have size $<\kappa$, $f_i$ is an isomorphism between $(\text{dom}(f_i),{<}_L)$ and $(\text{img}(f_i),{<}_K)$, and $x_i\in\text{dom}(f_{i+1})\cup\text{img}(f_{i+1})$.

- When $i=0$ let $f_0=\varnothing$.
- When $i<\kappa$ is limit, let $f_i=\bigcup_{j< i}f_j$.
- When $i+1$ is a successor stage and $x_i\in L\smallsetminus\text{dom}(f_i)$, we let $A=f_i[(-\infty,x_i)]$ and $B=f_i[(x_i,\infty)]$. By saturation of $K$, there is $c\in K$ such that $A< c< B$, and we can define $f_{i+1}=f_i\cup\{(x_i,c)\}$.
- The other cases are similar, and it's never hard to see that $f_i$ has the desired properties for all $i<\kappa$.

Finally, we get an isomorphism $f=\bigcup_{i<\kappa}f_i$ from $(L,{<})$ to $(K,{<})$.

Main proposition part 4

We'll show the linear order $(\mathcal{J},{<})$ is robust of size $\kappa$.

Since $|\mathcal{I}|=2^\kappa$, we can pick $\kappa^+$ many distinct elements $\{x_i\in\mathcal{I}:i<\kappa^+\}$ that are not in $\mathcal{J}$. For $i<\kappa^+$, define

$$I_i=\mathcal{J}\cup\{x_j:j< i\}.$$

By the saturation lemma part 1, every $I_i$ is saturated of size $\kappa$, because $\mathcal{J}\subseteq I_i$. By the saturation lemma part 2, $(I_i,{<})\cong(\mathcal{J},{<})$.

It's easy to see that $\{I_i:i<\kappa^+\}$ is increasing continuous, which shows that $(\mathcal{J},{<})$ is robust of size $\kappa$.

This argument is due to Garrett Ervin in a private conversation.

From Shelah [4] Theorem 8.4.7, there exist saturated linear orders of size $\kappa$ if and only if $\kappa^{<\kappa}=\kappa$. For a simple argument when $\kappa=\aleph_\omega$, see [1] §4.3.

[1]

David Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, Springer, 2002

[2]

Stevo Todorcevic, Partition Problems in Topology, Contemporary Mathematics, American Mathematical Society, 1989

[3]

Thomas Jech, Set Theory: The Third Millennium Edition, Revised and Expanded, Springer Monographs in Mathematics, Springer, 2002

[4]

Saharon Shelah, Classification Theory: and the Number of Non-Isomorphic Models, Studies in Logic and the Foundations of Mathematics, North-Holland, 1990

投稿日：2023年12月17日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

duyaa

6

235

中国人です。今はAlexander Kechris先生の弟子として、カリフォルニア工科大学で博士課程を受けています。

コメント

コメントはありません。

読み込み中...

読み込み中