---
title: Free Constructions and Free–Forgetful Adjunctions
module: Adjunctions
moduleNumber: 5
lessonNumber: 4
order: 504
summary: >
  Free monoids, free groups, and free vector spaces are left adjoints to
  forgetful functors, and the universal mapping property is all one needs to
  prove it. Some forgetful functors also have right adjoints (co-free
  constructions like the indiscrete topology), producing three-functor chains.
  Contravariant adjunctions, symmetric in their two functors, close the lesson
  with the pattern behind duality and representation theorems.
topics: [Adjunctions]
sources:
  - book: Simmons
    ref: "Ch. 5 §5.5 Free and co-free constructions; §5.2.1–5.2.3 algebraic, set-theoretic, topological examples; §5.6 Contravariant adjunctions"
  - book: Barr & Wells
    ref: "Ch. 13 §13.1 Free monoids"
draft: false
---

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 \dashv U \dashv 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

$$
X^\ast = \{\, \langle x_1 \cdots x_n \rangle : n \ge 0,\; x_i \in X \,\}
$$

to be the set of finite strings (words) over $X$, with concatenation as
multiplication and the empty string $\langle\rangle$ as identity. This is the
**Kleene closure** of $X$, and $F(X) = (X^\ast, \cdot, \langle\rangle)$ is the
**free monoid** on $X$. The insertion of generators
$\eta_X \colon X \to X^\ast = UF(X)$ sends $x$ to the one-letter string
$\langle x \rangle$.[^bw-monoid-def]

> **Proposition (Universal mapping property of the free monoid).** Let $X$ be a
> set. For every monoid $M$ and every function $u \colon X \to U(M)$, there is a
> unique monoid homomorphism $g \colon F(X) \to M$ with
> $u = U(g) \circ \eta_X$.

> **Proof.** Any homomorphism agreeing with $u$ on one-letter strings is forced
> everywhere, since a homomorphism preserves products and the identity:
>
> $$
> g(\langle\rangle) = 1_M,
> \qquad
> g(\langle x \rangle) = u(x),
> \qquad
> g(\langle x_1 \cdots x_n \rangle) = u(x_1) \cdot \dots \cdot u(x_n).
> $$
>
> Conversely these formulas _define_ a homomorphism: concatenation of strings maps
> to the product of the corresponding products, by associativity in $M$.
> Uniqueness and existence both read off.[^bw-monoid-prop] $\blacksquare$
$$
% caption: The universal property of the free monoid: a function $u$ on
% generators factors uniquely through the insertion of generators as a monoid
% homomorphism $g$ out of $F(X)$.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{4A6FA5}
  \node (X)   at (0,0)      {$X$};
  \node (UFX) at (3.6,0)    {$UF(X)$};
  \node (UM)  at (3.6,-2.3) {$U(M)$};
  \node (FX)  at (7.4,0)    {$F(X)$};
  \node (M)   at (7.4,-2.3) {$M$};
  \draw[->, acc, thick] (X) -- (UFX) node[midway, above] {$u_X$};
  \draw[->, thick] (X) -- (UM) node[midway, below left] {$u$};
  \draw[->, black, dashed, thick] (UFX) -- (UM) node[midway, right] {$U(g)$};
  \draw[->, black, dashed, thick] (FX) -- (M) node[midway, right] {$g$ unique};
  \node[font=\footnotesize, black, anchor=north] at (3.6,-2.9) {in $\mathbf{Set}$};
  \node[font=\footnotesize, black, anchor=north] at (7.4,-2.9) {in $\mathbf{Mon}$};
\end{tikzpicture}
$$

> **Worked example (Free monoid on two letters).** Let $X = \{a, b\}$ and
> $M = (\mathbb{N}, +, 0)$. A function $u \colon X \to U(M)$ with $u(a) = 1$,
> $u(b) = 3$ extends to the unique homomorphism $g \colon X^\ast \to M$ given by
> $g(\langle x_1 \cdots x_n\rangle) = u(x_1) + \dots + u(x_n)$: for instance
> $g(\langle abba\rangle) = 1 + 3 + 3 + 1 = 8$ and $g(\langle\rangle) = 0$. No other
> homomorphism agrees with $u$ on the one-letter words, since concatenation forces
> the value on every word. Changing the target changes only the arithmetic: into
> the free monoid $\{c, d\}^\ast$ with $u(a) = \langle c\rangle$ and
> $u(b) = \langle dd\rangle$, the same word $\langle abba\rangle$ maps to
> $\langle c\,dd\,dd\,c\rangle$.

By the [universal-arrow theorem](/category-theory/adjunctions/adjunctions-via-universal-arrows),
this family of universal properties (one per set $X$) amounts to the statement
$F \dashv U$ for the forgetful $U \colon \mathbf{Mon} \to \mathbf{Set}$, and it
forces everything else:

- **$F$ is a functor.** For $f \colon X \to Y$, the composite
  $\eta_Y \circ f \colon X \to Y^\ast$ is a function into the underlying set of
  a monoid, so it extends uniquely to $F(f) \colon 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.[^bw-monoid-fun]
- **$\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 \colon 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](/category-theory/universal-properties/universal-properties),
  here an instance of the uniqueness of
  [representations](/category-theory/representables-yoneda/representable-functors)
  of the functor $\mathbf{Set}(X, U(-))$.[^bw-monoid-uniq]

Nothing used strings. The identical argument handles any category of
"sets-with-operations": whenever the underlying-set functor
$U \colon \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.[^bw-free-general]

| Category | Free object on $S$ | Unit inserts | Counit evaluates |
| --- | --- | --- | --- |
| $\mathbf{Mon}$ | words over $S$ | one-letter words | multiply the word out |
| $\mathbf{Grp}$ | reduced words in $S$ and inverses | generators | multiply out |
| $\mathbf{Vect}_k$ | formal $k$-linear combinations | basis vectors | compute the sum |
| $\mathbf{Ab}$ (from $\mathbf{Grp}$) | abelianization $G/[G,G]$ | quotient map | — (counit is iso: a reflection) |
| $\mathbf{Cat}$ (from graphs) | path category | length-one paths | compose the path |

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.[^lein-fields]

## 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.[^simm-inv]

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

$$
\Sigma \;\dashv\; U \;\dashv\; \Pi,
$$

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 \colon X \to U(A)$ extends uniquely to a morphism
  $f^\sharp \colon \Sigma X \to A$ by $f^\sharp(x, 0) = f(x)$ and
  $f^\sharp(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 \colon U(A) \to X$ lifts uniquely to a morphism
  $g^\flat \colon A \to \Pi X$ by $g^\flat(a) = \big(g(a),\, g(a^{\bullet})\big)$
  — 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.

> **Worked example (Involution-algebra transposes).** Let $A = \mathbb{Z}$ with
> involution $n^{\bullet} = -n$ (so $n^{\bullet\bullet} = n$), and $X = \{a, b\}$.
>
> - **Free.** $\Sigma X = X + X = \{(a,0), (b,0), (a,1), (b,1)\}$ with the
>   involution flipping the tag. A function $f \colon X \to U(A)$ with $f(a) = 3$,
>   $f(b) = 5$ lifts to the unique morphism $f^\sharp \colon \Sigma X \to A$ by
>   $f^\sharp(x, 0) = f(x)$ and $f^\sharp(x, 1) = f(x)^{\bullet}$: here
>   $f^\sharp(a, 1) = -3$ and $f^\sharp(b, 1) = -5$. Equivariance forces the
>   tag-$1$ clause.
> - **Co-free.** $\Pi X = X \times X$ with the involution swapping coordinates. A
>   function $g \colon U(A) \to X$, say $g(n) = a$ for $n \ge 0$ and $g(n) = b$ for
>   $n < 0$, lifts to $g^\flat \colon A \to \Pi X$ by
>   $g^\flat(n) = (g(n), g(-n))$: for example $g^\flat(3) = (a, b)$,
>   $g^\flat(0) = (a, a)$, and $g^\flat(-4) = (b, a)$. The pair records $g$ on an
>   element and on its mirror image, the only data a morphism into $\Pi X$ carries.

$$
% caption: The double adjunction for involution algebras: the free functor tags
% two copies of $X$ (involution flips the tag) and the co-free functor pairs two
% copies (involution swaps the pair), with the forgetful functor between them.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, minimum width=22mm, minimum height=11mm] (set) at (0,0) {$\mathbf{Set}$};
  \node[draw, minimum width=22mm, minimum height=11mm] (inv) at (6.4,0) {$\mathbf{Inv}$};
  \draw[->, acc, thick] (set.25) -- (inv.155) node[midway, above] {free: $X + X$, tag swap};
  \draw[->, thick] (inv.180) -- (set.0) node[midway, below=1pt] {$U$ (forget)};
  \draw[->, acc, thick] (set.335) to[bend right=18] node[midway, below] {co-free: ($X$, $X$), pair swap} (inv.205);
\end{tikzpicture}
$$

## Discrete and indiscrete: co-freeness in topology

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

