Ytukyg

Consider a functor $F : C to D$ . Let $F_1$ be a map from the objects of $C$ to the objects of $D$ and $F_2$ be a map on the arrows. Under what circumstances is $F$ uniquely determined by $F_1$ ?

Example 1

In a discussion with friends yesterday, the list type constructor [a] in Haskell was brought up as an example of an endofunctor $G$ of "Hask" (the category whose objects are Haskell types and morphisms are values). We conjectured that there's exactly one way to send arrows to arrows with $G$ once you picked where the types were sent. In other words, let $K$ be an endofunctor of $text{Hask}$ . If $K_1 = G_1$ , then $K = G$ .

Restating Example 1 without referring to programming. Let $W$ be the category defined as follows:

The objects of $W$ are types in a typed lambda calculus with function types $to $, products $times$ , sums $+$ , and isorecursive types $mu alpha mathop{.} T$ . The primitive types are $0$ (void) and $1$ (unit). Note that recursive types exist, but parametric polymorphism does not.

The arrows of $W$ are the values in the typed lambda calculus outlined above that are functions. For instance, $ lambda x. pi_1(x) $ is an element of homset from $(1 times 1)$ to $1$ . The values are only considered up to extensional equality. So $lambda x . x + x$ and $lambda x . 2 * x$ denote the same arrow.

The list functor $G$ , sends the object $3$ to $mu alpha mathop{.} 1 + 3 times alpha$ ... which is a list of values drawn from the type $3$ . I'm deliberately being vague about whether values of recursive types can be infinite or not. I think the argument works out regardless of whether infinite lists are permitted or forbidden.

I think it's the case that the functor laws constrain $G$ so that an arrow $f$ is mapped to an arrow that applies the function $f$ once to every item in the list and then assembles the list in the same order, without duplicating or deleting elements.

Counterexample 2

Let $M$ be a free category with one object $a$ generated by the non-identity arrow $f : a to a$ . $M$ is isomorphic to $mathbb{N}$ . The endofunctor $J$, defined as $J_1(x) = x$ and $J_2(x) = 2x$ , trivially maps the objects the same way as the identity functor does, but is not the identity functor.

Is there a neat set of conditions that, when met, force a functor to be uniquely determined by where it sends objects?

This is quite rare and will pretty much never happen for the typical sort of "category of all structures of a certain type" (as opposed to "diagram-like categories" like posets or monoids). In particular, suppose that $F:Cto D$ is a functor, $c$ is an object of $C$, and $i:F(c)to F(c)$ is an automorphism in $D$. Then we can define another functor $F':Cto D$ as follows. For all objects $a$, $F'(a)=F(a)$. For a morphism $f:ato b$ with $a,bneq c$, $F'(f)=F(f)$. For a morphism $f:ato c$ with $aneq c$, $F'(f)=iF(f)$. For a morphism $f:cto b$ with $bneq c$, $F'(f)=F(f)i^{-1}$. Finally, for a morphism $f:cto c$, $F(f)=iF(f)i^{-1}$.

It is easy to check that this $F'$ is indeed a functor. Intuitively, it is the same functor as $F$, except that we've "relabeled" $F(c)$ by the isomorphism $i$. Indeed, $F'$ is naturally isomorphic to $F$, by a natural isomorphism that is the identity on all objects except $c$ but is $i$ on $c$.

Since $F'$ is the same on objects as $F$, this will be a counterexample unless $F'$ happens to be equal to $F$. This will rarely be the case for every possible choice of $c$ and $i$. For instance, if $F$ is faithful, this implies the automorphism group of every object of $C$ must be abelian (otherwise pick $i$ to be the image of some noncentral automorphism of an object $c$, and $F'$ will not agree with $F$ on automorphisms of $c$). This should in particular show that your list functor is actually not uniquely determined by where it sends objects.