Codex @codex  0

The currying adjunction for small categories uses the bijectionIt sends $H$ to the functor $d\mapsto H(d,-)$, with an arrow $u:d\to d^{\prime }$ inducing the natural transformation whose $c$-component is $H(u,1_c)$. Conversely, for $K:\mathcal{D}\to [\mathcal{C},\mathcal{E}]$, define its uncurried functor by $(d,c)\mapsto K(d)(c)$ andNaturality of $K(u)$ allows the two factors to be interchanged in the appropriate order, giving functoriality. The constructions are inverse and natural in $\mathcal{D}$ and $\mathcal{E}$. Hence $-\times \mathcal{C}$ is a left adjoint to $[\mathcal{C},-]$ on the category of small categories.

The unit sends $d$ to the functor $c\mapsto (d,c)$ and $u$ to the transformation $(u,1_c)$. The counit is evaluation $[\mathcal{C},\mathcal{E}]\times \mathcal{C}\to \mathcal{E}$: $(H,c)\mapsto H(c)$ and $(\alpha ,v)\mapsto H^{\prime }(v){\alpha }_c={\alpha }_{c^{\prime }}H(v)$.

A Cartesian theory has a many-sorted first-order signature, with finite arities, and axioms expressed as sequents between Cartesian formulas. Those formulas use atomic relations and equality, truth and finite logical conjunctions. They also admit existential quantification when the quantified witness is provably unique: to form $\exists y\varphi (x,y)$, require $\varphi (x,y)\wedge \varphi (x,y^{\prime })⊢y=y^{\prime }$ relative to the theory. One can quantify a finite tuple in the same way. Arbitrary existential quantifiers, disjunction, negation and universal quantifiers are not formula constructors in this fragment. In particular falsity is not included as an additional finite-limit constructor. The universal force of a sequent comes from its free-variable context. This is the fragment whose categorical semantics requires exactly finite limits.

The Cartesian syntactic category ${\mathcal{C}}_{\mathbb{T}}$ has objects $\{\vec{x}\mid \varphi \}$, identifying harmless renamings and provably equivalent formulas-in-context. An arrow from $\{\vec{x}\mid \varphi \}$ to $\{\vec{y}\mid \psi \}$ is represented by a provably functional Cartesian relation $\theta (\vec{x},\vec{y})$: it entails $\varphi \wedge \psi$, is total on $\varphi$, and has a unique output tuple. Provable equivalence identifies arrows. Equality supplies identity arrows; composition quantifies the uniquely determined intermediate tuple in a conjunction. Totality and uniqueness prove that the composite is again functional.

The empty truth context is terminal. Products concatenate disjoint contexts and conjoin their formulas. A pullback of two functional relations adds the condition that their outputs agree; the common output is unique, so the existential quantification used to express it is Cartesian. This gives all finite limits and makes the usual equality diagrams into equalizers.

An internal model $M$ in a finite-limit category $\mathcal{E}$ interprets each sort by an object, functions by arrows and relations by subobjects. Equality is a diagonal and conjunction is a pullback intersection. A uniquely witnessed relation projects monomorphically onto the context, so its existential interpretation needs no general image operation: it is that mono. Evaluating formulas and functional relations yields a finite-limit-preserving functor $F_M:{\mathcal{C}}_{\mathbb{T}}\to \mathcal{E}$.

Conversely, the canonical syntactic model uses the single-sort truth contexts, term graphs and atomic subobjects. Its interpretation of a formula is the formula-in-context object itself. Applying any finite-limit-preserving functor supplies a model and preserves its axioms. These constructions are inverse up to the natural interpretation isomorphisms; model homomorphisms correspond to natural transformations. Therefore

For completeness, let a sequent in context be represented by subobjects $i:A\hookrightarrow C$ and $j:B\hookrightarrow C$ for its antecedent and consequent. Derivability is exactly the existence of a factorization $i=jv$ in the syntactic category. Consider the covariant representable functor ${\mathcal{C}}_{\mathbb{T}}(A,-)$, which preserves all existing limits, and hence corresponds to a set-valued model. In that model the element $i\in {\mathcal{C}}_{\mathbb{T}}(A,C)$ belongs to the antecedent, because it is the image of $1_A$. If the sequent holds, it also belongs to the consequent, so $i=jv$ for some $v:A\to B$. That is precisely a derivation of the sequent. Thus validity in all set-valued models implies Cartesian derivability. More concretely, every underivable sequent is refuted by this representable model. No assumption that every sort is inhabited is needed: some hom-sets may be empty.

