Feasibly Categorical Abelian Groups
Douglas Cenzer, Jeffrey B. Remmel · Birkhäuser Boston eBooks · 1995
In some recent work by Grigorieff [7], Remmel [14, 15], and Cenzer and Remmel [1, 2, 3, 4], a systematic study of polynomial time models and their relation to recursive models has been undertaken. Here we say that a structure $$\mathcal{A} = (A,{{\{ R_{i}^{\mathcal{A}}\} }_{{i \in S}}},{{\{ f_{i}^{\mathcal{A}}\} }_{{i \in T}}},{{\{ c_{i}^{\mathcal{A}}\} }_{{i \in U}}}),$$ (where the universe A of A is a subset of {0,1}*) is recursive if A is a recursive subset of {0,1}*, S is an initial segment of the natural numbers ω = {0,1,…} and there is a recursive function s: S → ω such that each relation R is an s(i)-ary recursive relation over A, and T is an initial segment of ω and there is a recursive function t: T → ω such each function f is a partial recursive function which maps A t(i) into A. Similarly we say that a recursive structure $$A = \left( {A,\left\{ {R_i^A} \right\}i\varepsilon S,\left\{ {f_i^A} \right\}i\varepsilon T,\left\{ {c_i^A} \right\}i\varepsilon U} \right),$$ , is polynomial time if A is a polynomial time subset of {0,1}*, each relation is polynomial time, and each function is the restriction of a polynomial time function to A t(i) . For example, Grigorieff [7] studied recursive and polynomial time linear orderings. He showed that every recursive linear ordering is recursively isomorphic to some polynomial time linear ordering and that every recursive linear ordering is isomorphic to a polynomial time linear ordering (in fact, a real time linear ordering) whose universe is the binary representation of the natural numbers, Bin(ω).