A proof-theoretic characterization of the primitive recursive set functions
Journal of Symbolic Logic 57 (3):954-969 (1992)
| Abstract | Let KP- be the theory resulting from Kripke-Platek set theory by restricting Foundation to Set Foundation. Let G: V → V (V:= universe of sets) be a ▵0-definable set function, i.e. there is a ▵0-formula φ(x, y) such that φ(x, G(x)) is true for all sets x, and $V \models \forall x \exists!y\varphi (x, y)$ . In this paper we shall verify (by elementary proof-theoretic methods) that the collection of set functions primitive recursive in G coincides with the collection of those functions which are Σ1-definable in KP- + Σ1-Foundation + ∀ x ∃!yφ (x, y). Moreover, we show that this is still true if one adds Π1-Foundation or a weak version of ▵0-Dependent Choices to the latter theory | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,711 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJuris Steprāns (2005). Geometric Cardinal Invariants, Maximal Functions and a Measure Theoretic Pigeonhole Principle. Bulletin of Symbolic Logic 11 (4):517-525.
T. A. Slaman (1986). ∑1 Definitions with Parameters. Journal of Symbolic Logic 51 (2):453 - 461.
Richard Pettigrew (2010). The Foundations of Arithmetic in Finite Bounded Zermelo Set Theory. Cahiers du Centre de Logique 17:99-118.
Carl G. Jockusch Jr & Alexandra Shlapentokh (1995). Weak Presentations of Computable Fields. Journal of Symbolic Logic 60 (1):199 - 208.
Carl G. Jockusch Jr & Alexandra Shlapentokh (1995). Weak Presentations of Computable Fields. Journal of Symbolic Logic 60 (1):199 - 208.
Jeremy Avigad (2002). An Ordinal Analysis of Admissible Set Theory Using Recursion on Ordinal Notations. Journal of Mathematical Logic 2 (01):91-112.
Robert E. Byerly (1982). An Invariance Notion in Recursion Theory. Journal of Symbolic Logic 47 (1):48-66.
William I. Gasarch, Mark G. Pleszkoch & Robert Solovay (1992). Learning Via Queries in $\Lbrack +, < \Rbrack$. Journal of Symbolic Logic 57 (1):53 - 81.
William M. Farmer & Joshua D. Guttman (2000). A Set Theory with Support for Partial Functions. Studia Logica 66 (1):59-78.
Zlatan Damnjanovic (1995). Minimal Realizability of Intuitionistic Arithmetic and Elementary Analysis. Journal of Symbolic Logic 60 (4):1208-1241.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads1 ( #275,109 of 551,055 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
