Index sets of classes of hyper-hypersimple sets (Q1174056): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q949620 |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Victor L. Selivanov / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3320353 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Lattice of Recursively Enumerable Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hyperarithmetical Index Sets in Recursion Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819052 / rank | |||
Normal rank |
Revision as of 09:50, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Index sets of classes of hyper-hypersimple sets |
scientific article |
Statements
Index sets of classes of hyper-hypersimple sets (English)
0 references
25 June 1992
0 references
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)].
0 references
complexities of classes of hyper-hypersimple sets
0 references
index set of a predicate which is elementary in the lattice of recursively enumerable sets
0 references
arithmetic hierarchy
0 references