Implementing fragments of ZFC within an r.e. Universe. (13th September 2017)

• Record Type: Journal Article
• Authors: Martin, Eric; Stephan, Frank
• Is Part Of: Journal of logic and computation. Volume 28:Number 1(2018)
• Page Start: 1
• Page End: 32
• Publication Date: 2017-09-13
• Subjects: Recursively enumerable model -- Friedberg numbering -- axioms of Zermelo Fraenkel set theory (ZFC); Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exx030
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: The present work addresses the question: to what extent do natural models of a sufficiently rich fragment of set theory exist? Such models, here called Friedberg models, are built as a class of sets of natural numbers together with the element-relation "$x$ is in $y$ " given by $x\in A_y$, where $A_0$, $A_1$, $A_2$, $\ldots$ is a Friedberg numbering of all r.e. sets of natural numbers. A member $A_x$ of this numbering is considered to be a set in the given model iff the transitive closure of the induced membership relation starting from $x$ is well-founded. Furthermore, for all $k$, the set $B_k = \{x: A_x\mbox{ has size $k$ }\}$ must be recursive. It will be examined whether the axioms of set theory and some basic set-theoretic properties hold in such a model. Because they do not hold in full generality, comprehension and replacement need to be properly adapted. The validity of the axiom of power set depends on the Friedberg model under consideration. The other axioms hold in every Friedberg model.