nLab
anafunctor

Idea

A basic fact in ordinary category theory is that a functor $f:C\to D$ is an equivalence of categories – in that there is a functor $g:D\to C$ and natural isomorphisms $f\circ g\simeq {\mathrm{Id}}_D$ and $g\circ f\simeq {\mathrm{Id}}_C$ – precisely if it is an essentially surjective full and faithful functor.

But this statement does crucially depend on the axiom of choice: the functor $g$ is obtained by choosing for each object $d\in D$ an object $c\in C$ such that $f(c)\simeq d$.

The notion of anafunctor , introduced by Makkai, is a modification of the notion of functor such that even in the absence of the axiom of choice, the statement remains true that an anafunctor is an equivalence of categories precisely if it is essentially surjective and full and faithful.

Since questions concerning the axiom of choice tend to look a bit esoteric to those not actively interested in questions of foundations, it is helpful to think of this more generally in terms of internal category theory, where the concept is of independent use and in fact well known by other names than “anafunctor”:

consider some ambient category $ℰ$ internal to which we want to do category theory. A good example to keep in mind is the category Top of topological spaces. The axiom of choice does fail in Top, but for a very non-esoteric reason: in the simple sense that not every continous epimorphism $P\to X$ between topological spaces has a continuous section.

Then it may easily happen that an internal functor $f:C\to D$ between internal categories in $ℰ$ (for instance between topological categories) is k-surjective for all $k$, but still does not admit a weak inverse in $ℰ$. For instance the functor $C(U)\to X$ from a Cech groupoid associated to an open cover $U={\coprod }_i{U}_i$ of a topological space $X$ is k-surjective for all $k$ in $ℰ=\mathrm{Top}$, but in general does not admit a weak inverse, simply because the continuous function ${\coprod }_i{U}_i\to X$ does not have a continuous section, unless one of the $U_i$ is already equal to $X$. Entirely analogously, Makkai considered $ℰ={\mathrm{Set}}_{\neg C}$ to be the category Set of sets without the axiom of choice, where the same may happen: not every k-surjective functor for all $k$ has a weak inverse.

There is a standard way to deal with such situations where we are faced with a category – here the category $\mathrm{Cat}(ℰ)$ of categories internal to $ℰ$ – some of whose morphisms look like they ought to have inverses, but do not: we call these would-be invertible morphisms weak equivalences such that our category becomes a category with weak equivalences or a homotopical category. Then we pass to the corresponding homotopy category: the universal “improvement” of our category such that all the would-be invertible morphism do become invertible.

Here we take the weak equivalences in $\mathrm{Cat}(ℰ)$ to be the internal functors that are internally k-surjective for all $k$. It turns out that this choice of weak equivalences is particularly well-behaved in that it actually forms a calculus of fractions. Due to the early work on abstract homotopy theory by Gabriel and Zisman, there is simple explicit construction of the corresponding homotopy category $\mathrm{Ho}(\mathrm{Cat}(ℰ))$ in this case: the objects are the same as those of $\mathrm{Cat}(E)$ – hence categories internal to $ℰ$ for us – and the morphisms $f:C\to D$ are spans of morphism in $\mathrm{Cat}(ℰ)$

$$\begin{array}{ccc}\hat{C}& \stackrel{\hat{f}}{\to }& D\\ {\downarrow }^{\in W}\\ C\end{array},$$\array{ \hat C &\stackrel{\hat f}{\to}& D \\ \downarrow^{\mathrlap{\in W}} \\ C } \,,

where the left leg is a weak equivalence., hence for us: where the left leg is an internal functor that is $k$-surjective for all $k$. (This is the beginning of the construction of the Dwyer-Kan localization at our chosen weak equivalences.)

For the case $ℰ=\mathrm{Top}$ such a span is a morphism out of a Cech cover . For instance for $C=X$ a topological space regarded as a topological category, for $G$ a topological group and $D=BG$ its delooping one-object topological groupoid, such a span is a Cech cocycle on $X$ with values in $G$.

