0
$\begingroup$

I am looking for (many) examples of mathematical hierarchies like the arithmetical or the polynomial hierarchy that collapse precisely at level 2 (3 is also fine, but the level should be at least 2 and yet relatively low).

Some background: The arithmetical hierarchy, for example, is a quantifier alternation depth hierarchy. The formula $$\Xi ~{}={}~ \forall x \colon \varphi \qquad \text{would be at level 1}$$ of the hierarchy, the formula $$\Phi ~{}={}~ \forall\, w ~\forall\, x ~\exists\,y ~\exists\, z\colon \phi \qquad \text{would be at level 2}$$ of the hierarchy, and the formula $$\Psi ~{}={}~ \exists\, w ~\exists\, x ~\color{orange}{\forall\,y ~\exists\, z}\colon \phi\qquad \text{would be at level 3}$$ of the hierarchy.

If I understand correctly, if the arithmetical hierarchy were to collapse at level 2 (which it in fact does not), then the formula $\Psi$ would be equivalent to the formula $ \color{orange}{\forall\,y ~\exists\, z}\colon \phi$ because the leading existential quantifiers of $\Psi$ would not add any extra complexity / information to what the formula expresses.

I am looking for examples of mathematical hierarchies that are strict (not all levels are in fact the same) but which collapse at some relatively low level $k$ (meaning that all levels above $k$ are actually the same as level $k$), where preferrably $k=2$.

$\endgroup$
2
  • $\begingroup$ This question may be of interest. $\endgroup$ Commented May 26 at 23:29
  • $\begingroup$ Yes it is, thank you! : ) $\endgroup$
    – blk
    Commented May 26 at 23:39

0

You must log in to answer this question.

Browse other questions tagged .