Timeline for Analogues of Primitive Recursive Functions
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2016 at 15:56 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 28, 2016 at 15:55 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 29, 2016 at 15:38 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 30, 2016 at 14:11 | answer | added | Gro-Tsen | timeline score: 2 | |
| Feb 19, 2015 at 18:23 | answer | added | Thomas Benjamin | timeline score: 0 | |
| Feb 15, 2015 at 13:21 | comment | added | Thomas Benjamin | @JacobLurie: Considering your comment to Ulrik,I would like to know why you are asking the question--what is its motivation? Also, when you use the term $A$=$HYP_{M}$, are you meaning $\mathbb HYP$($\mathbb A_{\mathfrak M}$) as used in chapter IV, def 1.4 of $Admissible$ $Sets$ $and$ $Structures$? | |
| Jan 28, 2015 at 18:46 | comment | added | Jacob Lurie | @Ulrik That paper looks quite relevant, but not exactly what I'm looking for. If I'm reading it right, it seems to be about functions whose totality is provable using very weak set-theoretic assumptions, analogous to the characterization of primitive recursive functions as those functions which are provably total using very weak arithmetic assumptions. But I'm hoping for something which is specific to a fixed admissible set $A$, and specializes to primitive recursive arithmetic when I take $A = HF$. (Something that would generalize PRA, rather than being analogous to PRA.) | |
| Jan 28, 2015 at 18:42 | comment | added | Jacob Lurie | @Carlo It is relevant, but I am asking for something more refined: I want to consider not just which sets are $\Sigma_1$-definable in $A$, but when $A$ "knows" that one $\Sigma_1$-set is contained in another. | |
| Jan 21, 2015 at 14:43 | comment | added | Ulrik Buchholtz | Jensen and Karp's primitive recursive set functions give your generalized functions, and Michael Rathjen, A proof-theoretic characterization of the primitive recursive set functions, JSL 57(3), 1992 (www1.maths.leeds.ac.uk/~rathjen/PrimRec.pdf) seems to give the theory that you want. | |
| Jan 21, 2015 at 6:54 | comment | added | The Masked Avenger | When I read this I am reminded of Fenstad and Abstract Recursion Theory. I don't quite know why; it may not fit in with your program. | |
| Jan 21, 2015 at 5:36 | comment | added | Rachid Atmai | Moschovakis' book "Elementary induction on abstract structures" develops recursion theory on admissible sets. In the book he proves the Barwise Gandy Moschovakis theorem which says that if $A$ is a transitive set closed under pairing then the inductive relations on the structure $(A,\epsilon)$ are exactly the relations on $A$ which are $\Sigma_1$ over an admissible set. I don't know if this is directly relevant to your question, or if the theory reduces to PRA on $A$ if $A=H_{\omega}$. (see chapter 9 of the book). | |
| Jan 21, 2015 at 4:34 | history | asked | Jacob Lurie | CC BY-SA 3.0 |