Precomplete Arithmetical Equivalences
Asel Altaeva (aselaa@mail.ru)
Kazakh National University (Kazakhstan)
We study arithmetical equivalence relations and
investigate a possibility to modify main results on positive
equivalences concerning reducibility and completeness for the
relations in the arithmetical hierarchy considering
S0n+1 -equivalence relations generated by
0n -computable functions.
Particularly, such approach allows us to show that precomplete
arithmetical equivalences are computably isomorphic to each other.
We consider also various notions of completeness for the
arithmetical equivalence relations (e-completeness by Lachlan,
completeness by Ershov).