Reducibility by means of almost polynomial functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 68-78
Voir la notice de l'article provenant de la source Math-Net.Ru
The aim of the work is to introduce a variant of $m$-reducibility using almost polynomial functions and to study the resulting partially ordered set $\mathcal M_{\mathbb P}$ of the corresponding degrees of undecidability. It is proved that the set $\mathcal M_{\mathbb P}$ has at least a countable number of minimal elements, but has no maximal elements. The set $\mathcal M_{\mathbb P}$ is neither an upper nor a lower semilattice. Each element of the set $\mathcal M_{\mathbb P}$, other than the smallest, can be included in a continuum antichain. We construct a continuum family of pairwise isomorphic initial segments of the set $\mathcal M_{\mathbb P}$, having a countable width and height and intersecting only by the smallest element of the set.
Keywords:
$m$-reducibility, almost polynomial functions.
@article{IVM_2022_12_a4,
author = {S. S. Marchenkov},
title = {Reducibility by means of almost polynomial functions},
journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
pages = {68--78},
publisher = {mathdoc},
number = {12},
year = {2022},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/}
}
S. S. Marchenkov. Reducibility by means of almost polynomial functions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 68-78. http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/