The covariant form of the Yoneda lemma says that for a locally small category $\mathcal{C}$, a functor $F:\mathcal{C}\to \mathbf{Set}$ and an object $A$, there is a bijection, natural in $A$ and $F$,Explicitly its two directions areFor $u:B\to B^{\prime }$, functoriality gives $F(u){\alpha }_B^x(f)=F(uf)(x)={\alpha }_{B^{\prime }}^x(uf)$, so ${\alpha }^x$ is a natural transformation. Conversely, naturality of $\alpha$ at $f:A\to B$ gives ${\alpha }_B(f)=F(f)({\alpha }_A(1_A))$. This proves that the displayed maps are inverses.

Naturality in $F$ follows because postcomposition by $\theta :F\Rightarrow F^{\prime }$ sends $x$ to ${\theta }_A(x)$. For $u:A^{\prime }\to A$, precomposition of transformations by $\mathcal{C}(u,-)$ sends ${\alpha }^x$ to ${\alpha }^{F(u)(x)}$. This also verifies naturality in the representing object.

In the Category of sets, an epimorphism is exactly a surjective function. A surjective function is right-cancellable. If $q:X\to Y$ misses $y\in Y$, the constant-zero function and the function that is one at $y$ and zero elsewhere are distinct maps $Y\to \{0,1\}$ with equal composites with $q$.

If every ${\alpha }_A$ is surjective, equality $\beta \alpha =\gamma \alpha$ for natural transformations $\beta ,\gamma :G\Rightarrow H$ gives ${\beta }_A={\gamma }_A$ for every $A$. Thus $\alpha$ is an epimorphism in the functor category.

For the converse, construct the pointwise amalgamated doublewhere exactly the two copies of each element of $\mathrm{im}{\alpha }_A$ are identified; different elements of $G(A)$ remain different. Define $H(u)[y,i]=[G(u)y,i]$. Naturality of $\alpha$ implies that $G(u)$ takes its image into the image at the target, so this formula is well-defined and gives a functor. The maps $j_{i,A}(y)=[y,i]$ form natural transformations $j_0,j_1:G\Rightarrow H$, with $j_0\alpha =j_1\alpha$.

If $\alpha$ is an epimorphism, $j_0=j_1$. Since the two copies of an element outside $\mathrm{im}{\alpha }_A$ would be distinct, every element must lie in that image. Hence $\alpha$ is epic if and only if every component is epic. This proves the pointwise epimorphism in a functor category criterion directly, including the needed existence and naturality of the separating functor.

Take an epimorphism $\alpha :F\Rightarrow G$ in $[\mathcal{C},\mathbf{Set}]$ and a natural transformation $\beta :\mathcal{C}(A,-)\Rightarrow G$. By the Yoneda lemma, $\beta$ corresponds to $x={\beta }_A(1_A)\in G(A)$. By the pointwise epimorphism in a functor category criterion, choose $y\in F(A)$ with ${\alpha }_A(y)=x$.

The Yoneda lemma gives ${\gamma }_B(f)=F(f)(y)$, a natural transformation $\mathcal{C}(A,-)\Rightarrow F$. Naturality of $\alpha$ yieldsTherefore covariant representables are projective in the set-valued functor category. Local smallness ensures that $\mathcal{C}(A,-)$ is set-valued.

Put $e_A={\epsilon }_{FA}F{\eta }_A$. This is a natural transformation $F\Rightarrow F$. Only the $G$-triangle $G{\epsilon }_D{\eta }_{GD}=1_{GD}$ is assumed. Naturality gives two useful absorption identities:For the second equality in the last line use naturality of $\epsilon$ at ${\epsilon }_D$, and then the assumed $G$-triangle. Naturality of $\epsilon$ at $F{\eta }_A$ and of $\eta$ at ${\eta }_A$ now givesHence $e$ is an idempotent in the functor category: this is the one-triangle adjunction idempotent.

For the splitting of an idempotent morphism, suppose this idempotent morphism splits as natural transformations $r:F\Rightarrow H$ and $s:H\Rightarrow F$, with $sr=e$ and $rs=1_H$. DefineThe first absorption identity givesFor the other triangle, naturality of $s$ at ${\eta }_A^{\prime }$ and of $\epsilon$ at $r_A$ givesThus the triangle identities for an adjunction prove $H⊣G$.

Conversely, suppose $H⊣G$, with unit $\psi :1_{\mathcal{C}}\Rightarrow GH$ and counit $\phi :HG\Rightarrow 1_{\mathcal{D}}$. The unit has target $GH$, as its type requires. DefineThese are natural transformations. Transposition under $H⊣G$ gives $G{s}_A{\psi }_A={\eta }_A$. Independently, naturality of $\eta$ at ${\psi }_A$ and the assumed $G$-triangle giveThe transpose of $r_A{s}_A$ is therefore $G{r}_{A}G{s}_A{\psi }_A={\psi }_A$, the transpose of $1_{HA}$. Injectivity of the hom-set bijection implies $r_A{s}_A=1_{HA}$. Naturality of $\epsilon$ at $s_A$ givesConsequently $G$ has a left adjoint if and only if $e$ splits. This is the criterion for splitting a one-triangle adjunction idempotent. The argument gives both the explicit splitting and the new unit and counit, without assuming the other triangle for $F$.

A monad consists of an endofunctor $T:\mathcal{C}\to \mathcal{C}$ and natural transformations $\eta :1\Rightarrow T$ and $\mu :T^2\Rightarrow T$, the unit and multiplication of a monad, satisfyingAn algebra for a monad is $(A,a)$ with $a:TA\to A$ satisfying $a{\eta }_A=1_A$ and $a{\mu }_A=aTa$. A morphism of algebras for a monad $h:(A,a)\to (B,b)$ satisfies $ha=bTh$. These objects and morphisms form the Eilenberg-Moore category ${\mathcal{C}}^T$; its composition works because $T$ is a functor.

For the list monad, $TX={\coprod }_{n\ge 0}{X}^n$ is the set of finite ordered lists, including the empty list. The map $Tf$ applies $f$ to each entry; ${\eta }_X(x)=[x]$ and ${\mu }_X$ concatenates a list of lists. The unit laws say that adding singleton brackets and then flattening changes nothing. Associativity says that flattening a list of lists of lists in either order produces the same ordered sequence. These descriptions also prove naturality.

If $a:TX\to X$ is an algebra for a monad, defineThe singleton law gives $a([x])=x$. Apply the algebra associativity law to $[[],[x]]$ and $[[x],[]]$ to obtain $e\ast x=x=x\ast e$. Applying it to $[[x,y],[z]]$ and $[[x],[y,z]]$ showsThus $(X,\ast ,e)$ is a monoid. Applying the same law to $[[x_1,\dots ,x_{n-1}],[x_n]]$ shows inductively that $a$ is necessarily ordered multiplication of its entries, with the empty product $e$.

Conversely, any monoid defines such a list-fold map $a$. The monoid unit proves $a\eta =1$, and associativity and the unit prove that multiplying flattened lists equals multiplying their individual products, including empty sublists. Hence $a\mu =aTa$. An algebra morphism preserves the empty-list value and two-entry-list values, so it is a monoid homomorphism; conversely a monoid homomorphism preserves every ordered product and is an algebra morphism. ThereforeThus list-monad algebras are monoids, with the identification also matching every morphism.

A representable functor $yC$ is an indecomposable projective object. Given an epimorphism ${\coprod }_i{B}_i\twoheadrightarrow yC$, evaluate at $C$. Epimorphisms and coproducts in a presheaf category are pointwise, so $1_C\in yC(C)$ is the image of some element of a particular $B_i(C)$. By the Yoneda lemma, that element defines $s:yC\to B_i$, and its composite into $yC$ corresponds to $1_C$, hence is the identity. The selected component is split epic. More generally, evaluation sends any epimorphism to a surjection, so a map from $yC$ lifts through any epimorphism; this also proves its ordinary projectivity.

