# [FOM] Axiom of Choice in Category Theory

Andreas Blass ablass at umich.edu
Tue Jan 31 09:58:08 EST 2006

```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