We prove the following results: every recursively enumerable set approximated by finite sets of some set M of recursively enumerable sets with index set in \(\Pi_ 2\) is an element of M, provided that the finite sets in M are canonically enumerable. If both the finite sets in M and in \(\bar M\) are canonically enumerable, then the index set of M is in \(\Sigma_ 2\cap \Pi_ 2\) if and only if M consists exactly of the sets approximated by finite sets of M and the complement \(\bar M\) consists exactly of the sets approximated by finite sets of \(\bar M.\) Under the same condition M or \(\bar M\) has a non-empty subset with recursively enumerable index set, if the index set of M is in \(\Sigma_ 2\cap \Pi_ 2\). If the finite sets in M are canonically enumerable, then the following three statements are equivalent: (i) the index set of M is in \(\Sigma_ 2\setminus \Pi_ 2\), (ii) the index set of M is \(\Sigma_ 2\)-complete, (iii) the index set of M is in \(\Sigma_ 2\) and some sequence of finite sets in M approximate a set in \(\bar M.\) Finally, for every \(n\geq 2\), an index set in \(\Sigma_ n\setminus \Pi_ n\) is presented which is not \(\Sigma_ n\)-complete.
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Index Sets and Boolean Operations
- Index Sets Universal for Differences of Arithmetic Sets
- Language identification in the limit
- On the Degrees of Index Sets
- On the size of machines
- Program size in restricted programming languages
- Rice Theorems For D.R.E. Sets
- Toward a mathematical theory of inductive inference
- Multiple m-reducibility of index sets
- Index sets in the hyperarithmetical hierarchy
- Index sets related to prompt simplicity
- Index sets of quotient objects of the Post numeration
- Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
- Index sets and presentations of complexity classes
- \(\Sigma_ 5\)-completeness of index sets arising from the recursively enumerable Turing degrees
- \(\Sigma_ 5\)-completeness of index sets arising from the lattice of recursively enumerable sets
- Precomplete numberings
- On realization of index sets in \(\Pi_1^0\)-classes
- Fine hierarchy and definable index sets
- On the index sets of -subsets of the real numbers
- Index sets and degrees of unsolvability
- scientific article; zbMATH DE number 3857079 (Why is no real title available?)
- scientific article; zbMATH DE number 3974952 (Why is no real title available?)
- The position of index sets of identifiable sets in the arithmetical hierarchy
- The index set {e: We ≡1X}.
- scientific article; zbMATH DE number 4055599 (Why is no real title available?)
- scientific article; zbMATH DE number 4057498 (Why is no real title available?)
- Hyperarithmetical Index Sets in Recursion Theory
- scientific article; zbMATH DE number 4108745 (Why is no real title available?)
- scientific article; zbMATH DE number 4125390 (Why is no real title available?)
- scientific article; zbMATH DE number 701093 (Why is no real title available?)
- scientific article; zbMATH DE number 1047533 (Why is no real title available?)
- scientific article; zbMATH DE number 6318 (Why is no real title available?)
- scientific article; zbMATH DE number 4116518 (Why is no real title available?)
- scientific article; zbMATH DE number 749926 (Why is no real title available?)
- scientific article; zbMATH DE number 5026326 (Why is no real title available?)
- Index sets and universal numberings
This page was built for publication: Index sets in the arithmetical hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106842)