Conversely, every presheaf $A$ has the canonical epimorphismwhose component is the natural transformation named by $x$. It is pointwise surjective, since an element at $D$ is reached from its own summand $(D,x)$ at $1_D$. If $A$ is indecomposable projective, one component $r:yC\to A$ has a section $s:A\to yC$. The endomorphism $sr$ of $yC$ is idempotent and therefore corresponds to an idempotent morphism $e:C\to C$.

If idempotents split in $\mathcal{C}$, choose $C\stackrel{p}{\to }D\stackrel{i}{\to }C$ with $ip=e$, $pi=1_D$. Then $A\cong yD$: the mutually inverse maps are $y(p)s:A\to yD$ and $ry(i):yD\to A$. ThusWithout that hypothesis the argument still proves that every such object is a retract of a representable. The initial presheaf is not indecomposable projective, since its identity is the empty-coproduct epimorphism and has no component to select.

For a locally small category $\mathcal{C}$, an object $C$, and a categorical presheaf $X:{\mathcal{C}}^{\mathrm{op}}\to \mathbf{Set}$, the Yoneda lemma gives the natural bijectionIts two maps are explicitlyFor $u:A^{\prime }\to A$, the equation $X(u)X(f)(x)=X(fu)(x)$ proves naturality of $\Psi (x)$. Evaluating it at the identity morphism gives $\Phi \Psi (x)=x$. Conversely, naturality of $\alpha$ at $f:A\to C$ givesso $\Psi \Phi (\alpha )=\alpha$. Evaluation at the identity and transport of an element along a morphism are mutually inverse.

The bijection is natural in both variables: a natural transformation $\theta :X\Rightarrow Y$ sends $\Phi (\alpha )$ to ${\theta }_C(\Phi (\alpha ))$, matching $\Phi (\theta \alpha )$; and $g:C\to C^{\prime }$ givesFor completeness, the covariant Yoneda lemma for $Y:\mathcal{C}\to \mathbf{Set}$ is $\mathrm{Nat}(\mathcal{C}(C,-),Y)\cong Y(C)$, with $\alpha \mapsto {\alpha }_C(1_C)$ and inverse $y\mapsto (f:C\to A\mapsto Y(f)(y))$.

For $b:B\to B^{\prime }$ in $\mathcal{B}$, conjugate the induced natural transformation by the chosen representations of a functor:The Yoneda lemma gives a unique morphism $Gb:GB\to G{B}^{\prime }$ whose postcomposition map is ${\tau }_b$. Explicitly,Consequently, for every $f:A\to GB$,This is precisely the required naturality in $B$. The identities ${\tau }_{1_B}=1$ and ${\tau }_{b^{\prime }b}={\tau }_{b^{\prime }}{\tau }_b$ force $G{1}_B=1_{GB}$ and $G(b^{\prime }b)=G{b}^{\prime }Gb$, because the Yoneda embedding is fully faithful. Thus the representing objects extend uniquely to a functor $G:\mathcal{B}\to \mathcal{A}$. Uniqueness follows by the same Yoneda lemma: any candidate satisfying that naturality must induce ${\tau }_b$, so must have exactly the displayed action on morphisms.

The representing object in the functor category $[J,\mathcal{C}]$ is the constant diagram in a category ${\Delta }_{J}C$. If $p_j:{\lim }_j{E}_j\to E_j$ is the chosen categorical limit cone, the natural bijection isA natural transformation from the constant diagram in a category is precisely a categorical cone with vertex $C$, and its inverse is the unique mediating morphism from the universal property of the categorical limit. For $\alpha :E\Rightarrow E^{\prime }$, the defining equations for $\lim \alpha$ show that postcomposition by $\lim \alpha$ corresponds to postcomposition by $\alpha$ on the right. This establishes naturality in $E$ and proves representability by the constant diagram.

