3
$\begingroup$

Since a pullback of two functions f and g with common codomain into Set category is just a subset of cartesian product like this: {(x,y)/f(x)=g(y)} (with two more functions not important here) could this pullback set be the empty set in some cases (for exemple in the case of constant functions)?

My question is related to find pullbacks for primitive recursive functions, where the functions are all of them total and the domain and codomain are powers of natural numbers set. Which could be the aspect of those supposed pullbacks for constant functions since the empty set is not there available? Do they exist?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ "could this pullback set be the empty set in some cases?" Yes! Pullback to a point is just "fibre of the map" so sure a fibre can be empty. $\endgroup$
    – Kevin Buzzard
    Commented Feb 25, 2010 at 15:24
  • $\begingroup$ Pullback to a point? You mean a degenerate case of a pullback? Makes it any sense? And..what if we haven't the empty set available? $\endgroup$
    – Doctor Gibarian
    Commented Feb 25, 2010 at 15:37
  • $\begingroup$ Are you asking about the existence of pullbacks in the Lawvere Theory of primitive recursive functions? ncatlab.org/nlab/show/Lawvere+theory $\endgroup$
    – François G. Dorais
    Commented Feb 25, 2010 at 15:40
  • $\begingroup$ Ximo, it looks to me as if your first paragraph is asking the following question. (If not, please clarify.) Let X, Y and Z be sets, and let f: X --> Z and g: Y --> Z be functions. Is it possible that the pullback of f with g is empty? Kevin answered "no, e.g. take X to be the one-element set". More specifically, you could take X and Y both to be one-element sets, Z to be a two-element set {z_1, z_2}, and f and g to be the functions with respective images z_1 and z_2. $\endgroup$
    – Tom Leinster
    Commented Feb 25, 2010 at 16:22
  • $\begingroup$ Mh. In that case the square giving raise to the pullback woludn't be commutative and therefore the pullback set would be empty. Isn't it? My question is: could we make that for prim. rec. functions (where all of them are total and we've not the empty set as a possible domain)? Have they pullbacks? F.G.Dorais: I wish I could find that info in the web you send, but I don't see it there. Thank you anyway. $\endgroup$
    – Doctor Gibarian
    Commented Feb 25, 2010 at 16:34

2 Answers 2

Reset to default
2
$\begingroup$

I'm not sure if this is what you want, but it is not difficult to prove that if f and g are primitive recursive functions, then the set A = { (x,y) | f(x) = g(y) } is a primitive recursive subset of the natural number plane. That is, the characteristic function of this set is primitive recursive. The (trivial) reason is that the characteristic function is simply the composition of the characteristic function of equality with f and g.

One can therefore have primitive recursive access to that set when defining other primitive recursive functions, such as the ones you will need in your commutative diagram.

As you and Reid have observed, when this set is empty, then there can be no pull back in the category of primitive recursive functions. But when it is nonempty, then we can define primitive recursive functions r, s on N2 to make the commutative square, by mapping r(x,y) = f(x) and s(x,y) = g(y), when (x,y) is in A, and otherwise r(x,y) = a and s(x,y) = b for some fixed (a,b) in A. This makes the square commute, and it has the universal property for pullbacks, because if r' and s' from N to N make the square commute (fr' = gs'), then we can define t:N to N2 by t(n) = (r'(n),s'(n)). By commutativity, this is inside A, and the whole diagram commutes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, you can construct that diagram and that (prim rec) set but not to do it with all pair of functions. So that category has not pullbacks, as Reid Barton explains below. I was not sure about it. Thank you to all. $\endgroup$
    – Doctor Gibarian
    Commented Feb 25, 2010 at 17:35
3
$\begingroup$

I am a little confused why you are asking this question, when it seems that you have already arrived at the correct conclusion. But, I will take it at face value. The category of primitive recursive functions you describe does not have pullbacks. Indeed, take your example of two different constant functions with the same codomain and just apply the definition of pullback. There is no way to complete the diagram to a square at all, let alone a universal way.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .