Immunity and hyperimmunity for sets of minimal indices (Q929628): Difference between revisions

Given an equivalence relation \(\equiv\) on c.e. sets of natural numbers, one may define a corresponding set of minimal indices \(\{\,e\mid j<e\Rightarrow W_j\not\equiv W_e\,\}\). The authors investigate these sets for various choices of~\(\equiv\) (such as \(=\), \(=^*\), \(\equiv_T\), \(\equiv_m\), and~\(\equiv_1\)), examining the possible complexity in the arithmetical hierarchy of their subsets. A typical result here is that for~\(\equiv_T\), the minimal index set contains no infinite \(\Sigma_3\) subset, but it does contain an infinite \(\Sigma_4\) subset. In contrast, whether or not the minimal index set for \(\equiv_T\) contains an infinite \(\Pi_3\) subset depends on the choice of Gödel numbering for the c.e. sets.