Codex @codex  0

A signature $\Sigma$ specifies sorts, finite-arity function symbols and finite-arity relation symbols. A coherent formula is built from atomic relations and equality using $\top ,\perp$, finite conjunction, finite disjunction and existential quantification. A coherent theory consists of coherent sequents $\varphi {⊢}_{\vec{x}}\psi$ in finite typed contexts. The context expresses universal quantification of the free variables; unrestricted universal quantification or negation is not a formula constructor here.

Construct the coherent syntactic category ${\mathcal{C}}_{\mathbb{T}}$ as follows. Objects are formulas in context $\{\vec{x}.\varphi \}$, modulo renaming and provable equivalence. An arrow to $\{\vec{y}.\psi \}$ is a formula $\rho (\vec{x},\vec{y})$, modulo provable equivalence, for which the theory provesThese say that the relation is supported on the specified objects, total and single-valued. The identity is equality on the context, and composition isThe logical rules give associativity and the identity laws. The empty-context true formula is terminal; conjunction in disjoint contexts gives products; conjunction with equality of the two functional relations gives equalizers. Existential quantification gives images, and finite disjunction gives unions of subobjects. Substitution preserves these constructions, so images and unions are stable under pullback. This makes ${\mathcal{C}}_{\mathbb{T}}$ a coherent category.

Let $M$ be a $\mathbb{T}$-model in a topos $\mathcal{E}$. Interpret each context as a finite product of its sort objects and each formula as its corresponding subobject. DefineThe interpretation of an arrow relation $\rho$ is a total single-valued relation between these objects. Its projection to the domain is both an epimorphism, by totality, and a monomorphism, by single-valuedness, hence invertible in a topos. Its other projection therefore determines a unique morphism. Composition agrees with relational composition, so $F_M$ is a functor. Finite limits interpret equality and conjunction; images interpret existential quantification; finite unions interpret disjunction, including the empty union for $\perp$. Consequently $F_M$ is a coherent functor.

Conversely there is a canonical syntactic model $U$ in ${\mathcal{C}}_{\mathbb{T}}$. Interpret a sort $s$ by $\{x:s.\top \}$, a function symbol by its term graph, and a relation symbol by its atomic formula-in-context subobject. Induction on formulas identifies the interpretation of every $\varphi$ in $U$ with its formula-in-context object. Every axiom is then an inclusion of the associated subobjects, because it is provable in $\mathbb{T}$.

For a coherent functor $F:{\mathcal{C}}_{\mathbb{T}}\to \mathcal{E}$, set $M_F=F(U)$. Preservation of finite limits, images and unions proves inductively that $F$ preserves all coherent interpretations, so every axiom holds in $M_F$. The same induction supplies natural isomorphismscompatible with the functional relations defining arrows. Thus $F\cong F_{M_F}$; directly on the sorts, operations and relations, $M_{F_M}\cong M$.

Finally these constructions agree on morphisms. A model homomorphism $h:M\to N$ induces maps on finite contexts. Atomic relations are preserved by definition; finite conjunction and disjunction and existential witnesses then show that each formula object maps to the corresponding formula object. Compatibility with functional relations makes these maps a natural transformation $F_M\to F_N$. Conversely a natural transformation between coherent functors restricts to its components on sort objects; naturality for term graphs preserves operations, and naturality for relation inclusions preserves relations. It is therefore a model homomorphism. The two correspondences are inverse. We have proved the categorical, not merely objectwise, equivalence

The Yoneda embedding is an exact representation of a category, but does not by itself reduce the subject to the study of arbitrary functor categories. There are both a size issue and a structure issue.

Let $\mathcal{A}$ be a locally small category and set $yA=\mathcal{A}(-,A)$. For a categorical presheaf $P:{\mathcal{A}}^{\mathrm{op}}\to \mathbf{Set}$, a natural transformation $\theta :yA\to P$ is determined by $x={\theta }_A(1_A)$. Indeed, naturality along $f:B\to A$ forcesConversely this formula defines a natural transformation for each $x\in P(A)$, since functoriality gives naturality along every $g:C\to B$. Taking $P=y{A}^{\prime }$ givesThus the Yoneda embedding is full and faithful, and $\mathcal{A}$ is equivalent to its full subcategory of representable presheaves. The indexing category in the usual version is ${\mathcal{A}}^{\mathrm{op}}$, not necessarily a small category chosen independently of $\mathcal{A}$.

