Coequalizer in the category of primitive recursive functions

Question

What does a coequalizer in the category of primitive recursive functions look like? I know that in Set, a coequalizer is a minimum congruence but...what is it in particular in the category of primitive recursive functions (which is a subcategory of Set)?

Answer 1

For those readers unfamiliar with the class of primitive recursive functions, let me say that you may simplify things somewhat by fruitfully thinking of them as poor cousins of the computable functions. They were introduced, before Turing, as a natural class of computable total functions. But the class of primitive recursive functions is too weak to carry out the unbounded search operation that is so essential to computability (and which leads to partial functions, when the search fails). Nothing in my answer to the question will depend on any difference between the primitive recursive functions and the class of computable functions.

My answer is that neither the category of primitive recursive functions nor of computable functions admits co-equalizers. The basic reason is that for some primitive recursive functions, the smallest congruence is simply not a computable relation.

If one thinks about how one might build the congruence, this is to be expected, since there is a hidden unbounded search operation involved, and seemingly no way to know in advance whether it will succeed. Thus, we don't expect it to be computable. More specifically, if f,g are maps from A to B, then the desired congruence on B is the smallest relation making f(a) ∼ g(a) for all a. One concrete way to think about it is that two points b and c in B become equivalent with respect to ∼, if there is a zig-zag pattern a1,a2,... such that b=f(a1), g(a1)=f(a2), g(a2)=f(a3), etc. ending at g(an)=c (or swapping f and g in this pattern). Thus, to say that b ∼ c, we seem to need to discover whether one can get from b to c by following such a zig-zag pattern through the graphs of f and g. But that is an existential search, and we seem to have no computable way to determine whether we will find one or not. (The congruence, however, will always be computably enumerable, if f and g are computable.)

Let me give now a more detailed proof. Let A be a primitive recursive subset of the plane ω², such that the projection of A onto the first coordinate { a | exists b A(a,b) } is not primitive recursive. For example, let A be the set of pairs (a,b) such that a is a Turing machine program, and b is a code for a halting computation of program a on input 0. This is a primitive recursive set, since it is Delta₀ definable, but the projection of A onto the first coordinate is precisely the halting problem, the set of halting programs, and this is definitely not primitive recursive, because it is not even computable.

Now, consider the function f(a,b)=(a,b+2), if ¬A(a,b), otherwise f(a,b)=(a,b+1) if A(a,b) holds. Let i(a,b)=(a,b) be the identity function. Suppose towards contradiction that h:ω² to N is a co-equalizer of f and i. According to my (crude) understandiing of what this means, which I just learned this afternoon at the Wikipedia page here, it means that h.f = h.i, and h has the universal property that wheneverr h'.f = h'.i, then there is u with u.h = h'. (I am using dot for composition.)

Consider the case that a is not in the projection of A, so that A(a,b) never holds. In this case, we will have f(a,b)=(a,b+2) for all b, and so h(a,b) = h(i(a,b)) = h(f(a,b)) = h(a,b+2). By the universal property, h will send all the even values h(a,2b) to one value, and h(a,2b+1) to another. In particular, in this case, h(a,0) is not equal to h(a,1).

In the other case, suppose that a is in the projection of A, so that A(a,x) for some smallest value x. Now, we will still have h(a,b) = h(a,b+2) for values of b below x. But now, once at x, we see that h(a,x) = h(i(a,x)) = h(f(a,x)) = h(a,x+1). So here, h is now agreeing at an odd and even value of the second coordinate. It follows that all the odd and even values below x must be sent to the same value by h, and so in this case, h(a,0) = h(a,1).

Thus, the function g(a) = 1 if h(a,0) = h(a,1) and g(a) = 0 if h(a,0) not= h(a,1) is precisely the characteristic function of the projection of A. But that projection was not computable! It follows that h cannot be computable either. Thus, there can be no co-equalizer of the functions f and i within the category of computable functions, and hence also no co-equalizer within the category of all primitive recursive functions. QED

Finally, let me apologize for my clumsy working with category theory here. I am a category theory newbie, coming from logic and set theory, with a little computability theory. But if I may say so, I find this question attractively on the boundary between logic and category theory. The audience for the question would seem to be two large groups of talented people, logicians and category theorists, who I believe might benefit from greater interaction.