[FOM] Axiom of Choice in Category Theory

[Andreas Blass]

D is required to be discrete because, without some such assumption, the 
proposed axiom would be false.  Suppose, for example, that D is a 
category with two objects and one morphism f between them (plus of 
course the identities), that C is the subcategory consisting of the two 
objects but only the identity morphisms, and that F is the inclusion 
functor.  Any functor G from D to C must send both objects to the same 
object, as otherwise there's no place for it to send f.  But then FGF 
will be a constant functor and thus not equal to F.

Even if one requires F to be surjective on objects and on morphisms (so 
that one no longer has the preceding counterexample, and so that FGF=F 
amounts to saying that FG is the identity functor on D), there are 
still counterexamples.  Take C to have 4 objects, called a, b, c, d, 
with two morphisms (in addition to the identities), one from a to c and 
one from b to d.  Let D have 3 objects, called x, y, z, with morphisms 
from x to y and from x to z.  Let F be the functor sending both a and b 
to x, sending c to y, sending d to z, and acting on morphisms in the 
only possible way.  Then there is no G such that FGF=F.  No matter how 
you define G(x), you won't be able to lift both of the morphisms of D 
unless you make G(y)=G(z), but then FGF won't equal F.

There is no reason to expect F and G to be adjoint functors, especially 
since there may be many (inequivalent) G's for the same F.  For an 
extreme example, suppose C and D are discrete categories, i.e., 
essentially just sets, and F is a surjection, so G is a choice function 
(choosing for each object d in D some object c=G(d) in C such that 
F(c)=d).  The only way such a G could be an adjoint of F (on either 
side) would be if F were one-to-one (and G its inverse), i.e., when no 
actual "choice" is involved.

More generally, since the axiom of choice is used to produce things 
that we can't explicitly define, while adjoint functors are unique (up 
to natural isomorphism) when they exist, I wouldn't expect much of a 
connection between them, unless one takes advantage of the clause "up 
to natural isomorphism" as follows.   If I have a family of functors, 
and each of them has an adjoint, then to get a specific family of 
adjoints, one for each of them, I would in general need the axiom of 
choice.  Does that count as a connection?  But even in this situation, 
Michael Makkai has worked out a theory, replacing functors with what he 
calls anafunctors, that avoids the need for the axiom of choice.

Andreas Blass

Laurent Delattre wrote:
> I would like to discuss about the Axiom of Choice in
> Category Theory.
>
> If I am not mistaken, it is formulated the following
> way:
>
> "Let C and D be (small) categories such that C is not
> empty and D is discrete. Let F be a functor from C to
> D. There exists a functor G from D to C such that
> FGF=F".
>
> Can someone explain why  D is required to be discrete?
>
> Can F and G be seen as a pair of adjoint functors?
>
> More generally, what is the relation between the Axiom
> of Choice and adjunction?