$$
D \;\dashv\; U \;\dashv\; I,
$$

where $D(S)$ is $S$ with the **discrete** topology and $I(S)$ is $S$ with the
**indiscrete** topology.[^simm-top] 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}$.[^simm-pre] Algebra supplies a
chain of the same shape with more content: the inclusion
$U \colon \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}$.[^lein-grpmon]

$$
% caption: Three-functor ladders: the forgetful functor in the middle, its free
% (left) adjoint above and co-free (right) adjoint below, for spaces and for the
% inclusion of groups into monoids.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{4A6FA5}
  % left ladder: Top
  \node (set1) at (0,0)    {$\mathbf{Set}$};
  \node (top)  at (0,2.6)  {$\mathbf{Top}$};
  \draw[->, acc, thick] (-0.55,0.35) -- (-0.55,2.25) node[midway, left] {$D$ discrete};
  \draw[->, thick] (0,2.25) -- (0,0.35) node[midway, right=1pt] {$U$};
  \draw[->, acc, thick] (0.95,0.35) -- (0.95,2.25) node[midway, right] {$I$ indiscrete};
  \node[font=\footnotesize, black] at (0,-0.75) {$D$ adjoint $U$ adjoint $I$};
  % right ladder: Grp/Mon
  \begin{scope}[xshift=7.2cm]
    \node (mon) at (0,0)   {$\mathbf{Mon}$};
    \node (grp) at (0,2.6) {$\mathbf{Grp}$};
    \draw[->, acc, thick] (-0.55,0.35) -- (-0.55,2.25) node[midway, left] {$F$ adjoin inverses};
    \draw[->, thick] (0,2.25) -- (0,0.35) node[midway, right=1pt] {$U$};
    \draw[->, acc, thick] (0.95,0.35) -- (0.95,2.25) node[midway, right] {$R$ invertibles};
    \node[font=\footnotesize, black] at (0,-0.75) {$F$ adjoint $U$ adjoint $R$};
  \end{scope}
\end{tikzpicture}
$$

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 \dashv F_1 \dashv F_2 \dashv F_3 \dashv \cdots$ occur; posets already
supply arbitrarily long ones, and the constant-presheaf functor on a space sits
inside a five-term chain.[^simm-strings]

## Contravariant adjunctions

Every adjunction so far pairs two covariant functors, and the notion is
asymmetric. There is a contravariant variant, and it is
_symmetric_.[^simm-contra]

> **Definition (Contravariant adjunction).** Let
> $\mathcal{A} \xrightarrow{\;S\;} \mathcal{S}$ and
> $\mathcal{S} \xrightarrow{\;T\;} \mathcal{A}$ be contravariant functors. They
> form a **contravariant adjunction** if there is a bijection
>
> $$
> \mathcal{A}(A, T(X)) \;\cong\; \mathcal{S}(X, S(A))
> $$
>
> for all $A \in \mathcal{A}$, $X \in \mathcal{S}$, natural in both variables.

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,

$$
h_A \colon A \to TS(A),
\qquad
\eta_X \colon X \to ST(X),
$$

each pointing from an object toward its double dual.[^simm-contra]

$$
% caption: A contravariant adjunction is symmetric: both transposed hom-sets
% put the plain object on the left, and transposing identities yields two units
% pointing into the double duals, with no counits.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{4A6FA5}
  \node (A)   at (0,1.1)    {$A$};
  \node (TX)  at (3.4,1.1)  {$T(X)$};
  \node (X)   at (0,-1.1)   {$X$};
  \node (SA)  at (3.4,-1.1) {$S(A)$};
  \draw[->, thick] (A) -- (TX) node[midway, above] {$f$};
  \draw[->, acc, thick] (X) -- (SA) node[midway, below] {$f$ transposed};
  \draw[<->, black, dashed] (1.7,0.75) -- (1.7,-0.75);
  \begin{scope}[xshift=7.6cm]
    \node (A2)   at (0,1.1)    {$A$};
    \node (TSA)  at (3.2,1.1)  {$TS(A)$};
    \node (X2)   at (0,-1.1)   {$X$};
    \node (STX)  at (3.2,-1.1) {$ST(X)$};
    \draw[->, acc, thick] (A2) -- (TSA) node[midway, above] {$h_A$};
    \draw[->, acc, thick] (X2) -- (STX) node[midway, below] {unit at $X$};
    \node[font=\footnotesize, black, anchor=west] at (4.0,0) {two units};
  \end{scope}
\end{tikzpicture}
$$

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

