# Category and the axiom of choice

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.)

• Amazing, how similar our two answers are in spirit. – Andrej Bauer Jan 21 '13 at 11:58
• Is "weak equivalence" a standard terminology? I bet that topologists use this as "induces a weak equivalence on classifying spaces". – Martin Brandenburg Jan 22 '13 at 9:16
• 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. – Zhen Lin Jan 22 '13 at 9:38
• Nice answer, but what is a "setoid"? – Tom Leinster Jan 22 '13 at 17:18
• Ah, maybe I can guess: an equivalence relation, viewed as a groupoid? – 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.