MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question
What is "the primitive recursive functions category"? – Mike Shulman Jan 22 '10 at 20:10
That kind of attitude isn't going to help you get your questions answered. When you use nonstandard or vague terminology the burden is upon you to make sure you are understood, not upon us to understand what you're trying to say. – Qiaochu Yuan Jan 22 '10 at 21:27
Ximo, I like your question a lot. As I explain in my answer, it is attractively situated on the boundary between logic and category theory, and has a potential audience of talented people from these two areas who would benefit from greater interaction. I edited your question slightly (and re-tagged), but I think you could do more to make the category you refer to more clear. Click on "edit". Also, you can delete the comment that I think people understood negatively. Click on the 'x'. Your question has a pure universal algebra formulation: Is the smallest congruence of PR functions also PR? – Joel David Hamkins Jan 23 '10 at 5:04
@Ximo, you can't expect everyone here to know everything about every subfield of mathematics, and your response was really out of line. – Harry Gindi Jan 23 '10 at 7:40
Take it easy, I'm a beginner in this webpage. I'll do it better next. Have a good day and thank you for the response to Joel David Hamkins. – Doctor Gibarian Jan 23 '10 at 12:49
up vote 7 down vote accepted

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 ω2, 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 Delta0 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:ω2 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.