Positive enumerable functors

We just submitted a new article titled “Positive enumerable functors” and you can find the preprint here or on arxiv. This article is joint work with Barbara Csima and Daniel Yu who proved most of the results presented there in an undergraduate research project he did with Barbara and me over the summer.

We investigate different effectivizations of functors using Turing operators and enumeration operators and compare these notions. The most promising of these notions are positive enumerable functors. A positive enumerable functors from \(\mathcal A\) to \(\mathcal B\) consists of two enumeration operators \(\Psi\) and \(\Psi_*\) such that when given an enumeration of the positive diagram \(P(\hat{\mathcal A})\) of a structure isomorphic to \(\hat{\mathcal A}\cong \mathcal A\), \(\Phi\) enumerates the positive diagram of \(F(\hat{\mathcal A})\). The operator \(\Phi_*\) will take care of the isomorphisms by enumerating the graph of \(F(f:\hat{\mathcal A}\to\tilde{\mathcal A})\) given \(P(\hat{\mathcal A})\oplus Graph(f)\oplus P(\tilde{\mathcal A})\).

We show that if \(\mathcal A\) is positive enumerable bi-transformable to \(\mathcal B\) (if there are positve enumerable functors \(F:\mathcal A\to\mathcal B\) and \(G:\mathcal B\to \mathcal A\) such that \(F\) and \(G\) are “enumerable pseudo-inverses”) then \(\mathcal A\) and \(\mathcal B\) have the same enumeration degree spectrum and that positive enumerable functors are independent from the already established enumerable and computable functors.

We submitted the article to a conference and hope to expand it in the future, adding more preservation results and investigating syntactic equivalences.