Polynomial-time analogues of isolatedness (Q1192349)

Classical recursive equivalence types are defined as analogues of equipollence classes using only partial recursive functions: we say \(A\) is recursive equivalent to \(B\) if there is a partial recursive injective function \(f\) with \(f(A)=B\). Under this definition, Dedekind finite sets are called isolated sets. The study of these objects and the extent to which arithmetic can be lifted was the center of a lot of elegant research. \textit{A. Nerode} and \textit{J. B. Remmel} extended such studies to the situation where \(f\) is polynomial time [Lect. Notes Math. 1432, 323- 362 (1989; Zbl 0705.03024)]. This leads to various interpretations of the notion of ``Dedekind \(p\)-finite'', and in the present paper the author explores the connections between these definitions, and the extent to which cancellation laws hold.