--- title: Hom-Functors and Representables module: Representables and the Yoneda Lemma moduleNumber: 3 lessonNumber: 1 order: 301 summary: > Fixing an object A of a locally small category produces a set-valued functor, the hom-functor A(A,-), that records every map out of A. A functor is representable when it is naturally isomorphic to such a hom-functor. We define the covariant and contravariant hom-functors, collect the standard representables (identity, forgetful, powerset), and read maps as generalized elements of varying shape. topics: [Representables and the Yoneda Lemma] sources: - book: Leinster ref: "Ch. 4 — Representables; §4.1 Definitions and examples" - book: Barr & Wells ref: "Ch. 4 — Diagrams, naturality and sketches; §4.5 The Yoneda Lemma and universal elements" - book: Simmons ref: "Ch. 3 §3.3 Natural transformations; hom-functors" draft: false --- A category records objects by the maps between them, so the natural way to study one object is to collect every map into or out of it. Fix an object $A$ of a category $\mathcal{A}$. For each object $B$ there is a set $\mathcal{A}(A, B)$ of maps $A \to B$, and this assignment is functorial in $B$: a map $g : B \to B'$ turns a map $A \to B$ into a map $A \to B'$ by composition. The resulting functor $\mathcal{A}(A, -) : \mathcal{A} \to \mathbf{Set}$ records how $A$ maps into the rest of the category.[^lein-41] Different objects give different records, and an object whose record matches a given functor $X$ is said to **represent** $X$. Representable functors are the second route to universal properties, after [adjunctions](/category-theory/adjunctions/adjunctions): a representation of $X$ is a single object that captures everything $X$ does. The [Yoneda lemma](/category-theory/representables-yoneda/yoneda-lemma) computes exactly how much information a hom-functor carries. ## The covariant hom-functor Fix a [locally small](/category-theory/foundations/size-and-set-theory) category $\mathcal{A}$ and an object $A \in \mathcal{A}$, so that each class $\mathcal{A}(A, B)$ is a genuine set. Local smallness is what makes the following construction land in $\mathbf{Set}$. > **Definition (Covariant hom-functor).** Let $\mathcal{A}$ be locally small and > $A \in \mathcal{A}$. The functor $H^A = \mathcal{A}(A, -) : \mathcal{A} \to > \mathbf{Set}$ sends each object $B$ to the hom-set $H^A(B) = \mathcal{A}(A, B)$, > and each map $g : B \to B'$ to the function > $$ > H^A(g) = \mathcal{A}(A, g) : \mathcal{A}(A, B) \to \mathcal{A}(A, B'), > \qquad p \longmapsto g \circ p. > $$ The value $H^A(g)$ is **post-composition** with $g$; it is also written $g \circ -$ or $g_\ast$. Functoriality is immediate: $H^A(1_B)$ post-composes with an identity and so is the identity function, and $H^A(g' \circ g)$ post-composes with $g' \circ g$, which by associativity is post-composing with $g$ then with $g'$, i.e. $H^A(g') \circ H^A(g)$. $$ % caption: The covariant hom-functor $H^A$ sends a map $g : B \to C$ downstairs % to post-composition, turning each element $p : A \to B$ of $H^A(B)$ into % $g \circ p$ in $H^A(C)$. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (B) at (0,1.7) {$B$}; \node (C) at (3.4,1.7) {$C$}; \node (HB) at (0,0) {$H^A(B)$}; \node (HC) at (3.4,0) {$H^A(C)$}; \draw[->, thick] (B) -- (C) node[midway, above] {$g$}; \draw[->, thick, acc] (HB) -- (HC) node[midway, below] {$H^A(g)$}; \draw[->, black, dashed] (B) -- (HB) node[midway, left] {$H^A$}; \draw[->, black, dashed] (C) -- (HC) node[midway, right] {$H^A$}; \end{tikzpicture} $$ The name $H^A$ is fixed but many books write it $\mathcal{A}(A, -)$, $h^A$, or $\operatorname{Hom}(A, -)$; all denote the same functor. ## The contravariant hom-functor Fixing the second argument instead of the first gives the dual construction. Now a map $g : B' \to B$ turns a map $B \to A$ into a map $B' \to A$ by **pre-composition**, and pre-composition reverses direction, so the functor is contravariant. > **Definition (Contravariant hom-functor).** Let $\mathcal{A}$ be locally small > and $A \in \mathcal{A}$. The functor $H_A = \mathcal{A}(-, A) : > \mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ sends each object $B$ to > $H_A(B) = \mathcal{A}(B, A)$, and each map $g : B' \to B$ to > $$ > H_A(g) = \mathcal{A}(g, A) : \mathcal{A}(B, A) \to \mathcal{A}(B', A), > \qquad p \longmapsto p \circ g. > $$ The value $H_A(g)$ is also written $g^\ast$ or $- \circ g$. The reversal is essential: a map $B' \to B$ downstairs induces a map $H_A(B) \to H_A(B')$ upstairs, going the other way, exactly as a linear map of vector spaces induces a map of dual spaces in the reverse direction. $$ % caption: The contravariant hom-functor $H_A$ reverses arrows: a map % $g : B \to C$ induces $H_A(g) : H_A(C) \to H_A(B)$ by pre-composition, % $p \mapsto p \circ g$. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (B) at (0,1.7) {$B$}; \node (C) at (3.4,1.7) {$C$}; \node (HB) at (0,0) {$H_A(B)$}; \node (HC) at (3.4,0) {$H_A(C)$}; \draw[->, thick] (B) -- (C) node[midway, above] {$g$}; \draw[<-, thick, acc] (HB) -- (HC) node[midway, below] {$H_A(g)$}; \draw[->, black, dashed] (B) -- (HB) node[midway, left] {$H_A$}; \draw[->, black, dashed] (C) -- (HC) node[midway, right] {$H_A$}; \end{tikzpicture} $$ A functor $\mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ is called a **presheaf** on $\mathcal{A}$; the contravariant hom-functors $H_A$ are the **representable presheaves**, and they are the objects the Yoneda lemma is built around. The two variances are summarized below. | | Covariant | Contravariant | | --- | --- | --- | | Notation | $H^A = \mathcal{A}(A, -)$ | $H_A = \mathcal{A}(-, A)$ | | Type | $\mathcal{A} \to \mathbf{Set}$ | $\mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ | | Value at $B$ | maps $A \to B$ | maps $B \to A$ | | Action on $g$ | post-compose $g \circ -$ | pre-compose $- \circ g$ | | Records | maps _out of_ $A$ | maps _into_ $A$ | > **Worked example (A hom-functor on a chain).** Let $\mathcal{A}$ be the poset > $0 \le 1 \le 2$ as a category, with one arrow $i \to j$ whenever $i \le j$. > Fix $A = 1$ and compute the contravariant hom-functor $H_1 = \mathcal{A}(-, 1)$. > On objects, > $$ > H_1(0) = \mathcal{A}(0, 1) = \{\ast\}, \quad > H_1(1) = \mathcal{A}(1, 1) = \{1_1\}, \quad > H_1(2) = \mathcal{A}(2, 1) = \varnothing, > $$ > since $0 \le 1$ and $1 \le 1$ but $2 \not\le 1$. The only nonidentity arrow > that acts is $g : 0 \to 1$; contravariance sends it to > $H_1(g) : H_1(1) \to H_1(0)$, $p \mapsto p \circ g$, so $1_1 \mapsto g$, the > single element of $H_1(0)$. The presheaf $H_1$ is nonempty exactly on the > objects $\le 1$: a representable presheaf on a poset is the indicator of a > down-set. ## Representability Only set-valued functors can be compared to a hom-functor, and the comparison is [natural isomorphism](/category-theory/foundations/natural-transformations). > **Definition (Representable functor).** A functor $X : \mathcal{A} \to > \mathbf{Set}$ is **representable** if $X \cong H^A$ for some $A \in > \mathcal{A}$. A **representation** of $X$ is a choice of object $A$ together > with a natural isomorphism $H^A \xrightarrow{\ \sim\ } X$. Dually, a presheaf > $X : \mathcal{A}^{\mathrm{op}} \to \mathbf{Set}$ is representable if > $X \cong H_A$ for some $A$. A representation reduces a functor to a single representing object. Most functors into $\mathbf{Set}$ are not representable; the ones that are tend to be the functors that "pick out structure by a single generator." **Standard representables.** The recurring examples share a pattern: the representing object is a free structure on one generator.[^lein-41ex] - **Identity on $\mathbf{Set}$.** A map $1 \to B$ from the one-point set is an element of $B$, so $H^1(B) = \mathbf{Set}(1, B) \cong B$ naturally. The identity functor $1_{\mathbf{Set}}$ is represented by $1$. - **Forgetful $\mathbf{Top} \to \mathbf{Set}$.** A continuous map from the one-point space is a point, so the underlying-set functor is $\mathbf{Top}(1, -) = H^1$. - **Forgetful $\mathbf{Grp} \to \mathbf{Set}$.** For each $g \in G$ there is a unique homomorphism $\mathbb{Z} \to G$ sending $1 \mapsto g$, so the underlying-set functor is $\mathbf{Grp}(\mathbb{Z}, -) = H^{\mathbb{Z}}$, since $\mathbb{Z}$ is the free group on one generator. - **Forgetful $\mathbf{Vect}_k \to \mathbf{Set}$.** A linear map $k \to V$ is determined by the image of $1 \in k$, any vector at all, so $\mathbf{Vect}_k(k, V) \cong U(V)$ and $U = H^k$. - **Powerset $\mathcal{P} : \mathbf{Set}^{\mathrm{op}} \to \mathbf{Set}$.** A subset of $B$ is a map $B \to 2$ into the two-element set, so $\mathcal{P} = H_2$ as a presheaf, with $\mathcal{P}(g)(U) = g^{-1}U$. - **Open sets $\mathcal{O} : \mathbf{Top}^{\mathrm{op}} \to \mathbf{Set}$.** Continuous maps into the Sierpiński space $S$ (two points, one open singleton) correspond to open subsets, so $\mathcal{O} = H_S$. | Functor | Type | Representing object | Generator identity | | --- | --- | --- | --- | | $1_{\mathbf{Set}}$ | $\mathbf{Set} \to \mathbf{Set}$ | $1$ | element $=$ map from $1$ | | $U : \mathbf{Top} \to \mathbf{Set}$ | covariant | $1$ | point $=$ map from $1$ | | $U : \mathbf{Grp} \to \mathbf{Set}$ | covariant | $\mathbb{Z}$ | element $=$ hom from $\mathbb{Z}$ | | $U : \mathbf{Vect}_k \to \mathbf{Set}$ | covariant | $k$ | vector $=$ map from $k$ | | $\mathcal{P} : \mathbf{Set}^{\mathrm{op}} \to \mathbf{Set}$ | presheaf | $2$ | subset $=$ map into $2$ | | $\mathcal{O} : \mathbf{Top}^{\mathrm{op}} \to \mathbf{Set}$ | presheaf | $S$ | open set $=$ map into $S$ | > **Worked example (The forgetful functor on groups is $H^{\mathbb{Z}}$).** A > homomorphism $\mathbb{Z} \to G$ is fixed by the image of the generator $1$, > which may be any element of $G$, so $\mathbf{Grp}(\mathbb{Z}, G) \cong U(G)$ > by $\varphi \mapsto \varphi(1)$. Check the count on $G = \mathbb{Z}/3$: the > homomorphisms $\mathbb{Z} \to \mathbb{Z}/3$ are $n \mapsto 0$, > $n \mapsto n \bmod 3$, and $n \mapsto 2n \bmod 3$ — one for each of the three > elements of $U(\mathbb{Z}/3)$. Naturality holds because a homomorphism > $g : G \to G'$ acts on $\mathbf{Grp}(\mathbb{Z}, G)$ by post-composition, and > $(g \circ \varphi)(1) = g(\varphi(1))$ matches its action $U(g)$ on > underlying sets. So $U \cong H^{\mathbb{Z}}$: the free group $\mathbb{Z}$ on > one generator represents the forgetful functor. ### Representables from adjunctions Each forgetful functor above has a [left adjoint](/category-theory/adjunctions/adjunctions) (the free functor), and a left adjoint forces representability. > **Proposition (Representability from a left adjoint).** Any functor > $G : \mathcal{A} \to \mathbf{Set}$ with a left adjoint $F$ is representable; in > fact $G \cong H^{F(1)}$, where $1$ is the one-point set. > **Proof.** By the adjunction $F \dashv G$ and the isomorphism > $G(A) \cong \mathbf{Set}(1, G(A))$ from the identity example, > $$ > G(A) \cong \mathbf{Set}(1, G(A)) \cong \mathcal{A}(F(1), A) > $$ > naturally in $A$. The composite is a natural isomorphism $G \cong H^{F(1)}$. > More generally, for fixed $A \in \mathcal{A}$ the functor > $\mathcal{A}(A, G(-)) : \mathcal{B} \to \mathbf{Set}$ is representable > whenever $F \dashv G$, since $\mathcal{A}(A, G(B)) \cong \mathcal{B}(F(A), B)$ > naturally. $\square$ For $\mathbf{Top}$ the left adjoint is the discrete-space functor $D$ with $D(1) \cong 1$, recovering $U \cong H^1$; for $\mathbf{Vect}_k$ it is the free-vector-space functor with $F(1) = k$, recovering $U \cong H^k$; for $\mathbf{CRing}$ it is the polynomial-ring functor with $F(1) = \mathbb{Z}[x]$, so the forgetful functor is $H^{\mathbb{Z}[x]}$, matching the fact that ring maps $\mathbb{Z}[x] \to R$ are the same as elements of $R$. ## Generalized elements An object of an abstract category has no elements in any set-theoretic sense, but maps into it play the role of elements once a "shape" is chosen. > **Definition (Generalized element).** A **generalized element** of $A$ is any > map with codomain $A$. A map $S \to A$ is a generalized element of $A$ **of > shape $S$**. The term is only a synonym for "map," but it reorganizes the covariant hom-functor: $H^S = \mathcal{A}(S, -)$ sends each object to its set of generalized elements of shape $S$, and functoriality says a map $A \to B$ transports $S$-shaped elements of $A$ to $S$-shaped elements of $B$. $$ % caption: Maps of different shapes into $A$ are its generalized elements: shape % $1$ gives points, shape $\mathbb{N}$ gives sequences, shape $S^1$ gives loops. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (one) at (0,1.6) {$1$}; \node (nat) at (0,0) {$\mathbb{N}$}; \node (cir) at (0,-1.6) {$S^1$}; \node[draw, acc, thick, circle, minimum size=11mm] (A) at (3.6,0) {$A$}; \draw[->, thick] (one) -- (A) node[midway, above, sloped] {point}; \draw[->, thick] (nat) -- (A) node[midway, above] {sequence}; \draw[->, thick] (cir) -- (A) node[midway, below, sloped] {loop}; \end{tikzpicture} $$ In $\mathbf{Set}$ a shape-$1$ element is an ordinary element and a shape-$\mathbb{N}$ element is a sequence. In $\mathbf{Top}$ the shape-$1$ elements are points and the shape-$S^1$ elements are loops, so a continuous map $A \to B$ carries loops to loops. In algebra, a solution of $x^2 + y^2 = 1$ in a ring $R$ is the same thing as a generalized element of shape $\mathbb{Z}[x, y]/(x^2 + y^2 - 1)$, because a pair $(a, b)$ with $a^2 + b^2 = 1$ is a ring map from that quotient into $R$. Fixing a shape and reading off its generalized elements recovers a functor's values; representability tests whether those values match a hom-functor. ## Assembling the hom-functors The families $\{H^A\}$ and $\{H_A\}$ are not independent: a map between objects induces a map between their hom-functors, so each family is itself functorial. A map $f : A' \to A$ induces a natural transformation $H^f : H^A \to H^{A'}$, whose $B$-component sends $p : A \to B$ to $p \circ f : A' \to B$; note the reversal, $f : A' \to A$ producing $H^A \to H^{A'}$. Dually $f : A \to A'$ induces $H_f : H_A \to H_{A'}$ by $p \mapsto f \circ p$. Packaging these gives four functors, dual in pairs. | Family | Assembled functor | Type | | --- | --- | --- | | $H^A = \mathcal{A}(A, -)$ | $H^\bullet : \mathcal{A}^{\mathrm{op}} \to [\mathcal{A}, \mathbf{Set}]$ | covariant reps, contravariantly assembled | | $H_A = \mathcal{A}(-, A)$ | $H_\bullet : \mathcal{A} \to [\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$ | contravariant reps, covariantly assembled | The functor $H_\bullet : \mathcal{A} \to [\mathcal{A}^{\mathrm{op}}, \mathbf{Set}]$, sending each object $A$ to its representable presheaf $H_A$, is the **Yoneda embedding**. Both packaged functors involve one contravariance that cannot be avoided. A single bifunctor unifies them: $$ \operatorname{Hom}_{\mathcal{A}} : \mathcal{A}^{\mathrm{op}} \times \mathcal{A} \to \mathbf{Set}, \qquad (A, B) \mapsto \mathcal{A}(A, B), $$ acting on a pair $(f, g)$ by $p \mapsto g \circ p \circ f$. Contravariant in the first variable, covariant in the second, it carries the same data as $H^\bullet$ and $H_\bullet$ presented at once. $$ % caption: The two-variable hom-functor acts on $(f, g)$ by $p \mapsto g p f$: % contravariant in the source $A$ (pre-compose $f$), covariant in the target $B$ % (post-compose $g$). \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \node (A) at (0,1.7) {$A$}; \node (B) at (2.6,1.7) {$B$}; \node (Ap) at (0,0) {$A_0$}; \node (Bp) at (2.6,0) {$B_0$}; \draw[->, thick] (Ap) -- (A) node[midway, left] {$f$}; \draw[->, thick] (B) -- (Bp) node[midway, right] {$g$}; \draw[->, thick] (A) -- (B) node[midway, above] {$p$}; \draw[->, acc, thick, dashed] (Ap) -- (Bp) node[midway, below] {$g p f$}; \end{tikzpicture} $$ The reversal in the first argument is what makes $\operatorname{Hom}$ contravariant there: a map $A_0 \to A$ pre-composes to send an element of $\mathcal{A}(A, B)$ to one of $\mathcal{A}(A_0, B)$. This bifunctor also explains the naturality clauses in the definition of adjunction: $F \dashv G$ holds exactly when the functors $\mathcal{B}(F(-), -)$ and $\mathcal{A}(-, G(-))$ from $\mathcal{A}^{\mathrm{op}} \times \mathcal{B}$ to $\mathbf{Set}$ are naturally isomorphic.[^lein-adj] The [Yoneda lemma](/category-theory/representables-yoneda/yoneda-lemma) computes the natural transformations out of a representable presheaf, and its [consequences](/category-theory/representables-yoneda/yoneda-consequences) show that $H_\bullet$ embeds $\mathcal{A}$ faithfully into its presheaf category, so that an object is determined by the maps into it. [^lein-41]: **Leinster**, _Basic Category Theory_, §4.1 — Definitions and examples: the covariant hom-functor $H^A = \mathcal{A}(A, -)$, its action on maps by post-composition, and representability of set-valued functors. [^lein-41ex]: **Leinster**, _Basic Category Theory_, §4.1, Examples 4.1.4–4.1.20 — the identity, forgetful, powerset and open-set functors as representables, each represented by a free structure on one generator. Barr & Wells, §4.5.1 gives the same catalogue with the graph node/arrow functors. [^lein-adj]: **Leinster**, _Basic Category Theory_, §4.1, Definition 4.1.22 and Remark 4.1.24 — the two-variable hom-functor $\operatorname{Hom}_{\mathcal{A}}$, and the reformulation of adjointness as a natural isomorphism of the composite hom-functors $\mathcal{B}(F(-), -) \cong \mathcal{A}(-, G(-))$.