And finally: for the case that $ℰ={\mathrm{Set}}_{\neg C}$ is the category of sets without the axiom of choice, such a span is an anafunctor: a functor $\hat{C}\to C$ that is is surjective on objects and full and faithful, together with a functor $\hat{C}\to D$ out of the “resolution” of $C$.

So one can understand ordinary anafunctors as follows:

1. first we consider that the axiom of choice may fail, which makes previously invertible functors non-invertible;

2. then we universally force the now non-invertible functors to become invertible after all, by throwing in formal inverses for them.

Under the name anafunctors these concepts were first developed by Michael Makkai to do ordinary category theory with a foundations that does not include the axiom of choice. Later they were applied by Toby Bartels to internal categories, where the axiom of choice is simply not an option. These actually turned out to be known already (at least up to equivalence) in some contexts, in particular as Hilsum-Skandalis morphism?s between Lie groupoids.

Every functor may be interpreted as an anafunctor; that every anafunctor is equivalent to a functor is equivalent to the axiom of choice, in which case the inclusion of functors into anafunctors is in fact an equivalence of categories. But if you ignore functors and deal only with anafunctors (or saturated anafunctors), then the theory is entirely constructive (without using the axiom of choice or even excluded middle). Theorems that classically required choice now don't require choice (and indeed become constructive) with anafunctors. Thus, anafunctors (or even saturated anafunctors) are the correct notion to use if you are a constructivist (at least as long as you found mathematics on some sort of set theory at all); but they are also often the correct notion to use in internal category theory.

Definitions

Given categories $C$ and $D$, an anafunctor $F:C\to D$ may be rather slickly defined as a span of ordinary (strict) functors $C\stackrel{\sigma }{\leftarrow }\overline{F}\stackrel{\tau }{\to }D$ (where $\overline{F}$ is some category), with the property that the functor $\sigma :\overline{F}\to C$ is both faithful and (strictly!) surjective on both objects and morphisms (therefore both full and essentially surjective on objects). It is also possible to define an anafunctor as a span in which $\sigma$ is merely a weak equivalence (that is, faithful, full, and essentially surjective on objects), although that is slightly more complicated to work with.

In more explicit detail, an anafunctor $F:C\to D$ consists of:

• a set $\mid F\mid$ of specifications of $F$ (which corresponds to the set of objects of $\overline{F}$);

• maps $\sigma :\mid F\mid \to C$ and $\tau :\mid F\mid \to D$ (taking values in objects). Given $x:C$ and $y:D$, we say that $y$ is a specified value of $F$ at $x$ if, for some $s:\mid F\mid$, $x=\sigma (s)$ and $y=\tau (s)$; in this case, $s$ specifies $y$ as a value of $F$ at $x$, and we write $F_s(x)=y$. That is,

  $$F_s(x)≔\tau (s).$$F_s(x) \coloneqq \tau(s) .

  We say that $y$ is a value of $F$ at $x$ if $y$ is isomorphic (in $D$) to some specified value of $F$ at $x$; we write $F(x)\cong y$. (There is no notion of the value of $F$ at $x$, except in the up-to-isomorphism sense of the generalised the, and $F(x)=y$ is a meaningless statement.);

• for each $s,t:\mid F\mid$ and morphism $f:\sigma (s)\to \sigma (t)$ in $C$, a morphism

  $$F_{s,t}(f):F_s(x)\to F_t(y)$$F_{s,t}(f)\colon F_s(x) \to F_t(y)

  in $D$, where $x≔\sigma (s)$ and $y≔\tau (s)$. Similarly to the above, we can define whether a given morphism $g$ in $D$ is a specified value of $F$ at a given morphism $f$ in $C$ or whether $g$ is (merely) a value of $F$ at $f$. (Again, there is no notion of the value of $F$ at $f$.);

• $\sigma$ is a surjective function. Thus, $F$ has some value at any given object or morphism of $C$. (In the internalized case, this requirement can become quite complicated; for example, internal to Diff, one requires a surjective submersion?.);

