Existentially Complete Nerode Semirings
Thomas G. McLaughlin · Mathematical logic quarterly · 1995
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”. (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.