Timeline for Analogues of Primitive Recursive Functions
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2015 at 14:38 | comment | added | Thomas Benjamin | @NoahS: By the way, have you any reasonably natural choice for $T_{\mathbb A}$ and $F_{\mathbb A}$ for $\mathbb A$ admissible satisfying the criteria you mentioned in your comment? I would be interested in knowing what it is. | |
| Mar 13, 2015 at 17:55 | comment | added | Thomas Benjamin | (cont.) question but Prof. Lurie did not take this route. That is why I asked what motivated his question. Have you any idea? Please let me know. | |
| Mar 13, 2015 at 17:49 | comment | added | Thomas Benjamin | (cont.) functions by means of categories? If so, then (at least for first-order structures $\mathfrak U$) the morphisms will be the primitive computable functions of Moschovakis. Since the class $V_{KP(U)}$ for the structure ($V_{KP(U)}$,$\in$) is a first-order structure, the primitive computable functions should hold on $V_{KP(U)}$ and the elements of $V_{KP(U)}$ generated by the primitive computable functions and the subclass closed under them via the composition operation $\circ$ should form a category. One should then be able to use category-theoretic methods to answer Prof. Lurie's | |
| Mar 13, 2015 at 16:01 | comment | added | Thomas Benjamin | (cont.) tie-in to topos theory--my comment] with a natural number object (in the sense of the Peano-Lawvere Axiom)' generated by the empty category. In this category, every morphism 1$\rightarrow$$\mathbb N$ represents a natural number and every morphism $\mathbb N$$\rightarrow$$\mathbb N$ represents a function. Furthermore, the set of functions represented by the morphisms of this category contains strictly [but does not characterize (see Thm. 2.3 and Corollary 2.4)]the primitive recursive functions...[this from her abstract]." Is it possible to characterize the primitive recursive | |
| Mar 13, 2015 at 13:26 | comment | added | Thomas Benjamin | @NoahS: The 'process' is abstracting the notion of general recursive function from $\mathfrak N$= (N,+, $\cdot$) to arbitrary (unordered) first-order structures $\mathfrak U$, primarily as a tool for hierarchy theory. What puzzles me is why Prof. Lurie, who wrote an 800+ page monograph on higher topos theory, would be even asking a question about admissible sets. Why? Because Marie-France Thibault, in the Journal of Pure and Applied Algebra (Vol. 24, 1982, pp 79-83) wrote a paper titled "Pre-Recursive Categories" in which she studies "the free 'cartesian closed category [here is the | |
| Feb 21, 2015 at 1:40 | comment | added | Noah Schweber | (cont'd) to me, though, that seems strong evidence (if true) that that's the wrong approach. That's why I asked: "get according to what process?" It seems you have some fixed picture of how this generalization should occur, but that picture isn't clear to me. | |
| Feb 21, 2015 at 1:38 | comment | added | Noah Schweber | This doesn't really address the question. It seems quite easy to define some theory $T_\mathbb{A}$ satisfied by $\mathbb{A}$ and some class of functions $F_\mathbb{A}$ on $\mathbb{A}$ such that (1) $T_\mathbb{A}$ prove sthat each $f\in F_\mathbb{A}$ is total and (2) $F_{HF}=PrimRec$. The question is whether there is a reasonably natural choice of such $T$ and $F$. When you bring up Moschovakis it seems you are homing on on specifically one approach, and then arguing that, if we follow that approach, no such class of functions exists (although even here I don't follow your reasoning); | |
| Feb 20, 2015 at 14:06 | comment | added | Thomas Benjamin | (cont.) not the primitive recursive functions over $\mathfrak N$=(N,+,$\cdot$). | |
| Feb 20, 2015 at 14:03 | comment | added | Thomas Benjamin | @NoahS: If this helps any, the primitive, prime, and search computable functions of Moschovakis are defined over arbitrary first-order structures $\mathfrak M$ and are the analogues of the primitive recursive functions and general recursive functions over $\mathfrak N$=(N,+,$\cdot$). Prof. Lurie, in the second paragraph of his question, was interested in the admissible set $\mathbb A$=$\mathbb H$$Y$$P_{\mathfrak M}$ By the theorem I mentioned, the 'primitive recursive' functions over $\mathbb H$$F_{\mathfrak M}$ are the primitive computable functions of Moschovakis, | |
| Feb 20, 2015 at 1:55 | comment | added | Jacob Lurie | I'm afraid that I don't follow either. What exactly are you saying you can rule out? | |
| Feb 19, 2015 at 23:13 | comment | added | Noah Schweber | I'm a little confused - what do you mean by " . . . the generalization of primitive recursive function you get . . ."? Get according to what process? Also, how do you get from Barwise' result to the statement that no such class exists? (I'm probably just missing something, but this isn't clear to me.) | |
| Feb 19, 2015 at 18:31 | history | edited | Thomas Benjamin | CC BY-SA 3.0 |
fixed grammar
|
| Feb 19, 2015 at 18:23 | history | answered | Thomas Benjamin | CC BY-SA 3.0 |