$$
S(A) = \mathcal{A}(A, \mathbb{F}),
\qquad
T(X) = \mathcal{S}(X, \mathbb{F}),
$$

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.[^simm-schizo] 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.[^simm-contra]

| Ingredient | Covariant adjunction | Contravariant adjunction |
| --- | --- | --- |
| functors | one left, one right — asymmetric | both contravariant — symmetric |
| bijection | $\mathcal{B}(FA, B) \cong \mathcal{A}(A, GB)$ | $\mathcal{A}(A, TX) \cong \mathcal{S}(X, SA)$ |
| transposed identities | one unit, one counit | two units |
| triangle identities | $\varepsilon F \circ F\eta = 1$, $\;G\varepsilon \circ \eta G = 1$ | $T(h) \circ \eta_T = 1$ and its twin |
| canonical example | free $\dashv$ forgetful | hom into a dualizing object |

The [adjoint functor theorem](/category-theory/adjoints-limits/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](/category-theory/monads-algebras/monads) whose algebras recover the
original category.

[^bw-monoid-def]: **Barr & Wells**, _Category Theory for Computing Science_, §13.1.1 — the free monoid $F(X) = (X^\ast, \cdot, \langle\rangle)$ on a set $X$, the Kleene closure, and the insertion $\eta_X(x) = \langle x \rangle$ of one-letter strings.
[^bw-monoid-prop]: **Barr & Wells**, §13.1, Proposition 13.1.2 — the universal mapping property of the free monoid, with the extension $g(\langle x_1 \cdots x_n \rangle) = u(x_1) \cdots u(x_n)$ constructed explicitly.
[^bw-monoid-fun]: **Barr & Wells**, §13.1.3–13.1.4 — the free monoid assignment extends to a functor using only the universal property, with $\eta$ natural; the uniqueness clause supplies both functor laws.
[^bw-monoid-uniq]: **Barr & Wells**, §13.1 after Proposition 13.1.2 — $\eta_X$ is a universal element of $\mathrm{Hom}(X, U(-))$, so the free monoid is determined up to unique isomorphism.
[^bw-free-general]: **Barr & Wells**, §13.2.3 — for any category of structured sets whose underlying-set functor has a left adjoint $F$, the value $F(S)$ is the free structure on $S$: free groups, free abelian groups, free rings.
[^lein-fields]: **Leinster**, _Basic Category Theory_, §2.1, Examples 2.1.3(e) and Remark 2.1.4 — the forgetful functor from fields has no left adjoint; fields are not an algebraic theory because inversion is not everywhere defined.
[^simm-inv]: **Simmons**, _An Introduction to Category Theory_, §5.2.1 with Exercises 5.4.4–5.4.5 and 5.5.3–5.5.4 — involution algebras; $\Sigma X = X + X$ (tag-flip) free and $\Pi X = X \times X$ (coordinate-swap) co-free over the forgetful functor, with explicit transposes, units, and counits.
[^simm-top]: **Simmons**, §5.1, Exercise 5.1.3 — the forgetful functor $\mathbf{Top} \to \mathbf{Set}$ has distinct left and right adjoints (discrete and indiscrete topologies). Also Leinster, Example 2.1.5.
[^simm-pre]: **Simmons**, §5.1, Exercise 5.1.2 — discrete and indiscrete presets as the left and right adjoints of the forgetful functor $\mathbf{Pre} \to \mathbf{Set}$.
[^lein-grpmon]: **Leinster**, §2.1, Examples 2.1.3(d) — the inclusion $\mathbf{Grp} \hookrightarrow \mathbf{Mon}$ has a left adjoint (formally adjoin inverses; $\mathbb{N} \mapsto \mathbb{Z}$) and a right adjoint (submonoid of invertible elements), making $\mathbf{Grp}$ reflective and coreflective in $\mathbf{Mon}$.
[^simm-strings]: **Simmons**, §1.3 and Ch. 6 (long strings of adjunctions) — arbitrarily long adjoint strings exist already for posets; see also Leinster, Exercise 2.1.17 for the five-term chain around the constant-presheaf functor.
[^simm-contra]: **Simmons**, §5.6, Definition 5.6.1 — contravariant adjunctions, the symmetric bijection, the two units $A \to TS(A)$ and $X \to ST(X)$, and the remark that many representation theorems contain one.
[^simm-schizo]: **Simmons**, §5.6, Exercise 5.6.2 — contravariant adjunctions induced by a schizophrenic (dualizing) object living in both categories, with the bijection given by currying through $\mathbb{F}$ and the units given by evaluation.