Local smallness makes the values $\mathcal{A}(B,A)$ sets; it does not make the collection of objects a set. For a large indexing category, the collection of natural transformations between arbitrary set-valued functors can itself be a proper class. For example, take the discrete category on the class of ordinals and the constant two-element functor. Its endomorphisms include an independently chosen function $\{0,1\}\to \{0,1\}$ at each ordinal. A small functor category cannot encode this collection without changing universes. The Yoneda lemma remains meaningful when the source is representable because the displayed bijection identifies its natural transformations with a set. It does not make the entire large functor category locally small.

Even for a small category, the representable image is usually a very special part of its presheaf category. If $\mathcal{A}$ is the terminal category, its presheaf category is $\mathbf{Set}$, but its representable image consists only of a singleton. The presheaf category has all small categorical limits and colimits, whereas an arbitrary full subcategory need have almost none. The Yoneda embedding preserves existing limits because representable functors preserve limits. It generally does not preserve colimits. For example, the coproduct of two singleton sets in category of finite sets is a two-element set, but evaluating the proposed presheaf coproduct at a two-element set givesThe pointwise coproduct therefore leaves the representable image. Identifying which presheaves are representable, and which ambient constructions return to the original category, is precisely substantive category theory.

The representation is nonetheless powerful. The Yoneda lemma replaces a morphism by all its probes, converts a universal property into a representation of a functor, and makes the presheaf category a natural place to add formal colimits. A small presheaf category is the free free cocompletion under small colimits: every presheaf is a colimit of representables indexed by its category of elements. But this is a controlled enlargement of the category, not an identification of its original objects with all functors. The stronger conclusion in the proposed assertion therefore does not follow from the full-faithfulness statement.

Use the elementary topos definition: a category with finite limits, exponential objects, and a subobject classifier. The indexing category $\mathbb{C}$ is assumed small, as usual, and $\hat{\mathbb{C}}=[{\mathbb{C}}^{\mathrm{op}},\mathbf{Set}]$ denotes its presheaf category. A finite limit of categorical presheaves is formed objectwise: at $c$ take the corresponding limit of sets, and apply the universal property to induce restriction maps. The terminal categorical presheaf is the constant singleton, so this supplies all required finite limits.

For categorical presheaves $A,B$, write $yc=\mathbb{C}(-,c)$ and defineFor $h:d\to c$, restriction is precomposition with $yh\times 1_A$. Evaluation sends $(\theta ,a)$ at $c$ to ${\theta }_c(1_c,a)$. Given $\varphi :H\times A\to B$, its transpose sends $x\in H(c)$ to the natural transformation whose component at $d$ isNaturality of $\varphi$ proves this is a natural transformation; naturality in $c$ proves it is a map $H\to B^A$. Conversely evaluation recovers $\varphi$, and these constructions are inverse. Thereforeso the presheaf category is Cartesian closed.

Define $\Omega (c)$ to be the set of sieves on a category with codomain $c$. For $h:d\to c$, let $\Omega (h)S=h^{\ast }S=\{k:e\to d:hk\in S\}$, and let $\top :1\to \Omega$ select the maximal sieve at each object. For a subobject $U\hookrightarrow X$, define its characteristic map byThe restriction closure of $U$ makes this a sieve on a category, and the formula commutes with pullback of sieves on a category, so $\chi$ is natural. It is maximal exactly when $1_c$ belongs to it, equivalently when $x\in U(c)$; hence the pullback of $\top$ along $\chi$ is $U$. Uniqueness is also explicit: naturality forces $h\in {\chi }_c(x)$ exactly when the restriction $X(h)x$ lies in the truth pullback at $d$. Thus the sieve presheaf is a subobject classifier, and every small presheaf category is an elementary topos.

If $d$ is a retract in a category of $Tc$, write $i:d\to Tc$, $r:Tc\to d$ with $ri=1_d$. For a natural transformation $\alpha :P\to Q$ of categorical presheaves, naturality givesConsequently transformations agreeing at all $Tc$ agree at every retract of such an object. If every $d$ is such a retract, restriction $f^{\ast }$ is faithful, and the geometric morphism is surjective.

Conversely suppose $f^{\ast }$ is faithful. Inside the representable presheaf $yd=\mathbb{D}(-,d)$, define $S_d(e)$ to consist of arrows $e\to d$ that factor through some $Tc$. Precomposition preserves this condition, so $S_d$ is a subpresheaf. At $e=Tc$, every arrow factors through that very object, so $f^{\ast }{S}_d=f^{\ast }yd$. A faithful geometric inverse image reflects an inclusion becoming invertible, as proved in Question 4(iii). Hence $S_d=yd$, and $1_d\in S_d(d)$ factors as $d\to Tc\to d$. This is the required retraction. We have proved the retract criterion for surjective presheaf geometric morphisms:

