11
$\begingroup$

The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true first-order arithmetic is Turing-reducible to the monadic theory of the real line. (Shelah first showed it in the 1970's, but his original result assumed the continuum hypothesis.) But my question is, what is the Turing degree of the monadic theory of the real line?

Clearly the monadic theory of the real line is Turing reducible to true third-order arithmetic, but how does it compare to true second-order arithmetic, for instance?

$\endgroup$
1
  • $\begingroup$ Note the comment by @ErikWalsberg that "I don't think there has been any work on the monadic second order theory of the reals for a long time, people were probably scared off by the difficulty of the work of Shelah and Guervich", and his reference to open questions on these topics. (mathoverflow.net/questions/322883/…) There seem to be no surveys in the area from after 1985 (mathoverflow.net/questions/332867/…) $\endgroup$
    – user44143
    Commented Mar 7, 2021 at 1:55

1 Answer 1

7
+100
$\begingroup$

Gurevich and Shelah showed in The monadic theory and the “next world” that the monadic theory of the real line (or even just the Cantor Discontinuum) can compute
- the $V^B$ theory of second order arithmetic,
- the $V^B$ theory of third order arithmetic if CH holds (or if the union of $<\!c$ meager sets is meager),
where $B$ is the Boolean algebra of regular open sets, equivalently the algebra for adding a Cohen real.

Note the sharp contrast with the decidability of S2S.

Also, despite its power, the monadic theory of the real line does not interpret (allowing parameters) even Robinson arithmetic $\mathrm{Q}$ (On the strength of the interpretation method by Gurevich and Shelah; the theory there is mutually interpretable with $\mathrm{Q}$, $\mathrm{I}Σ_0$, and other typical weak arithmetical theories without exponentiation). See also Peano Arithmetic may not be interpretable in the monadic theory of orders by Lifsches and Shelah. The reason is that we have certain symmetries that break any purported interpretation.

However, the Cohen algebra $B$ is interpretable in the monadic theory of the reals, and with some effort, the theory can be used to reason about $B$-valued models, hence the unusual form of the complexity result.

I suspect the qualification $V^B$ can be removed in the 'true' $V$, but I only know the trivial (given known absoluteness results) consequences:
- under $V=L$, the theory of third order arithmetic is computable from the theory,
- under projective determinacy, the theory of second order arithmetic is computable from the theory,
- under a measurable Woodin cardinal + CH, $Σ^2_1$ truth is computable from the theory,
- there is a generic extension of $V$ (such as $\mathrm{Add}(ω_1,1) \times \mathrm{Add}(ω,1)$) in which the theory of third order arithmetic is computable from the theory (both as defined in the extension).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .