Free Constructions and Free–Forgetful Adjunctions

Free monoids, free groups, free vector spaces, and free categories on graphs are all instances of one notion, a left adjoint to a functor that forgets structure. Forgetful functors sometimes have right adjoints as well (co-free constructions), so chains $F⊣U⊣C$ of three functors are common. Contravariant adjunctions, where both functors reverse arrows, make the definition symmetric.

The free monoid

The cleanest free construction is the free monoid, because it can be built with bare hands. Let $X$ be a set. Define

to be the set of finite strings (words) over $X$, with concatenation as multiplication and the empty string $⟨⟩$ as identity. This is the Kleene closure of $X$, and $F(X)=(X^{\ast },\cdot ,⟨⟩)$ is the free monoid on $X$. The insertion of generators ${\eta }_X:X\to X^{\ast }=UF(X)$ sends $x$ to the one-letter string $⟨x⟩$.¹

By the universal-arrow theorem, this family of universal properties (one per set $X$) amounts to the statement $F⊣U$ for the forgetful $U:\mathbf{Mon}\to \mathbf{Set}$, and it forces everything else:

• $F$ is a functor. For $f:X\to Y$, the composite ${\eta }_Y\circ f:X\to Y^{\ast }$ is a function into the underlying set of a monoid, so it extends uniquely to $F(f):F(X)\to F(Y)$ — the homomorphism applying $f$ letterwise. Uniqueness gives $F(g\circ f)=F(g)\circ F(f)$ and $F(1_X)=1_{F(X)}$, because both sides of each equation solve the same factorization problem.³
• $\eta$ is natural. The defining square of $F(f)$ is the naturality square of $\eta$ at $f$.
• $F(X)$ is unique up to unique isomorphism. If $\gamma :X\to U(E)$ also has the universal property, the two universal arrows factor through each other, and uniqueness makes the composites identities — the standard argument for universal objects, here an instance of the uniqueness of representations of the functor $\mathbf{Set}(X,U(-))$.⁴

Nothing used strings. The identical argument handles any category of sets-with-operations: whenever the underlying-set functor $U:\mathcal{C}\to \mathbf{Set}$ has a left adjoint $F$, the object $F(S)$ is the free $\mathcal{C}$-structure on $S$ — free groups, free abelian groups, free rings, free vector spaces, the free category on a graph.⁵

Not every forgetful functor has a left adjoint: the underlying-set functor from fields has none, essentially because $x\mapsto x^{-1}$ is not defined everywhere and fields do not form an algebraic theory.⁶

The involution-algebra double adjunction

Free objects classify maps out of a set; co-free objects classify maps into one. Simmons's involution algebras show both sides in miniature, with every transpose computable.⁷

An involution algebra is a set $A$ with a unary operation $a\mapsto a^{\bullet }$ satisfying $a^{\bullet \bullet }=a$; morphisms are functions with $\phi (a^{\bullet })=\phi (a{)}^{\bullet }$. Write $\mathbf{Inv}$ for the category and $U:\mathbf{Inv}\to \mathbf{Set}$ for the forgetful functor. Then $U$ has adjoints on both sides,

both built from one copy of $X$ on each side of a mirror:

• Free: $\Sigma X=X+X$, the disjoint union of tagged pairs $(x,i)$ with $i\in \{0,1\}$, involution flipping the tag. A function $f:X\to U(A)$ extends uniquely to a morphism $f^{♯}:\Sigma X\to A$ by $f^{♯}(x,0)=f(x)$ and $f^{♯}(x,1)=f(x{)}^{\bullet }$ — the tag records how many times to apply the involution, and equivariance forces the second clause.
• Co-free: $\Pi X=X\times X$, ordered pairs with involution swapping coordinates. A function $g:U(A)\to X$ lifts uniquely to a morphism $g^{♭}:A\to \Pi X$ by $g^{♭}(a)=(g(a),g(a^{\bullet }))$ — the pair records the values of $g$ on an element and its mirror image, the only data a morphism into $\Pi X$ can carry.

