Fixed-point Selection Functions
M. M. Arslanov · Lobachevskii Journal of Mathematics · 2021
Let $$\simeq$$ be a binary relation between sets of integers, and $$\leq_{R}$$ be a Post reducibility, i.e. a reflexive and transitive relation between sets of integers such that if $$A\leq_{R}B$$ then the computational complexity of recognition of elements of $$A$$ is easier than (or equal to) the recognition of elements of $$B$$ . Suppose that for a class $${\mathcal{A}}$$ of arithmetical sets, which have an effective enumeration $$\{\Omega_{e}\}_{e\in\omega}$$ , there are $$R$$ -complete sets, i.e. such sets $$D$$ that for any $$A\in{\mathcal{A}}$$ , $$A\leq_{R}D$$ . Earlier we considered completeness criteria for such reducibilities roughly of the following type: For any $$A\in{\mathcal{A}}$$ , $$A$$ is $$R$$ -complete if and only if there is a function $$f$$ , defined on $$\omega$$ such that $$f\leq_{R}D$$ and $$\Omega_{f(i)} ot\simeq\Omega_{i}$$ for all $$i\in\omega$$ . This means that for any set $$A\in{\mathcal{A}}$$ , if it is non-complete, then any function $$f\leq_{R}A$$ has a fixed-point $$e$$ : $$\Omega_{f(e)}\simeq\Omega_{e}$$ . In this paper we introduce a notion of fixed-point selection function for sequences of such sets and study their complexity characteristics.