The algebraic structure of Quasi-degrees

Batyrshin I.I.
Department of mathematics, Kazan State University, 
-e-mail: ilnurb@yandex.ru

Tennenbaum (see [1]) introduced the notion of quasi-reducibility for sets: $A\leq_Q B$ if there is a computable
function $f$ such that $x\in A\Leftrightarrow W_{f(x)}\subseteq B$. $Q$-reducibility is a natural generalization
of many-one reducibility (m-reducibility) and is closely connected with enumeration reducibility. Besides, on
c.e. sets $Q$-reducibility implies $T$-reducibility: if a c.e. set $W\leq_QA$ then $W\leq_TA$.

Quasi-reducibility plays [2] the main part in the Marchenkov's solution to the Post's problem in his spirit. He
showed that no $\eta-$hyperhypersimple set is $Q$-complete and since $Q$-reducibility coincides with
$T$-reducibility on semirecursive c.e. sets, each semirecursive noncomputable $\eta$-hyperhypersimple set is a
solution to the Post's problem.

It also turned out that quasi-reducibility is closely connected to the word problems of groups: Dobritsa proved
that for every set of natural numbers $X$ there is a word problem with the same Quasi-degree as that of $X$, and
Belegradek [3] showed that for any computably presented groups $G$ and $H$, if $G$ is a subgroup of every
algebraically closed group of which $H$ is a subgroup, then $G$'s word problem must be quasi-reducible to that
of $H$.

The study of the algebraic structure of Quasi-degrees of c.e. sets was started by the paper of Downey, LaForte
and Nies [4], who established the density of the c.e. $Q$-degrees. Arslanov and Omanadze [5] started the study
of the algebraic structure of Quasi-degrees of $n$-c.e. sets. In my report I will present some new results in
this direction.

[1] H. Jr. Rogers. Theory of Recursive Functions and Effective Computability, New York,
McGraw-Hill, 1967.

[2] S. S. Marchenkov. A class of incomplete sets. Mat. Zametki \textbf{20}, 473-478 (1976); Math. Notes
\textbf{20}, 823-825 (1976, English translation).

[3] O. Belegradek. On algebraically closed groups, Algebra i Logika, \textbf{13}, No.3 (1974), 813-816.

[4] R. R. Downey, G. G. LaForte and A. Nies. Computably enumerable sets and Quasi-reducibility, Ann. of Pure and
Applied Logic \textbf{95} (1998), 1-35.

[5] M. M. Arslanov, R. Sh. Omanadze. $Q$-degrees of $n$-c.e. sets, to appear.