module Cat.Diagram.Exponential
{o β} (C : Precategory o β) (fp : has-products C) (term : Terminal C) where

# Exponential objectsπ

In a category $\mathcal{C}$ with all finite products (including a terminal object!), where by the usual internal logic dictionary we regard a morphism $f : \Gamma \to A$ as an $A$-term in context $\Gamma$, the notion of exponential object captures what it means for an object to interpret function types. An exponential object for $A$ and $B$ is an object $B^A$ equipped with an evaluation map

$\mathrm{ev} : B^A \times A \to B$

standing for the essence of function application: if I have a function $f : A \to B$, and I have an $x : A$, then application gives me an $f(x) : A$.

Moreover, exponential objects must satisfy a universal property relative to the product functor: if I have a derivation $m : \Gamma \times A \to B$, of a $B$-term in a context extended by $A$, then I should be able to form the βabstractionβ $\lambda m : \Gamma \to B^A$.

record is-exponential (B^A : Ob) (ev : Hom (B^A ββ A) B) : Type (o β β) where
no-eta-equality
field
Ζ        : β {Ξ} (m : Hom (Ξ ββ A) B) β Hom Ξ B^A
commutes : β {Ξ} (m : Hom (Ξ ββ A) B) β ev β Ζ m ββ id β‘ m
unique   : β {Ξ} {m : Hom (Ξ ββ _) _} m'
β ev β m' ββ id β‘ m
β m' β‘ Ζ m

The data above is an unpacked way of saying that the evaluation map extends to an equivalence between $\mathbf{Hom}(\Gamma, B^A)$ and $\mathbf{Hom}(\Gamma \times A, B)$: since being an equivalence is a proposition, once we have fixed the evaluation map, having abstractions is a property, not extra structure.

unlambda : β {C} (m : Hom C B^A) β Hom (C ββ A) B
unlambda m = ev β m ββ id

lambda-is-equiv : β {C} β is-equiv (Ζ {C})
lambda-is-equiv = is-isoβis-equiv Ξ» where
.is-iso.inv    β unlambda
.is-iso.rinv x β sym (unique x refl)
.is-iso.linv x β commutes x

As an aside, let us remark that the evaluation map $B^A \times A \to B$ is sufficient to interpret the more familiar formation rule for function application,

$\frac{\Gamma \vdash f : B^A\quad \Gamma \vdash x : A} {\Gamma \vdash f(x) : B}$

by relativising to an arbitrary context $\Gamma$ through composition, and that this indeed interprets the $\beta$-reduction rule:

private
app : β {Ξ} (f : Hom Ξ B^A) (x : Hom Ξ A) β Hom Ξ B
app f x = ev β f ββ id β β¨ id , x β©

beta : β {Ξ} (f : Hom (Ξ ββ A) B) (x : Hom Ξ A)
β app (Ζ f) x β‘ f β β¨ id , x β©
beta f x = pulll (commutes _)

Putting this data together, we can define an exponential object to be a pair $(B^A, \mathrm{ev})$, with a witness that $\mathrm{ev}$ supports abstraction.

record Exponential (A B : Ob) : Type (o β β) where
no-eta-equality
field
B^A        : Ob
ev         : Hom (B^A ββ A) B
has-is-exp : is-exponential B^A ev
open is-exponential has-is-exp public

Since a finite-products category is called Cartesian monoidal, a finite-products category where every pair of objects has an exponential is called Cartesian closed, and we abbreviate the phrase βCartesian closed categoryβ to βCCCβ.

record Cartesian-closed : Type (o β β) where
no-eta-equality

field has-exp : β A B β Exponential A B

module _ {A} {B} where open Exponential (has-exp A B) hiding (B^A) public
module Exp A B = Exponential (has-exp A B)

The connection between Cartesian closed categories and the lambda calculus is fundamental: however, it would take us too far afield of the basic properties of CCCs to discuss that in this module. You can find extended discussion, and an implementation, in the page on simply typed lambda calculus.

## Functorialityπ

In a Cartesian closed category, we can think of the exponential-assigning operation $(A,B) \mapsto B^A$ as an internalised analogue of the $\mathbf{Hom}$-functor. In the same way that a pair of morphisms $B \to B'$ and $A \to A'$ would act on the ordinary $\mathbf{Hom}$ sets by composition, they act on internal homs, too, defining a mapping $B^A \to B'^{A'}$.

[-,-]β : β {a a' b b'} β Hom b b' β Hom a' a β Hom (Exp.B^A a b) (Exp.B^A a' b')
[-,-]β f g = Ζ (f β ev β β¨ Οβ , g β Οβ β©)

[-,-] : Functor (C ^op ΓαΆ C) C
[-,-] .Fβ (A , B) = Exp.B^A A B
[-,-] .Fβ (f , g) = [-,-]β g f

