Index sets of classes of hyper-hypersimple sets (Q1174056): Difference between revisions

In Algebra Logika 22, No. 6, 666-692 (1983; Zbl 0536.03025), we cite a hypothesis stating that the index set of a predicate which is elementary in the lattice of recursively enumerable sets (r.e.s.) \(({\mathcal E};\subseteq)\) is universal on some finite level of hierarchies defined in the quoted paper. In ``Hierarchies and index sets'' [8th Int. Congr. Logic, Methodol. Philos. Sci., Moskva 1, 167-169 (1987)], we prove this hypothesis for a class of predicates defined by \textit{A. H. Lachlan} [Trans. Am. Math. Soc. 130, 1-37 (1968; Zbl 0281.02042)]. In this article we calculate complexities of many natural classes of hyper-hypersimple sets. The main results are Theorems 5 and 6, which study classes elementary in \(({\mathcal E};\subseteq)\). They verify the stated hypothesis for a new class of predicates. These results also provide new examples of elementary subclasses \({\mathcal E}\) whose index sets are universal on every level of an arithmetic hierarchy. Therefore, an elementary theory \(\text{Th}({\mathcal E})\) does not have quantifier eliminability, i.e., for every \(n\) there exists a formula in the language \(\{\subseteq\}\) with one free variable which is not equivalent in \(\text{Th}({\mathcal E})\) to any \(\Sigma_ n\)-formula. In Theorem 1-4 we study other classes of r.e.s., all of which are \(L_{\omega_ 1\omega}\)-definable in \(({\mathcal E};\subseteq)\). We use ideas and results developed by \textit{S. Lempp} [Trans. Am. Math. Soc. 303, 559-583 (1987; Zbl 0652.03030)].