MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 17 down vote accepted

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

share|cite|improve this answer
2  
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
2  
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.
share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.