Existentially Complete Nerode Semirings

✍ Scribed by Thomas G. McLaughlin

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 798 KB
• Volume: 41
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19950410102

✦ Synopsis

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.