What are (if any) equivalent forms of AC (The Axiom of Choice) in Category Theory ?


Here's a somewhat trivial one, but it is one that category theorists use all the time:

Let us say that a functor $F : \mathcal{C} \to \mathcal{D}$ is a weak equivalence if it is fully faithful and essentially surjective on objects, and that it is a strong equivalence if there exists a functor $G : \mathcal{D} \to \mathcal{C}$ such that $G F \cong \textrm{id}_{\mathcal{C}}$ and $F G \cong \textrm{id}_\mathcal{D}$.

Proposition. In Zermelo set theory with only bounded separation, the following are equivalent:

  • Every surjection of sets splits.
  • Any weak equivalence between two small categories is a strong equivalence.
  • Any weak equivalence between two small groupoids is a strong equivalence.
  • Any weak equivalence between two small preorders is a strong equivalence.
  • Any weak equivalence between two small setoids is a strong equivalence.

Here, by "small" I mean something internal to the set-theoretic universe in question.

On the other hand, if you're asking for category-theoretic formulations of the axiom of choice inside some category of "sets", then there are several:

  • The usual formulation just says that every epimorphism in $\textbf{Set}$ splits. This generalises easily to any category.
  • In any topos $\mathcal{E}$, one can formulate the axiom schema "every surjection $X \to Y$ splits" in the internal language of $\mathcal{E}$, and this axiom schema is valid if and only if every object is internally projective, in the sense that the functor $(-)^X : \mathcal{E} \to \mathcal{E}$ preserves epimorphisms. This is called the internal axiom of choice.

    The internal axiom of choice holds in $\textbf{Set}$ precisely if the usual axiom of choice holds; this is because $\textbf{Set}$ is a well-pointed topos; but in general the internal axiom of choice is weaker. For example, for any discrete group $G$, the category $\mathbf{B} G$ of all $G$-sets and $G$-equivariant maps is a topos in which the internal axiom of choice holds, but if $G$ is any non-trivial group whatsoever, then there exist epimorphisms in $\mathbf{B} G$ that do not split. (For example, $G \to 1$, where $G$ acts on itself by translation.)

  • 2
    $\begingroup$ Amazing, how similar our two answers are in spirit. $\endgroup$ – Andrej Bauer Jan 21 '13 at 11:58
  • $\begingroup$ Is "weak equivalence" a standard terminology? I bet that topologists use this as "induces a weak equivalence on classifying spaces". $\endgroup$ – Martin Brandenburg Jan 22 '13 at 9:16
  • 2
    $\begingroup$ It is standard terminology when working in choice-free settings, such as when dealing with internal categories in, say, $\textbf{Top}$. It also happens to be the weak equivalences in the folk model structure on the category of categories. $\endgroup$ – Zhen Lin Jan 22 '13 at 9:38
  • $\begingroup$ Nice answer, but what is a "setoid"? $\endgroup$ – Tom Leinster Jan 22 '13 at 17:18
  • $\begingroup$ Ah, maybe I can guess: an equivalence relation, viewed as a groupoid? $\endgroup$ – Tom Leinster Jan 22 '13 at 17:36

The following is equivalent to the axiom of choice:

A full and faithful functor which is essentially surjective on objects is an equivalence

Here by "equivalence" I mean "has an up-to-natural-isomorphism inverse".

But wondering which things are equivalent to the axiom of choice is such a set-theoretic thing to do. It is also interesting to ask whether category theory allows us for a more "algebraic" formulation of the axiom of choice. And indeed, in a topos we can express the axiom of choice in two ways:

  1. Externally: Every epi splits.
  2. Internally: Exponentiation by an object preserves epis.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy