<p>No, for the same reason as in the linked question: an SO sentence over a given class of structures can be translated to an MSO sentence over structures augmented with their Cartesian powers, which can in turn be translated to an MSO sentence over graphs due to the universality of graphs. Thus, if MSO on graphs collapses to <span class="math-container">$\Sigma^1_k$</span>, then the polynomial hierarchy collapses to <span class="math-container">$\mathrm{PH}=\Sigma^\mathrm P_k$</span>.</p>
<p>More precisely, let <span class="math-container">$\Phi$</span> be an SO sentence in a finite signature <span class="math-container">$L$</span>, quantifying over <span class="math-container">$l$</span>-ary relations. Assume for simplicity that <span class="math-container">$L$</span> is relational. Let <span class="math-container">$L'=L\cup\{P(x_1,\dots,x_l,y)\}$</span>, and for any <span class="math-container">$L$</span>-structure <span class="math-container">$\mathcal A=(A,\dots)$</span>, let <span class="math-container">$f(\mathcal A)$</span> be the <span class="math-container">$L'$</span>-structure with domain <span class="math-container">$A\mathbin{\dot\cup}A^l$</span> that carries the original <span class="math-container">$L$</span>-structure on <span class="math-container">$A$</span>, and where <span class="math-container">$P$</span> is interpreted as the graph of the partial function that maps an <span class="math-container">$l$</span>-tuple of elements of <span class="math-container">$A$</span> to the corresponding element of <span class="math-container">$A^l$</span>. Notice that <span class="math-container">$f$</span> is polynomial-time computable. Then there is an MSO sentence <span class="math-container">$\Phi'$</span> such that
<span class="math-container">$$\mathcal A\models\Phi\iff f(\mathcal A)\models\Phi'$$</span>
for every <span class="math-container">$L$</span>-structure <span class="math-container">$\mathcal A$</span>.</p>
<p>Moreover, there is a polynomial-time function <span class="math-container">$g$</span> mapping <span class="math-container">$L'$</span>-structures to graphs, and a <span class="math-container">$1$</span>-dimensional FO interpretation <span class="math-container">$I$</span> such that for any <span class="math-container">$L'$</span>-structure <span class="math-container">$\mathcal A'$</span>, <span class="math-container">$I$</span> interprets <span class="math-container">$\mathcal A'$</span> in <span class="math-container">$g(\mathcal A')$</span>. (There are many ways how to do that; see e.g. <a href="https://doi.org/10.1215/ijm/1256054991" rel="nofollow noreferrer">Hedrlín &amp; Pultr</a> and <a href="https://doi.org/10.1016/0022-0000(79)90043-6" rel="nofollow noreferrer">Miller</a> for variants of this construction in various contexts.) Then <span class="math-container">$\Phi'^I$</span> is an MSO sentence on graphs (more precisely, <span class="math-container">$\mathrm{MSO}_1$</span>, i.e., quantifying over sets of vertices) such that
<span class="math-container">$$\mathcal A\models\Phi\iff g(f(\mathcal A))\models\Phi'^I.$$</span>
If <span class="math-container">$\Phi'^I$</span> is equivalent to an <span class="math-container">$\Sigma^1_k$</span> sentence (not necessarily MSO), then the right-hand side can be evaluated in <span class="math-container">$\Sigma^\mathrm P_k$</span>.</p>
<p>Since every PH language can be expressed by an SO sentence over finite structures in a suitable signature, we obtain <span class="math-container">$\mathrm{PH}=\Sigma^\mathrm P_k$</span> if such a collapse holds for all MSO sentences over graphs.</p>

CC BY-SA 4.0
2023-07-11T08:13:18.537Z
2023-07-11T08:46:43.143Z
2023-07-11T08:46:43.143Z
Emil Jeřábek
<p>Is there some <span class="math-container">$k$</span> such that, given any formula <span class="math-container">$\varphi$</span> in the monadic second order theory of graphs (this question applies for either MSO with sets of vertices and edges or just MSO with sets of edges), there is an equivalent formula <span class="math-container">$\psi$</span> with quantifier-alternation <span class="math-container">$k$</span>?</p>
<p>(Here I think it makes sense to count both alternation in first-order and second-order quantifiers)</p>
<p>This question is inspired by <a href="https://cstheory.stackexchange.com/q/53035/68281">Are MSO formulae expressible as existential SO formulae over arbitrary structures?</a>. Finite state automata act as a kind of canonical form for formulas in WS1S (the weak monadic second order theory of one successor). So one wonders if there's possibly some other kind of canonical form for one of the monadic second order theories of graphs.</p>

<lo.logic><model-theory>
Are MSO formulae on graphs expressible with bounded quantifier alternation?
TomKern
# Are MSO formulae on graphs expressible with bounded quantifier alternation?

(Asked by: username_0 on 2023-07-11)

Is there some $k$ such that, given any formula $\varphi$ in the monadic second order theory of graphs (this question applies for either MSO with sets of vertices and edges or just MSO with sets of edges), there is an equivalent formula $\psi$ with quantifier-alternation $k$?

(Here I think it makes sense to count both alternation in first-order and second-order quantifiers)

This question is inspired by [Are MSO formulae expressible as existential SO formulae over arbitrary structures?](https://cstheory.stackexchange.com/q/53035/68281). Finite state automata act as a kind of canonical form for formulas in WS1S (the weak monadic second order theory of one successor). So one wonders if there's possibly some other kind of canonical form for one of the monadic second order theories of graphs.

**Tags:** lo.logic, model-theory


---

## 1 answers

### Answer by username_1 on 2023-07-11. Score: 3

No, for the same reason as in the linked question: an SO sentence over a given class of structures can be translated to an MSO sentence over structures augmented with their Cartesian powers, which can in turn be translated to an MSO sentence over graphs due to the universality of graphs. Thus, if MSO on graphs collapses to $\Sigma^1\_k$, then the polynomial hierarchy collapses to $\mathrm{PH}=\Sigma^\mathrm P\_k$.

More precisely, let $\Phi$ be an SO sentence in a finite signature $L$, quantifying over $l$-ary relations. Assume for simplicity that $L$ is relational. Let $L'=L\cup\{P(x\_1,\dots,x\_l,y)\}$, and for any $L$-structure $\mathcal A=(A,\dots)$, let $f(\mathcal A)$ be the $L'$-structure with domain $A\mathbin{\dot\cup}A^l$ that carries the original $L$-structure on $A$, and where $P$ is interpreted as the graph of the partial function that maps an $l$-tuple of elements of $A$ to the corresponding element of $A^l$. Notice that $f$ is polynomial-time computable. Then there is an MSO sentence $\Phi'$ such that
$$\mathcal A\models\Phi\iff f(\mathcal A)\models\Phi'$$
for every $L$-structure $\mathcal A$.

Moreover, there is a polynomial-time function $g$ mapping $L'$-structures to graphs, and a $1$-dimensional FO interpretation $I$ such that for any $L'$-structure $\mathcal A'$, $I$ interprets $\mathcal A'$ in $g(\mathcal A')$. (There are many ways how to do that; see e.g. [Hedrlín & Pultr](https://doi.org/10.1215/ijm/1256054991) and [Miller](https://doi.org/10.1016/0022-0000(79)90043-6) for variants of this construction in various contexts.) Then $\Phi'^I$ is an MSO sentence on graphs (more precisely, $\mathrm{MSO}\_1$, i.e., quantifying over sets of vertices) such that
$$\mathcal A\models\Phi\iff g(f(\mathcal A))\models\Phi'^I.$$
If $\Phi'^I$ is equivalent to an $\Sigma^1\_k$ sentence (not necessarily MSO), then the right-hand side can be evaluated in $\Sigma^\mathrm P\_k$.

Since every PH language can be expressed by an SO sentence over finite structures in a suitable signature, we obtain $\mathrm{PH}=\Sigma^\mathrm P\_k$ if such a collapse holds for all MSO sentences over graphs.


---

