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

Gurevich, Shelah - Interpreting Second Order Logic in the Monadic Theory of Order

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.


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.

  • $\begingroup$ Another way to pin down (say) $\omega$ is as a suborder of $\mathbb{R}$ with a first point, no last point, and which remains discrete after adding any additional point in $\mathbb{R}$. This is what I originally did in my answer, but it's worse. $\endgroup$ Aug 17 '20 at 1:39
  • $\begingroup$ This is incredibly helpful, and a very elegant way to see things, thank you. Just to check, we can see that $\mathbb{R}$ is the unique order satisfying these assumptions, by using these assumptions to produce a dense subset which forms a countable dense order without endpoints. But for this my approach was first to use the existence of an unbounded subset with order type $\omega^* + \omega$ (i.e. $\mathbb{Z}$). Is the existence of this actually implied by the assumptions (it can easily be added, by interchanging the descriptions of $U$ and $L$ you gave for example). $\endgroup$
    – Buchi Fan
    Aug 17 '20 at 10:12
  • 1
    $\begingroup$ Actually @NoahSchweber I can see that I have done something wrong. I had mistakenly convinced myself that I could show that any linear order satisfying the conditions must be separable, but I was being stupid and confusing being a dense subset of the order with being a subset which 'internally' is densely ordered. I understand everything except for the uniqueness of a first countable Dedekind-complete linear order with no endpoints or isolated points, do you have any hints? My mind is tunnelling in on trying to show separability follows but this doesn't seem to go anywhere. $\endgroup$
    – Buchi Fan
    Aug 17 '20 at 19:37
  • 1
    $\begingroup$ @BuchiFan What I wrote was wrong - consider the long line. I believe this is fixable (specifically I think "Every suborder has a cofinal $\omega$-sequence and a coinitial $\omega^*$-sequence" does the job) but it's a more complicated argument and I'm not certain. I've edited to reflect this, and I think (for now at least) you should unaccept this answer. $\endgroup$ Aug 17 '20 at 19:52
  • $\begingroup$ @BuchiFan I've found a different argument. $\endgroup$ Aug 17 '20 at 20:32

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.