scientific article; zbMATH DE number 4051591

From MaRDI portal
Publication:3787992





Let \(L_ 2\) be the monadic second order language for two successors arithmetic, and let \(L_{\omega 2}\) be the set of weak formulas of \(L_ 2\), i.e., formulas containing quantifiers only for individual and finite set variables. A formula of \(L_ 2\) represents a set of infinite binary trees whose nodes are labelled by symbols \(\ell\), r for two successor functions. A distance between any two trees is defined so that the obtained metric space of trees is compact. Let \(N_ 0\) denote the set of \(L_ 2\)-formulas representing closed sets of trees, and then define the sets \(N_ k\) as follows: \[ \phi \in N_{2k+1}\text{ iff } \phi \equiv \exists \alpha_ 1\exists \alpha_ 2...\exists \alpha_ n \psi \text{ where } \psi \in N_{2k}, \] \[ \phi \in N_{2k+2}\quad iff\quad \phi \equiv \forall \alpha_ 1\forall \alpha_ 2...\forall \alpha_ n \psi \text{ where } \psi \in N_{2k+1}. \] Here \(\alpha_ 1,\alpha_ 2,...,\alpha_ n\) are finite set variables. In the paper it is proved that the sets \(N_ k\) form an infinite hierarchy, more precisely, \(N_ i\subsetneqq N_{i+1}\) for \(i=0,1,2,... \). Furthermore, a characterization of representable closed sets as well as a characterization of representable open sets of trees is given in automata terms.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787992)