To what extent MSO = WS1S, when adding relations? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T01:21:44Z http://mathoverflow.net/feeds/question/32329 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32329/to-what-extent-mso-ws1s-when-adding-relations To what extent MSO = WS1S, when adding relations? Michaël 2010-07-18T00:02:04Z 2010-07-18T00:55:01Z <p>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}}, &lt;, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ and the more usual <i>word model</i>: $${\mathbb{N}^{\rm fin}}(w) = \langle \{0, \ldots, |w|-1\}, &lt;, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ where $Q_{a_i} = \{p \;|\; w_p = a_i\}$.</p> <p>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.</p> <p>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?</p> <p>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$."</p> <p>Now, if we add a predicate $|X| &lt; |Y|$, then WS1S becomes undecidable (see Klaedtke &amp; Ruess, 10.1.1.7.3029), while MSO stays trivially decidable.</p> <p>Thank you.</p>