Equational proof of two expressions for $\lambda x\,\lambda y\,y$ for functors

64 Views Asked by At

Take as given the operations of a cartesian closed category for $\bf Cat$, which is to say we have category products and projections, and a functor category $C^D$ for any two categories $C,D$, with an evaluation map $\epsilon$ and a curry operation $\lambda$ satisfying the usual laws of a CCC.

Let $\Delta_C^D$ be the diagonal functor $C\to D\to C$, which can be defined as $\lambda\pi_1^{C,D}$. This functor produces constant functors if it is partially evaluated: if $X\in C$ then $\Delta_C^D(X):D\to C$ is the constant functor of $X$.

The question concerns two expressions for the functor corresponding to $x:C\mapsto (y:D\mapsto y)$. On the one hand it is the currying of the second projection functor, $\lambda\pi_2^{C,D}$, and on the other hand it is the constant functor of the identity functor on $D$, $\Delta_{D^D}^C(1_D)$. So it should be a theorem that:

$$\Delta_{D^D}^C(1_D)=(\lambda\pi_1^{D^D,C})(1_D)=\lambda\pi_2^{C,D}$$

Is it possible to prove this identity "equationally", that is, using only the rules of a CCC applied to $\bf Cat$, rather than the tedious approach of just checking that the object, morphism, and natural transformation parts are equal?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, since the internal language of a cartesian closed category at least contains the simply typed lambda calculus with products. This implies that equations that hold in the simply typed lambda calculus with products can be shown to hold in any cartesian closed category using only that structure. If you present all that structure using universal properties, then you can just use equational reasoning.

In this case we have products so we have the equations: $$\begin{align} \langle \pi_1, \pi_2 \rangle & = id \\ \langle f \circ h, g \circ h \rangle & = \langle f,g \rangle \circ h\\ \pi_1 \circ \langle f,g \rangle & = f \\ \pi_2 \circ \langle f,g \rangle & = g \end{align}$$

Define $f \times g \equiv \langle f\circ\pi_1,g\circ\pi_2\rangle$. For cartesian closure, we have: $$\begin{align} \lambda(\varepsilon) & = id \\ \lambda(f \circ (h\times id)) & = \lambda(f)\circ h \\ \varepsilon \circ (\lambda(f)\times id) & = f \end{align}$$ where $\varepsilon : B^A \times A\to B$ is the "application" or "evaluation" morphism, and the counit of the relevant adjunction, and $\lambda : \text{Hom}(A\times B,C) \cong \text{Hom}(A,C^B)$ is the "currying" isomorphism witnessing (half of) the adjunction. (Note that both of these sets of equations arise via the same systematic process.)

The trickiest part is interpreting what the expression $\Delta(1)$ means. Since we're using $\Delta$ as an arrow $D^D \to (D^D)^C$ here we need to produce an arrow $\Gamma \to D^D$ which is what $\lambda(\pi_2)$ is. Next, we need to "apply" $\Delta$ to that which we can do just by composing which gives $\Delta \circ \lambda(\pi_2) : \Gamma \to (D^D)^C$. Now we need to "uncurry", which is $\lambda^{-1}(\Delta\circ\lambda(\pi_2)) : \Gamma\times C \to D^D$. If we set $C$ (or $\Gamma$) to the terminal object, we'd be almost done. Alternatively, we can set $C$ to $\Gamma$ and duplicate it. Either way, we don't have $\lambda^{-1}$ as an operation. Instead, it is definable in terms of $\varepsilon$. In particular, $\lambda^{-1}(f) = \varepsilon \circ (f \times id)$. If we consider duplicating via $\langle id,id \rangle : \Gamma \to \Gamma\times\Gamma$ then we can simplify $\lambda^{-1}(\Delta \circ \lambda(\pi_2))\circ\langle id,id\rangle$ to $\varepsilon \circ \langle \Delta \circ \lambda(\pi_2), id\rangle$.

Your question is then $\varepsilon \circ \langle \Delta \circ \lambda(\pi_2), id\rangle \stackrel{?}{=} \lambda(\pi_2)$ where $\Delta \equiv \lambda(\pi_1)$, and the calculation is: $$\begin{align} \varepsilon\circ\langle\Delta\circ\lambda(\pi_2),id\rangle & = \varepsilon\circ\langle\lambda(\pi_1)\circ\lambda(\pi_2),id\rangle \\ & = \varepsilon\circ\langle\lambda(\pi_1\circ\langle \lambda(\pi_2)\circ\pi_1,\pi_2\rangle),id\rangle \\ & = \varepsilon\circ(\lambda(\pi_1\circ\langle \lambda(\pi_2)\circ\pi_1,\pi_2\rangle)\times id)\circ\langle id,id\rangle \\ & = \pi_1\circ\langle \lambda(\pi_2)\circ\pi_1,\pi_2\rangle\circ\langle id,id\rangle \\ & = \lambda(\pi_2)\circ\pi_1 \circ\langle id,id \rangle \\ & = \lambda(\pi_2)\circ id \\ & = \lambda(\pi_2) \end{align}$$