Classically, we can explicitly construct the free Abelian group $\newcommand{\Z}{\mathbb{Z}}\Z[X]$ on a set $X$ as the set of finitely-supported functions $X \to \Z$, and so easily see that the unit map $X \to \Z[X]$ (inclusion of generators) is injective.


Constructively, this construction of $\Z[X]$ doesn’t work for arbitrary $X$. The unit map $X \to \Z[X]$ should send $x \in X$ to the function $1\_x : X \to \Z$, sending $y \in X$ to $1$ if $y = x$ and $0$ otherwise; but this definition-by-cases requires that $X$ has decidable equality (i.e. for every $x,y \in X$, either $y = x$ or $y \neq x$).


Similarly, most other classical explicit constructions of $\Z[X]$ rely at some point on decidable equality of $X$. The abstract-nonsense syntactic construction of $\Z[X]$ as a free model of an algebraic theory works fine constructively; but from this construction, it’s not clear that the unit map $X \to \Z[X]$ is injective.


**Is there some constructive proof that the unit map $X \to \Z[X]$ is injective for arbitrary $X$, or can it fail?**


[Note this is a self-answered question. It came up since the fact was required [here](https://mathoverflow.net/a/272617/2273); asking several experts, the answer seems to be not well-known. After a couple of days, I worked out an answer via an explicit construction, and then also got a reply pointing to a slightly less explicit answer in the literature; so I’m writing it up here to make the answer and construction more prominently available.]



Constructively, is the unit of the “free abelian group” monad on sets injective?
I'd like to present a more modular proof. The key lemma (which I learnt from Christian Sattler) is that any set $X$ is a filtered colimit of finite sets. Indeed, let $I$ be the category of pairs $(n, f)$ with $n \in \mathbb N$ and $f : [n] \to X$, where a morphism $(n, f) \to (m, g)$ is a function $p : [n] \to [m]$ such that $f = g \circ p$. Since the category of finite sets has finite colimits, so does $I$, and so in particular $I$ is filtered. Now $X$ is the colimit $\mathop{\mathrm{colim}}\_{(n,f) \in I} [n]$ in the obvious way.


The free abelian group functor $F$ commutes with colimits, being a left adjoint, so $FX \cong \mathop{\mathrm{colim}}\_{(n,f) \in I} F[n]$. Moreover, the functor $U$ sending an abelian group to its underlying set commutes with *filtered* colimits, so $UFX \cong \mathop{\mathrm{colim}}\_{(n,f) \in I} UF[n]$.


The unit maps $[n] \to UF[n]$ are injective since $[n]$ has decidable equality. Filtered colimits commute with pullbacks in sets, so they preserve monomorphisms. This means precisely that the unit map $X \to UFX$ is also injective, as needed.


If we look more closely at the characterisation of equality in a sequential colimit of sets, we obtain an explicit description of $UFX$ as in previous answers.


