Categorical proof subgroups of free groups are free? 
This is a crossport of this question from MSE.

Is there a categorical proof that subgroups of free groups are free?
How about the result that subgroups of free abelian groups are free abelian?
What is it about $\mathsf{Grp}$ and $\mathsf{Ab}$ that makes subobjects of free objects free? Can one characterize such categories? In particular, are there any other ones apart from $\mathsf{Grp}$ and $\mathsf{Ab}$?

I have received some comments on MSE, one claiming such a proof exists, one doubting it, and another claiming it cannot be proved in $ZF$.
 A: Free isn't a very good notion categorically, since it requires reference to an underlying set.  A similar but catgeorically better notion is "projective." An abelian category in which all subobjects of projective modules are projective is called hereditary.  Abelian groups are one such example, but so are representations of a quiver, or coherent sheaves on a smooth 1-dimensional affine variety (coherent sheaves on a 1-d smooth projective variety are morally similar, but don't have many projective objects.  They have the similar property that a subobject of a locally free object is locally free).  This property follows whenever $\operatorname{Ext}^2(M,N)$ vanishes for any objects in the category (you may also need enough projectives, as well.  This is where coherent sheaves on a projective variety runs into trouble).  This theory doesn't apply to free groups, since groups aren't an abelian category.
A: I am not sure what exactly is meant by a categorical proof but here is my best approximation.
If $G$ is a group let $BG$ be the category of right $G$-sets.  It is well known that $G\cong H$ if and only if $BG$ and $BH$ are equivalent categories.
Now if $F_X$ is a free group on $X$ then $BF_X$ is the category whose objects are sets $Y$ together with an $X$-tuple  of permutations of $Y$ where we have permutations act on the right.
Let $H$ be a subgroup of $F_X$.  Choose a Schreier transversal $T$ for $F_X/H$ (this is the non -categorical part). Let $B$ be the set of nonidentity elements of $H$ of the form $txu^{-1}$ with $t\in T$, $x\in X$ and $u\in T$ the representative of $Htx$.
One needs to show that $BH$ is equivalent to the category of sets with a $B$-tuple of permutations. Given an $H$-set $Y$ you get an obvious $B$-tuple by forgetting the action of the other elements of $H$.  To go other way recall that there is a functor $BH\to BF_X$ given by $Y\mapsto Y\otimes_H F_X$. Moreover, using the transversal $T$ it is easy to see that the action of elements of $X$ on this tensor product are determined precisely by the action of $B$ on $Y$.  Thus if you have a $B$-tuple of permutations of $Y$ you can define  an $X$-tuple of permutations of $Y\times F_X/H$ and hence an action of $F_X$ on $Y\times F_X/H$ which restricts on $Y\times \{H\}$ to an action of $H$ extending the original action of $B$. This proves $H$ is free on $B$.  Schreier transversals are needed to recover the original action.  
A nuts and bolts version of this argument without categorical language can be found in http://arxiv.org/abs/1006.3833
A: "Subobjects of free algebras are free" is satisfied comparatively rarely for algebraic theories. I'm going to start a list and people should feel free to add. I'm making it CW. 
Before starting, let me say that IMHO a more interesting general question to consider is: when are retracts of free objects free? That can be a very tough question. We had some discussion here: Is a retract of a free object free? 


*

*Ben Webster got the ball rolling with various categories of modules (although he concentrated more on whether subobjects of projectives are projective). By the way, vector bundles can be seen as projective objects over the ring of smooth functions, but need not be free: some vector bundles are not trivial bundles. 

*Submonoids of free monoids need not be free. This fails for even the simplest cases, e.g., the monoid generated by $2, 3$ in $(\mathbb{N}, +)$ isn't free. 

*Subalgebras of free commutative $k$-algebras (aka polynomial algebras) need not be free. The subalgebra generated by $t^2, t^3$ in $k[t]$ ($k$ a field) can't be a polynomial algebra as it isn't even a UFD. 

*Subalgebras of free Boolean algebras need not be free. For example, a finitely generated free Boolean algebra on $n$ elements has cardinality $2^{2^n}$, isomorphic to a power set of $P([2^n])$. A quotient of the set $2^n$, say one with 3 elements, induces an inclusion $P([3]) \to P([2^n])$ of Boolean algebras. 

*Pablo mentioned that subalgabras of free Lie algebras are free. (What's a good reference for that?) 
A: Let me elaborate on my comment. I think freeness is a red herring. The content of the standard topological proof is that a covering space of a $1$-dimensional CW complex is again a $1$-dimensional CW complex. Of course this naturally generalizes to the case where $1$ is replaced by any positive integer $k$, which suggests the following definition.
Say that a group $G$ has homotopy dimension at most $k$ if $BG$ can be presented by a $k$-dimensional CW complex (e.g. take $BG$ to be a compact hyperbolic $k$-manifold). Then the same argument about covering spaces shows that every subgroup of a group with homotopy dimension at most $k$ again has homotopy dimension at most $k$. Homotopy dimension at most $1$ is equivalent to freeness in the presence of choice, but using it instead of freeness in the argument removes the need to choose a spanning tree and that should address concerns about uses of choice. 
As the long list of examples in Todd's answer also suggests, we should be looking at some property other than freeness in general. I think some kind of cohomological dimension is a better candidate; as stated in Matthias Wendt's comment below, the nontrivial free groups are precisely the groups of cohomological dimension $1$. And $1$-dimensionality also shows up in Ben Webster's answer. 
