Category and the axiom of choice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T08:18:33Z http://mathoverflow.net/feeds/question/119454 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119454/category-and-the-axiom-of-choice Category and the axiom of choice lesli 2013-01-21T10:39:52Z 2013-01-22T09:14:34Z <p>What are (if any) equivalent forms of AC (The Axiom of Choice) in Category Theory ? </p> http://mathoverflow.net/questions/119454/category-and-the-axiom-of-choice/119458#119458 Answer by Andrej Bauer for Category and the axiom of choice Andrej Bauer 2013-01-21T11:21:37Z 2013-01-21T11:21:37Z <p>The following is equivalent to the axiom of choice:</p> <blockquote> <p>A full and faithful functor which is essentially surjective on objects is an equivalence</p> </blockquote> <p>Here by "equivalence" I mean "has an up-to-natural-isomorphism inverse".</p> <p>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:</p> <ol> <li><em>Externally:</em> Every epi splits.</li> <li><em>Internally:</em> Exponentiation by an object preserves epis.</li> </ol> http://mathoverflow.net/questions/119454/category-and-the-axiom-of-choice/119459#119459 Answer by Zhen Lin for Category and the axiom of choice Zhen Lin 2013-01-21T11:22:29Z 2013-01-21T11:22:29Z <p>Here's a somewhat trivial one, but it is one that category theorists use all the time:</p> <blockquote> <p>Let us say that a functor $F : \mathcal{C} \to \mathcal{D}$ is a <strong>weak equivalence</strong> if it is fully faithful and essentially surjective on objects, and that it is a <strong>strong equivalence</strong> if there exists a functor $G : \mathcal{D} \to \mathcal{C}$ such that <code>$G F \cong \textrm{id}_{\mathcal{C}}$ and $F G \cong \textrm{id}_\mathcal{D}$</code>.</p> <p><strong>Proposition.</strong> In Zermelo set theory with only bounded separation, the following are equivalent:</p> <ul> <li>Every surjection of sets splits.</li> <li>Any weak equivalence between two small categories is a strong equivalence.</li> <li>Any weak equivalence between two small groupoids is a strong equivalence.</li> <li>Any weak equivalence between two small preorders is a strong equivalence.</li> <li>Any weak equivalence between two small setoids is a strong equivalence.</li> </ul> <p>Here, by "small" I mean something internal to the set-theoretic universe in question.</p> </blockquote> <p>On the other hand, if you're asking for category-theoretic formulations of the axiom of choice <em>inside</em> some category of "sets", then there are several:</p> <ul> <li>The usual formulation just says that every epimorphism in $\textbf{Set}$ splits. This generalises easily to any category.</li> <li><p>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 <em>internally</em> projective, in the sense that the functor $(-)^X : \mathcal{E} \to \mathcal{E}$ preserves epimorphisms. This is called the <strong>internal axiom of choice</strong>.</p> <p>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.)</p></li> </ul>