1
$\begingroup$

[Edited]

Let $\mathsf{PR}$ be the category defined as follows:

Choose a specific presentation of Primitive Recursive Arithmetic, that is, with a specific set of terms for primitive recursive functions.

Let the objects of $\mathsf{PR}$ be any $1$-ary term $A(x)$ in PRA. (Intuitively, think of a primitive recursive set given explicitly as as as set of zeros of some term).

Let the morphisms $\phi: A \rightarrow B$ of $\mathsf{PR}$ be a $1$-ary terms $\varphi(x)$ such that $\vdash_{PRA} A(x) = 0 \Rightarrow B(\varphi((x)) = 0$. Identify two morphisms $\varphi$ and $\psi$ if PRA proves $\varphi(x) = \psi(x)$.

Composition of morphisms is composition of terms.

Question: does this category have other names or other presentations? It seems like this category should be of interest.

Any references would be appreciated.

$\endgroup$
11
  • 2
    $\begingroup$ What does "$\vdash_{PRA}$" mean? (I read that as "proves, together with the axioms of primitive recursive arithmetic," but I just want to be sure, especially because you've already used "$PRA$" to mean something which is not a theory. $\endgroup$ Feb 17, 2015 at 23:54
  • $\begingroup$ Yes, I meant it as you say. It means proves in primitive recursive arithmetic. $\endgroup$
    – Rex Butler
    Feb 18, 2015 at 0:01
  • $\begingroup$ What is $\Gamma$? And how do you compose these morphisms? $\endgroup$ Feb 18, 2015 at 10:12
  • 1
    $\begingroup$ Is it intended that there is a morphism between any two objects (if this is a category at all, for what are the identity morphisms and what is the composition)? I can stick into $\Gamma$ something that is false, say $0 = 1$, and get a morphism from anywhere to anywhere. $\endgroup$ Feb 18, 2015 at 10:54
  • 1
    $\begingroup$ As it is defined now, the category seems pretty badly behaved: e.g., all nonconstant terms are mono and epi, while the only isomorphisms are those given by the $x$ term, and next to no diagrams have limits or colimits. I think it would be more natural to identify morphisms given by terms $\phi(x),\psi(x)$ whenever PRA proves $A(x)=0\to\phi(x)=\psi(x)$. $\endgroup$ Feb 18, 2015 at 18:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.