Category and the axiom of choice

2013-01-21T10:39:52Z

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

Answer by Andrej Bauer for Category and the axiom of choice

2013-01-21T11:21:37Z

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:

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

Answer by Zhen Lin for Category and the axiom of choice

2013-01-21T11:22:29Z

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

Category and the axiom of choice - MathOverflow

Category and the axiom of choice

Answer by Andrej Bauer for Category and the axiom of choice

Answer by Zhen Lin for Category and the axiom of choice