FOM: question about s1s and s2s
Joseph S. Miller (Grad)
jmiller at polygon.math.cornell.edu
Mon Jun 18 15:29:49 EDT 2001
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
>
More information about the FOM
mailing list