Reducibility by Means of Almost Polynomial Functions
Sergey Seraphimovich Marchenkov · Russian Mathematics · 2022
A variant of m-reducibility is introduced using almost polynomial functions, and the resulting partially ordered set $${{\mathcal{M}}_{\mathbb{P}}}$$ of the corresponding degrees of undecidability is analyzed. It is proved that the set $${{\mathcal{M}}_{\mathbb{P}}}$$ has at least a countable number of minimal elements but no maximal elements. $${{\mathcal{M}}_{\mathbb{P}}}$$ is neither an upper nor a lower semilattice. Each element of $${{\mathcal{M}}_{\mathbb{P}}}$$ , other than the smallest one, can be included in a continuum antichain. We construct a continuum family of pairwise isomorphic initial segments of $${{\mathcal{M}}_{\mathbb{P}}}$$ , having a countable width and height and intersecting only by the smallest element of the set.