Reducibility by means of almost polynomial functions

S. S. Marchenkov

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 68-78

Résumé

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.

Détail

Keywords: $m$-reducibility, almost polynomial functions.