A simple computational interpretation of set theory

Details A simple computational interpretation of set theory A simple computational interpretation of set theory

2010-05-24

arxiv.org/abs/1005.4380v3

Mathematics

Logic

v3: various copyediting, added thm 5.2 to better explain 6.4

Scientific paper

CZF is a system of set theory which, over classical logic, is equivalent to ZF, while over intuitionistic logic, it has a well-known constructive type-theoretic interpretation. This article introduces a simpler, intuitive family of constructive interpretations: sets are well-founded extensional computable conditional enumerations of sets. One interpretation in this family is just this: all sets are inductively built from the empty set by iterating the construction {f_n | n:N ^ g_n = h_n}, where, in turn, g and h are computable sequences of sets, and f is a computable sequence such that f_n is a set when g_n and h_n are extensionally equal. Extended Church's Thesis, an assumption which is incompatible with classical logic, is required to make this a model of CZF. Besides its foundational interest, it yields a direct conservativity result for certain choice principles, the Subcountability axiom, and for some so-called Omniscience principles, including first-order arithmetic Omniscience. A larger interpretation in this family also models the Regular Extension Axiom.

Affiliated with

Also associated with

No associations

Rating

A simple computational interpretation of set theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A simple computational interpretation of set theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simple computational interpretation of set theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119533