Abstract

Let Λ denote the semiring of isols. We characterize existential completeness for Nerode subsemirings of Λ, by means of a purely isol-theoretic “Σ1 separation property”. 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 . In addition, we strengthen the negative part of [13] by showing that existential completeness is not secured, for a given Nerode semiring, by either a certain “functional closure” property for the extensions of partial recursive functions or the property of “pulling in” some portion of each partial recursive fiber; these latter results are perhaps a little surprising