Rogers semilattices

Let $S$ be a countable set. A numbering of $S$ is a surjective map $\nu$ from the set of natural numbers $\omega$ onto $S$. A standard tool for comparing the complexity of different numberings is provided by the notion of reducibility between numberings: a numbering $\nu$ is reducible to another numbering $\mu$ if there is total computable function $f(x)$ such that $\nu(x) = \mu(f(x))$ for all $x\in\omega$. Numberings which are reducible to each other are called equivalent numberings.
Goncharov and Sorbi [1] started developing the theory of generalized computable numberings. One of their approaches to generalized computations can be summarized as follows. Let $\Gamma$ be a complexity class (e.g., $\Sigma^0_1$, $\Sigma^{-1}_2$, $\Sigma^0_n$, or $\Pi^1_n$). Consider a countable family $\mathcal{S} \subset P(\omega)$. A numbering $\nu$ of the family $\mathcal{S}$ is $\Gamma$-computable if the set $G_{\nu}=\{ \langle n,x\rangle \,\colon x\in \nu(n)\}$ belongs to the class $\Gamma$. We say that a family $\mathcal{S}$ is $\Gamma$-computable if it has a $\Gamma$-computable numbering. Rogers semilattice of a family is a quotient structure of all computable numberings of the family, modulo equivalence of the numberings, ordered by the relation induced by the reducibility of numberings.
In a way similar to the classical studies of computable numberings [2], one introduces the notion of the Rogers semilattice of a $\Gamma$-computable family $\mathcal{S}$. We say that an upper semilattice $\mathcal{U}$ is a Rogers $\Gamma$-semilattice if there is a $\Gamma$-computable family $\mathcal{S}$ such that the Rogers semilattice of $\mathcal{S}$ is isomorphic to $\mathcal{U}$.
In this talk we eill discuss some recent results on Rogers semilattices for different complexity classes.
The talk is based on joint works with Nikolay Bazhenov, Birzhan Kalmurzaev, Manat Mustafa and Mars Yamaleev.

Список литературы

1. S. S. Goncharov, A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices”, Algebra and Logic, 36:6 (1997), 359–369
2. Yu. L. Ershov, Theory of numberings, Nauka, Moscow, 1977 (Russian)