Browsing by Author "PONG, Wai Yan"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Implementing Fragments of ZFC within an r.e. Universe
    (2009-06-30) MARTIN, Eric; PONG, Wai Yan; STEPHAN, Frank
    Rabin showed that there is no r.e. model of the axioms of Zermelo and Fraenkel of set theory. In the present work, it is investigated to which extent natural models of a sufficiently rich fragment of set theory exist. Such models, called Friedberg models in the present work, are built as a class of subsets of the natural numbers, together with the element-relation given as x is in y if and only if x is in the set y-th r.e. set from a given Friedberg numbering of all r.e. sets of natural numbers. The y-th member of this numbering is then considered to be a set in the given model iff the downward closure of the induced element-ordering from y is well-founded. For each axiom and basic property of set theory, it is shown whether or not that axiom or property holds in such a model. Comprehension and replacement need to be properly adapted, as not all functions and objects definable using first-order logic exist in the model. The validity of the power set axiom, in an adequate formulation, depends on the model chosen. The other axioms hold in every Friedberg model. Furthermore, it is shown that there is a least Friedberg model which contains exactly those sets from the von Neumann universe which exist in all Friedberg models while there is no greatest Friedberg model. The complexity of the theory of a Friedberg model depends much on the model and ranges from the omega-jump of the halting problem to the omega-jump of a Pi-1-1-complete set.