• $F$ preserves identities. That is, given $s:\mid F\mid$, the value of $F$ specified by $s$ and $s$ at the identity of $\sigma (s)$ is the identity of $\tau (s)$, or (in symbols) $F_{s,s}({id}_{\sigma (s)})={id}_{\tau (s)}$, or (whenever this makes sense)

  $$F_{s,s}({id}_x)={id}_{F_s(x)};$$F_{s,s}(\id_x) = \id_{F_s(x)} ;

• $F$ preserves composition. That is, given $s,t,u:\mid F\mid$, $f:\sigma (s)\to \sigma (t)$, and $g:\sigma (t)\to \sigma (u)$,

  $$F_{s,u}(f;g)=F_{s,t}(f);F_{t,u}(g).$$F_{s,u}(f;g) = F_{s,t}(f);F_{t,u}(g) .

  (Here the semicolon indicates composition in the anti-Leibniz order.).

From the above explicit data, the category $\overline{F}$ is constructed as follows: the objects of $\overline{F}$ are the elements of $\mid F\mid$, while a morphism $s\to t$ in $\overline{F}$ is simply a morphism $\sigma (s)\to \sigma (t)$ in $C$. Then $\sigma$ extends to a surjective faithful functor from $\overline{F}$ to $C$ (acting as the identity on morphisms), and $\tau$ extends to a functor from $\overline{F}$ to $D$ (mapping the morphism $f:s\to t$ in $\overline{F}$ to $F_{s,t}(f):\tau (s)\to \tau (t)$ in $D$).

An anafunctor $F$ is saturated if, whenever $F(x)\cong y$, $F_s(x)=y$ for some unique specification $s$, where the unicity of $s$ depends not only on $x$ and $y$ but also on how $y$ is a value of $F$ at $x$. To be precise: if $g:y\prime \to y$ is an isomorphism in $D$ and $F_{s\prime }(x)=y\prime$ for some specification $s\prime$, then there is a unique specification $s$ such that $F_{s\prime ,s}({id}_x)=g$ (where in particular, $\sigma (s)=x$ and $F_s(x)=y$). Every anafunctor $F:C\to D$ has a saturation $\overline{F}$; $\overline{F}$ is a saturated anafunctor and $F\cong \overline{F}$ in the category of anafunctors from $C$ to $D$. In fact, the inclusion of the saturated anafunctors into the anafunctors (as a full subcategory) is an equivalence of categories (given fixed $C$ and $D$).

Categories, anafunctors, and a suitably defined notion of ananatural transformation between them form a bicategory ${\mathrm{Cat}}_{\mathrm{ana}}$; an internal equivalence in this 2-category is called an anaequivalence. Every functor may be interpreted as an anafunctor, with $\mid F\mid$ always taken to be (the set of objects in) $C$ itself and $\sigma$ the identity functor. Indeed, there is a 2-functor to ${\mathrm{Cat}}_{\mathrm{ana}}$ from the strict 2-category $\mathrm{Str}\mathrm{Cat}$ of categories, functors and natural transformations; this functor is an equivalence if and only if the axiom of choice holds. Thus, most mathematicians will identify ${\mathrm{Cat}}_{\mathrm{ana}}$ and $\mathrm{Str}\mathrm{Cat}$ as simply Cat, the $2$-category of categories; however, mathematicians who doubt the axiom of choice will distinguish them. While anafunctors exist in any case, there is an ideological statement that may be implied by their use: that $\mathrm{Cat}$ is really ${\mathrm{Cat}}_{\mathrm{ana}}$ rather than $\mathrm{Str}\mathrm{Cat}$.

Internal anafunctors

We generalise the slick definition of anafunctors as spans rather than the detailed definition involving specified values.

Let $S$ be a category containing a collection of morphisms called “covers” such that

• every isomorphism is a cover,
• covers are closed under composition,
• any pullback of a cover exists and is a cover (pullback stability),
• every cover is the quotient object of its kernel pair, i.e. is an effective epimorphism. (Since all pullbacks of covers exist, this is equivalent to saying that every cover is a regular epimorphism.)

