MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures: $${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ and the more usual word model: $${\mathbb{N}^{\rm fin}}(w) = \langle \{0, \ldots, |w|-1\}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ where $Q_{a_i} = \{p \;|\; w_p = a_i\}$.

Then WS1S is the set of second order formulas with models of the form ${\mathbb{N}}(w)$, with order, and for which second order quantification is limited to finite subsets of the domain. MSO is the set of second order formulas with models of the form ${\mathbb{N}^{\rm fin}}(w)$, with order.

The usual proof that REG = WS1S proves at the same time that MSO = WS1S. My question is then, for which first or second order relations can we keep this to be true?

For instance, if we add a unary predicate $E(X)$ which says that a (monadic) second order variable contains an even number of objects, we add no power, as $E(X)$ is expressible as "there exists $X_1$ and $X_2$ that partition $X$, in such a way that if an element is in $X_i$ the next one in $X$ is in $X_j$, $i \neq j$, and the first element of $X$ is in $X_1$ and the last is in $X_2$."

Now, if we add a predicate $|X| < |Y|$, then WS1S becomes undecidable (see Klaedtke & Ruess,, while MSO stays trivially decidable.

Thank you.

share|cite|improve this question
I've find-changed your \def ined commands for commands that jsMath understands. Unfortunately, this is not LaTeX, just some javascript that understands basic LaTeX mathematical markup. If I made an error, feel free to roll back. (I also used ^{\rm fin} rather than ^{\text{fin}} because jsMath gets the sizing wrong with the later.) – Theo Johnson-Freyd Jul 18 '10 at 0:57
Oh, sorry. Though, it worked, didn't it? :-) I'll have a closer look to jsMath to know what are the do-s and don't-s. Thanks. – Michaël Jul 19 '10 at 0:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.