Premium
Existentially Complete Nerode Semirings
Author(s) -
McLaughlin Thomas G.
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410102
Subject(s) - semiring , mathematics , property (philosophy) , characterization (materials science) , closure (psychology) , completeness (order theory) , natural number , partial function , kleene algebra , partially ordered set , discrete mathematics , pure mathematics , algebra over a field , mathematical analysis , philosophy , materials science , epistemology , economics , market economy , nanotechnology
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.