Note that these are precisely the axioms saying that the singleton families $\{p:V\to U\}$ where $p$ is a cover form a subcanonical Grothendieck pretopology. One important class of examples is when $S$ is a regular category and the covers are the regular epimorphisms. Another is when $S$ is the category of smooth manifolds and the covers are the surjective submersions.

In such a situation, if $C$ and $D$ are internal categories in $S$, we define an anafunctor $C\to D$ to consist of a span $C\leftarrow F\to D$ of internal functors such that:

1. $F_0\to C_0$ (the map of objects) is a cover.

2. $F\to C$ is fully-faithful, in the internal sense that the following is a pullback square:

   $$\begin{array}{ccc}{F}_1& \to & C_1\\ \downarrow & & \downarrow \\ F_0\times F_0& \to & C_0\times C_0\end{array}$$\array{F_1 & \to & C_1 \\ \downarrow && \downarrow \\ F_0\times F_0& \to & C_0\times C_0}

Note that assuming $F_0\to C_0$ is a cover, so is $F_0\times F_0\to C_0\times C_0$ (it is a composition of pullbacks of $F_0\to C_0$); thus the above pullback always exists.

By the remarks above, if $S$ is Set and “cover” means “surjection” (an example where the covers are the regular epimorphisms), then we recover the original external notion of (small) anafunctor. An anafunctor, defined in this way, is saturated just when the map $\mathrm{core}(F)\to \mathrm{core}(C\times D)$ of cores is an isofibration, so we need an internal notion of core to define saturated anafunctors internally. An anafunctor is an anaequivalence when $F\to D$ is fully faithful and a cover on objects; for Lie groupoids, these are the Morita equivalences.

If $C\leftarrow F\to D$ and $C\leftarrow G\to D$ are internal anafunctors, we define an ananatural transformation between them (or simply a natural transformation, given the context) to be a natural transformation between the two induced internal natural transformations $F{\times }_{C}G\to D$. We can then prove that internal categories, anafunctors, and natural transformations form a bicategory. (Interestingly, you may need the axiom of choice in the metalogic? to conclude this, depending on whether there is a natural way to choose the necessary pullbacks; else you get an anabicategory, in which the composition functors are anafunctors.)

The role of the assumptions about covers is:

• Identity maps must be covers in order to have identity anafunctors (and more generally, for every functor to give rise to an anafunctor).
• To compose anafunctors by pullback, the pullbacks of covers must exist and be covers, and covers must be closed under composition.
• To define $F{\times }_{C}G$ and obtain a notion of natural transformation, we again need covers to have pullbacks.
• To define composition of natural transformations between anafunctors, we need covers to be effective; see diagram (118) in HGT1.

Note: in Section 1.1.5 of HGT1, the following additional axiom was assumed on the class of covers:

• every congruence involving a cover has a quotient object which is a cover.

This is not needed for anafunctors but is used to relate descent to bundles (and then to $2$-bundles).

Homotopy-theoretic interpretation

Observe that the surjective-on-objects equivalences are precisely the acyclic fibrations for the folk model structure on Cat. Therefore, anafunctors can be identified with the “one-step generalized morphisms” in $\mathrm{Cat}$ whose first leg is not just a weak equivalence but an acyclic fibration. However, it appears that the folk model structure on Cat only exists (with its weak equivalences being the fully faithful and essentially surjective maps) under the assumption of some choice—though full AC is not needed, COSHEP suffices.

More generally, it is proven in EKV that if $S$ has a Grothendieck coverage, then under suitable additional conditions on $S$ (and, of course, the axiom of choice assumed external to $S$), there is a model structure on the category $\mathrm{Cat}(S)$ of internal categories in $S$ relative to that coverage. The internal anafunctors relative to the given coverage, as defined above, can then once again be identified with the spans whose first leg is an acyclic fibration.