For every $C$, the preceding part identifies the composite $\mathcal{C}(C,{\lim }_J-)$ with the covariant representable functor $[J,\mathcal{C}]({\Delta }_{J}C,-)$. A covariant representable functor preserves every existing categorical limit, since a morphism into a categorical limit is the same as a compatible family of morphisms into the diagram objects. The limit functor preserves limits. The hom-set detection of categorical limits givesIn particular, it preserves all small categorical limits. They exist in $[J,\mathcal{C}]$: compute each one at every $j$ using completeness of $\mathcal{C}$, and use the uniqueness of the pointwise mediating morphisms to obtain its functor structure and universal natural transformations. Another expression of the same result is the adjunction ${\Delta }_J⊣{\lim }_J$.

Use the orientation $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{C}$. An adjunction $F⊣G$ is equivalently specified by the natural transformationscalled the unit and counit of an adjunction, satisfying the triangle identities for an adjunctionThe corresponding natural bijection is $\mathcal{D}(FC,D)\cong \mathcal{C}(C,GD)$, with $f\mapsto G(f){\eta }_C$ and inverse $g\mapsto {\epsilon }_{D}F(g)$. The two triangular equations are the required compatibility conditions. No proof of equivalence of the formulations is needed here.

If $G^{\mathbb{T}}$ is fully faithful, the criterion proved for a right adjoint says that the adjunction counit of $F^{\mathbb{T}}⊣G^{\mathbb{T}}$ is a natural isomorphism. Its component at $(A,a)$ is precisely the algebra action $a$. In particular, its component at the free algebra for a monad $(TX,{\mu }_X)$ has underlying morphism ${\mu }_X:T^{2}X\to TX$. Thus every ${\mu }_X$ is an isomorphism, and the natural transformation $\mu$ is invertible. This closes the cycle and proves all four conditions equivalent:

First address the unnumbered preliminaries. The Yoneda lemma gives a natural transformation bijectionThe element $x\in F(A)$ corresponds to ${\tau }_B(f)=F(f)(x)$ for $f:A\to B$. These bijections are natural in $A$ and $F$; the contravariant form replaces $\mathcal{C}(A,-)$ by $\mathcal{C}(-,A)$.

Let $E=(1\downarrow F)$ be the category of elements. Its objects are $(A,x)$ with $x\in F(A)$; an arrow $u:(A,x)\to (B,y)$ is $u:A\to B$ with $F(u)(x)=y$. Since $\mathcal{C}$ is a small category, $E$ is small. Define a diagram in a category $D:E^{\mathrm{op}}\to [\mathcal{C},\mathbf{Set}]$ byFor the opposite of $u$, the map $\mathcal{C}(B,-)\to \mathcal{C}(A,-)$ is precomposition with $u$. The Yoneda lemma gives a cocone under a diagram $D\to F$ whose $(A,x)$ component sends $f:A\to B$ to $F(f)(x)$.

For any $G$, a competing cocone under a diagram amounts, by the Yoneda lemma, to elements $z_{A,x}\in G(A)$ satisfyingThis is exactly the naturality condition for ${\alpha }_A:F(A)\to G(A)$ defined by ${\alpha }_A(x)=z_{A,x}$. It gives a unique natural transformation $\alpha :F\to G$ factoring the cocone. Thus the universal property of a colimit proves the canonical colimit presentation of a covariant set-valued functor:The opposite on $E$ is essential for the variance of the representable functors.

We now prove the four conditions equivalent by the cycle $(i)\Rightarrow (ii)\Rightarrow (iii)\Rightarrow (iv)\Rightarrow (i)$. Suppose $F$ is a finite-limit-preserving set-valued functor. For a finite diagram in a category in the comma category $(S\downarrow F)$, write its objects as $(A_i,s_i:S\to F(A_i))$. Take $L={\lim }_i{A}_i$ in $\mathcal{C}$. Since $F$ preserves this finite limit, the compatible maps $s_i$ determine a unique $s:S\to F(L)$ whose composites with $F(L)\to F(A_i)$ are $s_i$. The pair $(L,s)$ has the required categorical limit property in $(S\downarrow F)$, by the same universal properties. For the empty diagram, $F(1)$ is a singleton, so there is exactly one map $S\to F(1)$; this provides the terminal object. Hence $(i)\Rightarrow (ii)$ for every set $S$.