Through some calculations that are just annoying enough to stun the unsuspecting reader, we can show that this is indeed a functor $\mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathcal{C}$. With a bit more effort, we can show that our defining equivalence between the $\mathbf{Hom}$-sets $\Gamma \times A \to B$ and $\Gamma \to B^A$ satisfies the naturality condition required to to characterise $-^A$ as the right adjoint to $- \times A$.

[-,-] .F-id =
Ζ (id β ev β β¨ Οβ , id β Οβ β©) β‘
Ζ (ev β id ββ id)              β‘Λ
id                             β
[-,-] .F-β (f , g) (f' , g') = sym $unique _$
ev β β¨ (Ζ (g β ev β β¨ Οβ , f β Οβ β©) β Ζ (g' β ev β β¨ Οβ , f' β Οβ β©)) β Οβ , id β Οβ β©
ev β Ζ (g β ev β β¨ Οβ , f β Οβ β©) ββ id β Ζ (g' β ev β β¨ Οβ , f' β Οβ β©) ββ id          β‘
(g β ev β β¨ Οβ , f β Οβ β©) β Ζ (g' β ev β β¨ Οβ , f' β Οβ β©) ββ id
g β ev β Ζ (g' β ev β β¨ Οβ , f' β Οβ β©) ββ id β id ββ f
g β (g' β ev β β¨ Οβ , f' β Οβ β©) β id ββ f
(g β g') β ev β β¨ Οβ , (f' β f) β Οβ β©                                                  β

productβ£exponential : β {A} β Bifunctor.Left Γ-functor A β£ Bifunctor.Right [-,-] A
productβ£exponential {A} = hom-isoβadjoints Ζ lambda-is-equiv nat where
module _ {a b c d} (g : Hom a b) (h : Hom c d) (x : Hom (d ββ A) a) where
nat : Ζ (g β x β β¨ h β Οβ , id β Οβ β©) β‘ Ζ (g β ev β β¨ Οβ , id β Οβ β©) β Ζ x β h
nat = sym $unique _$
ev β (Ζ (g β ev β β¨ Οβ , id β Οβ β©) β Ζ x β h) ββ id
ev β Ζ (g β ev β β¨ Οβ , id β Οβ β©) ββ id β (Ζ x β h) ββ id  β‘
(g β β ev β β¨ Οβ , id β Οβ β© β) β (Ζ x β h) ββ id
(g β ev) β (Ζ x β h) ββ id
g β ev β Ζ x ββ id β h ββ id
g β x β h ββ id                                             β

## From an adjunctionπ

As a converse to the results above, if each product functor $- \times A$ has a right adjoint $-^A$, then $\mathcal{C}$ is a Cartesian closed category, with the object $B^A$ serving as the exponential. This means that we can prove that a category is Cartesian closed by appealing to general facts about the existence of right adjoints, if any apply.

: (-^_ : Ob β Functor C C)
β (β A β Bifunctor.Left Γ-functor A β£ -^ A)
β Cartesian-closed
open Exponential
open is-exponential

exp : β A B β Exponential A B
exp A B .B^A = Aβ A .Fβ B
exp A B .ev = adj A .counit.Ξ΅ B
exp A B .has-is-exp .Ζ          = L-adjunct (adj A)
exp A B .has-is-exp .commutes m = R-L-adjunct (adj A) m
exp A B .has-is-exp .unique m' x = sym $Equiv.injectiveβ (_ , R-adjunct-is-equiv (adj A)) (R-L-adjunct (adj A) _) x cc : Cartesian-closed cc .Cartesian-closed.has-exp = exp ## Exponentiable objectsπ We refer to an object $B : \mathcal{C}$ as exponentiable if, for every other $A : \mathcal{C}$, the exponential object $A^B$ exists. This means that we have a right adjoint $-^B$ to the functor $- \times B$, by the discussion above. It will, however, be more useful to us to characterise exponentiability of $B$ by a condition on the slice category $C/B$. -^B : Functor C C -^B .Fβ = -^Bβ -^B .Fβ h = Ζ (h β ev) -^B .F-id = ap Ζ (idl ev) β lambda-ev _ -^B .F-β f g = sym$ Exponential.unique (exp _) _
(  apβ _β_ refl (apβ _ββ_ refl (introl refl) β Γ-functor .F-β _ _)
Β·Β· pulll (Exponential.commutes (exp _) _)
Β·Β· extendr (Exponential.commutes (exp _) _))

Recall the constant families functor $\Delta_B : \mathcal{C} \to \mathcal{C}/B$, which sends an object $X$ to the product projection $\pi_2 : X \times B \to B$. Following , we have the following characterisation of exponentiability: In a category with pullbacks, an object $B$ is exponentiable iff. we have a right adjoint functor $\Delta_B \vdash \Pi_B$.

Suppose $B$ is exponentiable. The value $\Pi_B(h)$ on a family $h : A \to B$ is defined to be the pullback