Since all objects in the folk model structure on Cat are fibrant, according to Kenneth Brown’s theorem in homotopical cohomology theory it follows that one-step generalized morphisms already realize the full localization, i.e. they represent all morphisms in the homotopy category $\mathrm{Ho}(\mathrm{Cat})$.

If we specialize to groupoids, with their folk model structure by Brown-Golasinski, then by the general idea of homotopical cohomology theory this means that anafunctors between groupoids represent nonabelian cocycles on groupoids with values in groupoids. By the notion of codescent such homotopical cocycles are related to descent data that enters the definition of sheaves and stacks.

Questions of size

In general, it seems that even if $C$ and $D$ are small categories, then the category $\mathrm{Ana}(C,D)$ of anafunctors from $C$ to $D$ is not necessarily even essentially small, and thus the 2-category ${\mathrm{Cat}}_{\mathrm{ana}}$ of categories and anafunctors is not cartesian closed.

This is true, however, under the assumption of COSHEP, since in that case (as above) anafunctors represent maps in $\mathrm{Ho}(\mathrm{Cat})$, which is locally small by general model category theory. More specifically, under COSHEP every anafunctor $C\leftarrow F\to D$ is equivalent to one where the set of objects of $F$ is $C_0\prime$, where $C_0\prime \to C_0$ is a projective cover of the set $C_0$ of objects of $C$.

COSHEP is actually stronger than necessary for this; all that is really needed is that for any set $X$, the full subcategory of $\mathrm{Set}/X$ consisting of surjections has a weakly initial set. In that case, any anafunctor $C\leftarrow F\to D$ is equivalent to one where the set of objects of $F$, equipped with its surjection to $C_0$, belongs to the weakly initial set. Note that COSHEP implies that this category has a weakly initial object, namely a projective cover of $X$, while AC implies that $1_X$ is a weakly initial object; thus this assertion can be regarded as saying that choice is only violated in a “small number of ways.” It also follows from the assertion that the free exact completion of $\mathrm{Set}$ is well-powered, which in turn follows from assertion that $\mathrm{Set}$ has a generic proof; both of these can also be regarded as saying that choice is only violated “at a small level.”

In Makkai’s paper referenced below, he proves that $\mathrm{Ana}(C,D)$ is small under the assumption of what he calls the small cardinality selection axiom, which in turn follows from Blass’ axiom of small violations of choice. It is not obvious, however, what the structural counterparts of these axioms might be, or whether they are related to the axioms mentioned above. They carry the same feel that “choice is violated only in a small way,” but the proof presented there is an “injective” approach, in that the set of possibilities for the objects of $F$ is constructed mainly from $D$, rather than purely from $C$ as in the “projective” approach above using COSHEP or its relatives.

Generalizations

Higher versions

Since the folk model structure on $\mathrm{Cat}$ extends to $\omega$-categories, also the anafunctor concept generalizes to these strict higher categories. Indeed, again by Brown-Golasinski, strict $\omega$-groupoids are fibrant with respect to the folk model structure, so that the corresponding $\omega$-schreiber:omega-anafunctors|anafunctors between $\omega$-groupoids represent cocycles in nonabelian cohomology.

More details on $\omega$-anafunctors are described in the context of Differential Nonabelian Cohomology in the private area of the $n$Lab. See omega-anafunctor.

Additive version

The notion of abelian butterfly introduced by Behrang Noohi Weak maps of 2-groups is the additive version of the notion of (saturated) anafunctor: the equivalence between, on the one hand, internal groupoids and internal functors and, on the other hand, arrows and commutative squares in an abelian category extends to an equivalence between saturated anafunctors and butterflies.

Urs says: Why do you restrict this to the abelian case? From page 16 of Noohi’s article I got the impression that he is precisely describing the ana-2-functors between one-object 2-groupoids in terms of the corresponding (possibly nonabelian) crossed modules.

Mathieu says: I don’t see that (or something like that) on that page, but saturated anafunctors should correspond to butterflies also in the semi-abelian case (using the notion of internal crossed module in a semi-abelian category introduced by Janelidze), but I have not checked it. The special case of groups is probably easy to check: saturated anafunctors between two internal groupoids in the category of groups should correspond to butterflies between the corresponding crossed modules.

