Existentially Complete Nerode Semirings

Let Λ denote the semiring of isols. We characterize existential completeness for Nerode subsemirings of Λ, by means of a purely isol‐theoretic “Σ 1 separation property”. (A “concrete” characterization that is not Λ‐theoretic is well known: the existentially complete Nerode semirings are the ones that are isomorphic to Σ 1 ultrapowers.) Our characterization is purely isol‐theoretic in that it is formulated entirely in terms of the extensions to Λ of the Σ 1 subsets of the natural numbers. Advantage is taken of a special kind of isol first conjectured to exist by Ellentuck and first proven to exist by Barback (unpublished). In addition, we strengthen the negative part of [13] by showing that existential completeness is not secured, for a given Nerode semiring, by either (i) a certain “functional closure” property for the extensions of partial recursive functions or (ii) the property of “pulling in” some portion of each partial recursive fiber; these latter results are perhaps a little surprising.