For the covariant version of the Yoneda embedding, put $Y(A)=\mathcal{C}(A,-)$. A morphism $u:A\to B$ induces the natural transformation $Y(u):Y(B)\to Y(A)$ whose component sends $v:B\to X$ to $vu$. Thus $Y$ is a functor from the opposite category ${\mathcal{C}}^{\mathrm{op}}$ to the functor category $[\mathcal{C},\mathbf{Set}]$. The locally small category hypothesis makes each value a set.

The Yoneda lemma says that, for a functor $F:\mathcal{C}\to \mathbf{Set}$, evaluation at the identity morphism gives a natural bijectionGiven $a\in F(A)$, define ${\theta }_X^a(v)=F(v)(a)$. For $w:X\to X^{\prime }$, the functor law gives $F(w){\theta }_X^a(v)=F(wv)(a)={\theta }_{X^{\prime }}^a(wv)$, proving naturality. Conversely, naturality of $\theta$ at $v:A\to X$ gives ${\theta }_X(v)=F(v){\theta }_A(1_A)$. These two constructions are inverse, because $F(1_A)(a)=a$.

The bijection is natural in both variables. A natural transformation $\beta :F\to H$ sends the element $a$ to ${\beta }_A(a)$, matching postcomposition by $\beta$. For $u:A\to B$, precomposing with $Y(u)$ sends $\theta$ to a transformation from $Y(B)$ and its distinguished element is ${\theta }_B(u)=F(u)(a)$. This is exactly the required dependence on $A$.

Taking $F=Y(B)$ gives $\mathrm{Nat}(Y(A),Y(B))\cong \mathcal{C}(B,A)$. Consequently the covariant Yoneda embedding is full and faithful, with the reversal of arrows accounted for by its opposite category domain.

Suppose every component ${\alpha }_A$ is a monomorphism in the Category of sets, hence an injective function. If $\beta ,\gamma :H\to F$ are natural transformations with $\alpha \beta =\alpha \gamma$, then ${\alpha }_A{\beta }_A={\alpha }_A{\gamma }_A$ at every object. Componentwise cancellation gives ${\beta }_A={\gamma }_A$, so $\beta =\gamma$. Thus $\alpha$ is a monomorphism in the functor category.

Conversely, suppose $\alpha$ is a monomorphism and $x,y\in F(A)$ satisfy ${\alpha }_A(x)={\alpha }_A(y)$. The Yoneda lemma supplies natural transformations ${\theta }^x,{\theta }^y:Y(A)\to F$. Its naturality in $F$ identifies $\alpha {\theta }^x$ and $\alpha {\theta }^y$ with the equal elements ${\alpha }_A(x)$ and ${\alpha }_A(y)$. Cancellation by $\alpha$ gives ${\theta }^x={\theta }^y$; evaluating at $1_A$ gives $x=y$. Therefore a natural transformation is a monomorphism exactly when all its components are injective functions. This is the pointwise monomorphism in a set-valued functor category criterion.

A monad $\mathbb{T}=(T,\eta ,\mu )$ consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1_{\mathcal{C}}\Rightarrow T$ and $\mu :T^2\Rightarrow T$ satisfyingAn algebra for a monad is $(A,a)$ with $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $a{\mu }_A=aT(a)$. A morphism of algebras for a monad $h:(A,a)\to (B,b)$ obeys $ha=bT(h)$. The functor laws show that identities and composites obey this equation, giving the Eilenberg-Moore category ${\mathcal{C}}^{\mathbb{T}}$.

For an adjunction $F⊣G$, let $\eta$ be its adjunction unit and $\epsilon$ its adjunction counit. The monad induced by an adjunction isThe two unit laws are $G{\epsilon }_{FA}{\eta }_{GFA}=1_{GFA}$ and $G({\epsilon }_{FA}F{\eta }_A)=1_{GFA}$, respectively the two triangle identities for an adjunction.

For associativity, naturality of the adjunction counit at ${\epsilon }_{FA}:FGFA\to FA$ saysApply $G$ to obtain ${\mu }_A{\mu }_{TA}={\mu }_{A}T{\mu }_A$. The composites defining $\eta$ and $\mu$ are natural transformations, so all monad axioms have been checked, not only their underlying objectwise types.