where the map $f^B : A^B \to B^B$, on the right, is the action of $(-)^B$ on $f$. An application of the universal properties at hand shows that we can extend maps $h : X \to Y$ over $B$ to maps $\Pi_B(X) \to \Pi_B(Y)$. The calculation that this is functorial is routine, so we omit it from the page.

exponentiableβproduct
: has-pullbacks C
β Functor (Slice C B) C
exponentiableβproduct pb = f where
f : Functor (Slice C B) C
f .Fβ h = pb {B = top} (-^B .Fβ (h .map)) (Ζ Οβ) .apex
f .Fβ {x} {y} h = pb _ _ .universal (sym p) where abstract
p : Ζ Οβ β !  β‘ -^B .Fβ (y .map) β -^B .Fβ (h .map) β pb {B = top} (-^B .Fβ (x .map)) (Ζ Οβ) .pβ
p = Ζ Οβ β !                                         β‘
Ζ Οβ β pb _ _ .pβ                                β‘Λ
Ζ (x .map β ev) β pb _ _ .pβ                     β‘Λ
Ζ ((y .map β h .map) β ev) β pb _ _ .pβ          β‘
Ζ (y .map β ev) β Ζ (h .map β ev) β pb _ _ .pβ   β

It remains to prove that this functor is actually a right adjoint to the constant-families functor $\Delta_B : \mathcal{C} \to \mathcal{C}/B$ like we had claimed. We start with an elementary observation: given maps $f : A \to B$ and $q : X \to A^B$, asking for

$\lambda (f \circ \mathrm{ev}) \circ q = \lambda(\pi_2) \circ \operatorname{!}$

is equivalent to asking for

$f \circ \lambda^{-1}(q) = \pi_2\text{,}$

which is in turn equivalent to asking that $q$ be a map $\Delta_B(X) \to f$, over $B$.

cohβ : β {X} (f : /-Obj B) (q : Hom X (-^Bβ (f .domain)))
β (Ζ (f .map β ev) β q β‘ Ζ Οβ β !)
β (f .map β app q β‘ Οβ)
cohβ f h = prop-ext!
(Ξ» p β Equiv.injective (_ , lambda-is-equiv _) (sym (Ζ-β (has-is-exp _)) Β·Β· p Β·Β· done))
(Ξ» p β Ζ-β (has-is-exp _) Β·Β· ap Ζ p Β·Β· sym done)

This is the last piece that we need to establish an equivalence between the $\mathbf{Hom}$-sets $\mathbf{Hom}_\mathcal{C}(X, \Pi_B(f))$ and $\mathbf{Hom}_{\mathcal{C}/B}(\Delta_B(X), f)$, and even though it factors through the rather complicated path displayed below, it definitionally sends $h : \mathbf{Hom}_\mathcal{C}(X, \Pi_B(f))$ to

$\lambda^{-1}(p_1\circ h)\text{.}$

Having this very simple computational description will greatly simplify the proof that this meandering equivalence is actually natural β and that naturality is all that stands between us and the adjunction $\Delta_B \dashv \Pi_B$ weβve been chasing.

Hom X (Ξ .β f)

Ξ£ (Hom X (-^B .Fβ (f .domain))) (Ξ» h β Ξ£ (Hom X top) Ξ» h' β Ζ (f .map β ev) β h β‘ Ζ Οβ β h')

Ξ£ (Hom X (-^B .Fβ (f .domain))) (Ξ» h β Ζ (f .map β ev) β h β‘ Ζ Οβ β !)

Ξ£ (Hom (X ββ B) (f .domain)) (Ξ» h β f .map β h β‘ Οβ)
β
Slice C B .Precategory.Hom (b.β X) f
ββ

remβ-Ξ² : β {X} (f : /-Obj B) (h : Hom X (Ξ .β f))
β Equiv.to (remβ f) h .map β‘ app (pb _ _ .pβ β h)
remβ-Ξ² f h = refl

nat : hom-iso-inv-natural {L = constant-family fp} {R = exponentiableβproduct pb} (remβ _ .fst)
nat g h x = ext \$
remβ _ .fst (Ξ .β g β x β h) .map                           β‘
app (pb _ _ .pβ β Ξ .β g β x β h)                           β‘
app (Ζ (g .map β ev β pb _ _ .pβ ββ id) β x β h)
app (Ζ (g .map β ev β pb _ _ .pβ ββ id)) β (x β h) ββ id
(g .map β ev β pb _ _ .pβ ββ id) β (x β h) ββ id
g .map β ev β (pb _ _ .pβ β x) ββ id β h ββ id
g .map β (ev β (pb _ _ .pβ β x) ββ id) β b.β h .map
g .map β remβ _ .fst x .map β b.β h .map                   β

## References

• Johnstone, Peter T. 2002. Sketches of an Elephant: a Topos Theory Compendium. Oxford Logic Guides. New York, NY: Oxford Univ. Press. https://cds.cern.ch/record/592033.