__Preprint:__

**
Arnold Beckmann, Sam Buss, Sy-David Friedman,
Moritz Müller, and Neil Thapen
"Cobham Recursive Set Functions and Weak Set Theories"
In **

**
Download
preprint.
**

**Abstract:**
The Cobham recursive set functions (CRSF) provide a notion of
polynomial time computation over general sets.
In this paper, we determine a subtheory KP^{U}_{1} of
Kripke-Platek set theory whose Σ_{1}-definable functions
are precisely CRSF. The theory KP^{U}_{1} is based on the
∈-induction scheme for Σ_{1}-formulas
whose leading existential quantifier satisfies
certain boundedness and uniqueness conditions.
Dropping the uniqueness condition and adding the axiom
of global choice results in a theory KPC^{≤}_{1} whose
Σ_{1}-definable functions are CRSF^{C},
that is, CRSF relative to a global choice function *C*.
We further show that the addition of global choice
is conservative over certain local choice principles.