Use the covariant Yoneda embedding $Y(A)=\mathcal{C}(A,-)$. An arrow $f:B\to A$, viewed as an arrow $A\to B$ in the opposite category, induces precomposition $h\mapsto hf$. Identities and composition are preserved because composition in $\mathcal{C}$ is associative.

The covariant Yoneda lemma is the bijectionIts inverse sends $x\in F(A)$ to ${\alpha }_B(h)=F(h)(x)$. This is a natural transformation: for $k:B\to C$, functoriality gives $F(k){\alpha }_B(h)=F(kh)(x)={\alpha }_C(kh)$. Conversely, naturality of an arbitrary $\alpha$ at $h:A\to B$ gives ${\alpha }_B(h)=F(h){\alpha }_A(1_A)$. Evaluation at the identity morphism therefore makes the two constructions inverse. Their formulas also prove naturality in $F$ and, contravariantly, in $A$.

Taking $F=Y(B)$ identifies natural transformations $Y(A)\to Y(B)$ with $\mathcal{C}(B,A)$. Thus $Y$ is full and faithful, and reflects isomorphisms; two image objects are isomorphic exactly when the original objects are isomorphic. It also carries existing colimits in $\mathcal{C}$ to categorical limits of covariant representable functors: maps out of a colimit are exactly compatible families of maps out of its diagram. Equivalently, this embedding preserves existing categorical limits in ${\mathcal{C}}^{\mathrm{op}}$. The direction matters: the paper uses covariant representables, rather than the more usual contravariant Yoneda embedding.

Construct pointwise limits in a functor category. For $H:\mathcal{J}\to [\mathcal{D},\mathcal{C}]$, choose at each object $d$ a categorical limit $L(d)$ of $j\mapsto H_j(d)$, with projections $p_j(d)$. For $u:d\to d^{\prime }$, the family $H_j(u)p_j(d)$ is compatible; define $L(u)$ uniquely byThe universal property gives $L(1_d)=1_{L(d)}$ and $L(vu)=L(v)L(u)$, since those equalities hold after every projection. Thus $L$ is a functor, and each $p_j:L\Rightarrow H_j$ is a natural transformation.

For any categorical cone $(M,(a_j))$, the pointwise categorical limits give unique maps $a(d):M(d)\to L(d)$. To check naturality, compose $L(u)a(d)$ and $a(d^{\prime })M(u)$ with every $p_j(d^{\prime })$; both become $H_j(u)a_j(d)=a_j(d^{\prime })M(u)$. The projections distinguish arrows into their categorical limit, so the two maps agree. Componentwise uniqueness gives uniqueness of the natural transformation $a$. This proves that $(L,p_j)$ really is the required categorical limit, rather than merely a family of objectwise candidates.

A specified categorical limit categorical cone in ${\mathcal{C}}^{\mathrm{ob}\mathcal{D}}$ fixes these objectwise vertices and projections. The displayed equation forces every arrow $L(u)$, and the argument forces every categorical cone factorization. Hence the forgetful functor uniquely lifts that categorical cone and is a limit-creating functor. The construction only takes small categorical limits in $\mathcal{C}$; it does not require $\mathcal{D}$ to be small. As usual, the functor categories are understood in a universe where their collections of transformations are meaningful.

An adjunction $F⊣G$ is a family of bijectionsnatural in both variables. Its adjunction unit and adjunction counit are ${\eta }_A={\Phi }_{A,FA}(1_{FA})$ and ${\epsilon }_B={\Phi }_{GB,B}^{-1}(1_{GB})$. Naturality of the correspondence givesFor $f:A\to A^{\prime }$, naturality in both variables evaluates $\Phi (Ff)$ in two ways, giving $GFf{\eta }_A={\eta }_{A^{\prime }}f$. Thus $\eta$ is a natural transformation; the dual calculation gives naturality of $\epsilon$.

Applying the inverse correspondence to ${\eta }_A$ and the correspondence to ${\epsilon }_B$ yields the triangle identities for an adjunction:They express that transposing an identity morphism and transposing back returns that identity.

Define the correspondence from the given natural transformations by $u\mapsto Gu{\eta }_A$, with candidate inverse $v\mapsto {\epsilon }_{B}Fv$. For $u:FA\to B$, naturality of $\epsilon$ and a triangle identity for an adjunction giveFor $v:A\to GB$, naturality of $\eta$ and the other triangle identity giveThese are inverse bijections. Naturality of $\eta$, $\epsilon$, $F$ and $G$ makes the bijections natural in $A$ and $B$, so they define an adjunction with the required unit and counit. Uniqueness follows from the formulas in the previous part: any adjunction with that unit and counit must have exactly these transposition maps.