Interpreting monadic theory of reals in the monadic theory of linear order.

Question

Below is an extract from Gurevich, Shelah - Interpreting Second Order Logic in the Monadic Theory of Order. I am trying to understand how the monadic theory of the real line is interpretable in the monadic theory of order (they do not include any further explanation or proof, only saying that it can be done easily).

Here are some definitions which might be useful. If $(\alpha,<)$ is a linear order then by 'the monadic theory of $\alpha$' is meant the first order theory of the structure $(\mathcal{P}(\alpha),\subseteq,<)$ where $<$ is the ordering of $\alpha$ given on singleton subsets. The 'monadic theory of order' is the intersection of all of these first order theories as we allow $\alpha$ to vary over all linear orders.

Is there perhaps some recursive set of axioms $T_{\mathbb{R}}$ such that if we take the union of the monadic theory of order with $T_{\mathbb{R}}$ we get the complete theory of the structure $(\mathcal{P}(\mathbb{R}),\subseteq,<)$? (Worth noting, both the monadic theory of order and the monadic theory of $\mathbb{R}$ are undecidable).

I cannot find this 'easy' interpretation but feel I might be missing something obvious.

Answer 1

I don't see how to fix my original strategy - in particular, although I don't have a counterexample I suspect that "is a Dedekind-complete linear order without endpoints or isolated points, all of whose suborders have cofinality and coinitiality $\le \omega$" does not necessarily pin down $\mathbb{R}$ up to isomorphism.

However, we can still get the expected reduction (although at a glance this doesn't yield an interpretation per se - still thinking about that). Say that a linear order $A$ is $\mathbb{R}$ish if it is Dedekind-complete and has no endpoints or isolated points. The key observation is the following:

(Lemma) Every $\mathbb{R}$ish order has a suborder isomorphic to $\mathbb{R}$, and every $\mathbb{R}$ish suborder of $\mathbb{R}$ is isomorphic to $\mathbb{R}$.

The point then is that $\mathbb{R}$ sits at the bottom of an MSO-definable class of orderings in an MSO-definable sense. So we can perform the following translation:

(Definition) For an MSO sentence $\varphi$, let $\hat{\varphi}$ be the MSO sentence "Every $\mathbb{R}$ish order has an $\mathbb{R}$ish suborder satisfying $\varphi$."

By the lemma we have that $\hat{\varphi}$ is part of the MSO-theory of order iff $\mathbb{R}\models\varphi$:

• If $\mathbb{R}\not\models\varphi$ then $\mathbb{R}\not\models\hat{\varphi}$, since all $\mathbb{R}$ish suborders of $\mathbb{R}$ are isomorphic to $\mathbb{R}$ per the lemma and hence also don't satisfy $\varphi$.

• Conversely, if $\mathbb{R}\models\varphi$ then every $\mathbb{R}$ish linear order has a $\mathbb{R}$ish suborder satisfying $\varphi$ - namely, any suborder isomorphic to $\mathbb{R}$ itself, which is guaranteed to exist per the lemma.

The map $\varphi\mapsto\hat{\varphi}$ is clearly computable, and so we get a reduction of $Th_{MSO}(\mathbb{R})$ to the monadic theory of order as desired.