The unit of the first adjunction tags each element with $0$; its counit $\Sigma U(A)\to A$ sends $(a,i)$ to $a^{(i)}$ (apply the involution $i$ times). The unit of the second, $A\to \Pi U(A)$, is $a\mapsto (a,a^{\bullet })$; its counit projects a pair onto its first coordinate. Checking the triangle identities on these formulas is a two-line computation each.

Discrete and indiscrete: co-freeness in topology

The same $F⊣U⊣C$ shape appears for spaces. Let $U:\mathbf{Top}\to \mathbf{Set}$ send a space to its set of points. Then

where $D(S)$ is $S$ with the discrete topology and $I(S)$ is $S$ with the indiscrete topology.⁸ Both adjunctions are freeness statements with the quantifiers pointing opposite ways:

• $\mathbf{Top}(D(S),Y)\cong \mathbf{Set}(S,U(Y))$: every function out of a discrete space is continuous, so the discrete topology is the free (finest) way to topologize $S$ — maps out are unconstrained.
• $\mathbf{Top}(X,I(S))\cong \mathbf{Set}(U(X),S)$: every function into an indiscrete space is continuous, so the indiscrete topology is the co-free (coarsest) way — maps in are unconstrained.

The preorder analogue swaps topologies for comparisons: discrete (equality) and indiscrete (everything comparable) presets are the left and right adjoints of the forgetful $\mathbf{Pre}\to \mathbf{Set}$.⁹ Algebra supplies a chain of the same shape with more content: the inclusion $U:\mathbf{Grp}\hookrightarrow \mathbf{Mon}$ has left adjoint $F$ (adjoin inverses formally; $F$ of the additive monoid $\mathbb{N}$ is $\mathbb{Z}$) and right adjoint $R$ (the submonoid of invertible elements), so $\mathbf{Grp}$ is both a reflective and a coreflective subcategory of $\mathbf{Mon}$.¹⁰

A functor may have a left adjoint and no right adjoint (free monoid), a right and no left (rare for forgetful functors of algebras, routine elsewhere), or both. Longer strings $\cdots ⊣F_1⊣F_2⊣F_3⊣\cdots$ occur; posets already supply arbitrarily long ones, and the constant-presheaf functor on a space sits inside a five-term chain.¹¹

Contravariant adjunctions

Every adjunction so far pairs two covariant functors, and the notion is asymmetric. There is a contravariant variant, and it is symmetric.¹²

Both hom-sets now have the plain object in the left slot and a functor image in the right slot, so the two functors play interchangeable roles — each is adjoint on the right to the other. Rewriting one category as its opposite turns this into an ordinary adjunction, but the symmetric form is how the examples actually arrive. Transposing identities now produces two units and no counits,

each pointing from an object toward its double dual.¹²

The standard source of contravariant adjunctions is a dualizing object: a single structure $\mathbb{F}$ that lives compatibly in both categories (Simmons calls it schizophrenic). Homming into it gives two contravariant functors

each hom-set enriched with the other category's structure, and the adjunction bijection is currying: a map $A\to T(X)$ and a map $X\to S(A)$ are both functions $A\times X\to \mathbb{F}$ with the variables read in different orders.¹³ The units $A\to TS(A)$ are evaluation maps, and asking when they are isomorphisms is asking for a duality theorem. Vector-space double duality ($\mathbb{F}=k$), Stone duality ($\mathbb{F}$ = the two-element set as both Boolean algebra and space), and Pontryagin duality (the circle) all fit this frame; many representation theorems contain a contravariant adjunction whose units are isomorphisms.¹²

The adjoint functor theorem gives conditions for the initial objects that build free constructions to exist. The composite $U\circ F$, the underlying set of the free structure, carries a monad whose algebras recover the original category.