Urs says: I haven’t checked the details. But he is looking at derived homs of crossed complexes. By general nonsense these derived hom should be given by homs out of cofibrant replacements. This is another way of talking about the anafunctor picture. Somebody should check the details.

Tim: Noohi has pointed out to me a slip in his HHA article in which he gives an ‘algebraic’ description of weak map (and thus of anafunctor) between the crossed modules corresponding to the 2-groups. He has posted a corrected version on the archive (http://arxiv.org/abs/math/0506313v3, but make sure you get version 3).

References

The term “anafunctor” was intrroduced by Michael Makkai in

• Makkai, Avoiding the axiom of choice in general category theory

The popularity of the term was notably pushed by Toby Bartels, who considered internalizations of Makkai’s definition in

• Toby Bartels, Higher Gauge Theory I: 2-Bundles (arXiv:math.CT/0410328)

A development and exposition of the general setup taking Makkai’s and Bartels’ motivations and the theory of homotopical categories into account is

• David Roberts, Internal categories and anafunctors (PhD thesis, chapter I) (pdf)

Since anafunctors are a special case of a more general concept, they, or the general theory applying to them, has been considered under different terms elsewhere.

The general question of model category structures on categories of internal categories is discussed in

• T. Everaert, R.W. Kieboom and T. Van der Linden , Model structures for homotopy of internal categories TAC, Vol. 15, CT2004, No. 3, pp 66-94. (web (pdf))

Closely related, still a bit more general, are the considerations in

• Jardine, Cocycle categories K-theory 0782 (web) (pdf)

Discussion

The following discussion was about the effect of different notions of coverage on the definition of and operations on anafunctors.

David Roberts says: If one uses a coverage, then composing anafunctors means a choice has to be made in the filler of $U\to D_0\leftarrow V$ with the right map a cover. Presumably the resulting bicategory of anafunctors is independent, up to biequivalence, of the choices made. Also, at the very least the identity map has to be a cover, so as to define the identity anafunctor.

DR says: Well I suppose we could follow Makkai’s philosophy twice and have a composition anafunctor (in the original sense) for composing anafunctors (in the internal sense) and end up with an anabicategory.

Mike: Yes, presumably it won’t depend on the fillers chosen; I haven’t checked the details, though. “Grothendieck coverage” means the same as “Grothendieck topology” and thus includes closure under lots of things, including composition and containing identities.

David R: I noticed the adjective Grothendieck in the preceeding sentence half-way through asking the question, but I think my point still holds for general coverages, without the closure properties.

Mike: Well, as you pointed out, you need at least identity maps to be covers to have identity anafunctors, and you need covers to be stable under composition, as well as pullback, in order to define composition of anafunctors. An arbitrary coverage might not satisfy those, although pretty much any coverage arising in practice does. The other point that a choice has to be made unless you have honest pullback-stability is certainly true. So probably the most natural-feeling context in which to work is a (possibly singleton) Grothendieck pretopology. I would be happy for this page to ignore the case where covers don’t have pullbacks; I did some rewriting above to reflect this discussion. I think this discussion could now be deleted; feel free to do so if you agree.

David R: After some thought, one could do without the identity anafunctor, and be satisfied with a anafunctor (of the external variety) giving the identity: $1\to \mathrm{Ana}(X,X)$. I think I should move this discussion to a section of its own, and develop these ideas there. As an aside, I think I saw an example of a non-Grothendieck coverage in John and Alex’s smooth spaces paper.

Toby: You only get an anabicategory anyway, because of the choice of pullbacks (unless the structure of the coverage fixes these, as can be done in $\mathrm{Set}$).

Anafunctors really should make sense in any site whatsoever (as long as we can compose ananatural transformations, which I guess we can if the site is subcanonical). The trick of getting away with single maps (as one can do, for example, in a superextensive site) is not really necessary. In fact, using a coverage makes the definitions, while more complicated, really look more natural in topological categories.