FOM: question about s1s and s2s

[Joseph S. Miller (Grad)]

On Fri, 15 Jun 2001, Alexander Rabinovich wrote:

[text deleted]

> Here are some other related results:
> 
> The monadic second order theory (MLO)  of reals
> is decidable when you restrict quantification
> to F_\sigma sets (Rabin).
> However, MLO  is undecidable when quantification is over
> arbitrary subsets of reals (Shelah).
> 
> Maybe Shelah also proved that MLO over the reals
>  is still decidable
> for quantification over Borel sets (or up to some level of Borel
> hierarchy).
> 

This was conjectured by Rabin.  In [2], Shelah made the stronger
conjecture that S2S with quantification over Borel sets of paths is
decidable.  As far as I know, no progress has been made on either.  In a
1985 survey of monadic second-order theories [3], Gurevich mentions only
one open question -- Shelah's conjecture.

I would be interested in anything that is known about these problems.

[3] Y. Gurevich (1985).
Monadic second-order theories. Model-theoretic logics,
479--506, Perspect. Math. Logic, Springer, New York. 

Joseph Miller
jmiller at math.cornell.edu

> 
> [1] M. O. Rabin (1969).
>  Decidability of second order theories and automata on
>   infinite trees.  In  Trans. Amer. Math. Soc., 141,pp 1-35.
> [2]  S. Shelah (1975).
> The monadic theory of order.  Annals of Mathematics 102:379--419.
> 
> 
> Alexander Rabinovich
> Dept. of  Computer Science
> Tel Aviv University
> rabino at math.tau.ac.il
>