Index sets in the arithmetical hierarchy (Q1106842): Difference between revisions

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.