Discrete families of recursive functions and index sets (Q1842381): Difference between revisions

Second order index sets of the discrete families of partial recursive functions (PRF) are studied. Let \(\{\varphi_e\}_{e \in \omega}\) be a Gödel numbering of the set of PRF. The \(e\)-th computable numbering is defined as follows: \(\nu^e : = \lambda i,x. \varphi_e (\langle i,x \rangle)\), and let \(\nu^e\) enumerate the family of PRF \(F^{(e)} : = \{ \lambda x. \nu^e (i,x)\}_{e \in \omega}\). Denote by \(I(F)\) the set \(\{e : F^{(e)} = F\}\), and denote by \(R_1\) the family of total recursive functions. The authors show: If \(A\) is a non-recursive recursively enumerable set then \(\{\langle i,j \rangle : W_i \cap W_j = \emptyset\;\&\;W_i \cup W_j = A \cap W_i\;\&\;W_i\) is nonrecursive\} is \(\Pi_3\)-complete. The family \(\{e : F^{(e)} \subseteq R_1\) is effectively discrete\} is \(\Sigma_3\)-complete. The family \(\{e : F^{(e)} \subseteq R_1\) is discrete\}, as well as the family \(\{e : F^{(e)} \subseteq R_1\) is discrete, but not effectively discrete\} are both \(\Pi_3\)-complete. The index set of any family \(F\) of total recursive functions which has exactly one (i.e. \(|L \{F\} |= 1)\) numbering up to numbering equivalence, is \(\Pi_4\)-complete. The article contains a series of other results closely related to the above-mentioned ones. A number of open problem are listed.