[proofplan] The unit maps $\eta_S: S \to U(F(S))$ produce a comparison function from morphisms $F(S) \to A$ to functions $S \to U(A)$ by applying $U$ and precomposing with $\eta_S$. The universal property of the free object gives the inverse comparison function by sending each function $S \to U(A)$ to its unique extension $F(S) \to A$. We then verify that these bijections are natural in the object $A$ and in the set $S$, using uniqueness of extensions to identify the relevant composites. [/proofplan] [step:Define the hom-set comparison maps from the unit functions] Fix a set $S$ and an object $A \in \mathcal A$. Define the function \begin{align*} \Phi_{S,A}: \mathcal A(F(S), A) &\to \mathbf{Set}(S, U(A)) \\ h &\mapsto U(h) \circ \eta_S. \end{align*} This is well-defined because $h: F(S) \to A$ is a morphism in $\mathcal A$, so $U(h): U(F(S)) \to U(A)$ is a function, and therefore $U(h) \circ \eta_S: S \to U(A)$ is a function. Define also the function \begin{align*} \Psi_{S,A}: \mathbf{Set}(S, U(A)) &\to \mathcal A(F(S), A) \\ f &\mapsto \bar f, \end{align*} where $\bar f: F(S) \to A$ denotes the unique morphism guaranteed by the free object universal property, satisfying \begin{align*} U(\bar f) \circ \eta_S = f. \end{align*} [/step] [step:Use uniqueness of extensions to prove the comparison maps are inverse bijections] Let $f: S \to U(A)$ be a function. By definition of $\Psi_{S,A}$, the morphism $\Psi_{S,A}(f) = \bar f$ satisfies \begin{align*} U(\bar f) \circ \eta_S = f. \end{align*} Hence \begin{align*} \Phi_{S,A}(\Psi_{S,A}(f)) = \Phi_{S,A}(\bar f) = U(\bar f) \circ \eta_S = f. \end{align*} Thus $\Phi_{S,A} \circ \Psi_{S,A} = \operatorname{id}_{\mathbf{Set}(S,U(A))}$. Conversely, let $h: F(S) \to A$ be a morphism in $\mathcal A$. The function $\Phi_{S,A}(h): S \to U(A)$ is \begin{align*} \Phi_{S,A}(h) = U(h) \circ \eta_S. \end{align*} The morphism $\Psi_{S,A}(\Phi_{S,A}(h))$ is, by definition, the unique morphism $g: F(S) \to A$ satisfying \begin{align*} U(g) \circ \eta_S = U(h) \circ \eta_S. \end{align*} But $h$ itself satisfies this same equation. By uniqueness in the free object universal property, \begin{align*} \Psi_{S,A}(\Phi_{S,A}(h)) = h. \end{align*} Therefore $\Psi_{S,A} \circ \Phi_{S,A} = \operatorname{id}_{\mathcal A(F(S),A)}$, so $\Phi_{S,A}$ is a bijection with inverse $\Psi_{S,A}$. [guided] The universal property says two things at once: existence and uniqueness of extensions. Existence gives the map $\Psi_{S,A}$, while uniqueness is what proves that no information is lost when passing between a morphism $F(S) \to A$ and its underlying function on generators. Let $f: S \to U(A)$ be a function. The universal property supplies a unique morphism $\bar f: F(S) \to A$ such that \begin{align*} U(\bar f) \circ \eta_S = f. \end{align*} Therefore applying $\Phi_{S,A}$ after $\Psi_{S,A}$ gives \begin{align*} \Phi_{S,A}(\Psi_{S,A}(f)) = \Phi_{S,A}(\bar f) = U(\bar f) \circ \eta_S = f. \end{align*} So every function is recovered from its unique extension. Now let $h: F(S) \to A$ be a morphism. Its image under $\Phi_{S,A}$ is the function \begin{align*} U(h) \circ \eta_S: S \to U(A). \end{align*} When we apply $\Psi_{S,A}$ to this function, we obtain the unique morphism $g: F(S) \to A$ satisfying \begin{align*} U(g) \circ \eta_S = U(h) \circ \eta_S. \end{align*} The original morphism $h$ satisfies this same equation, because substituting $g=h$ gives exactly the right-hand side. The uniqueness clause in the universal property therefore forces $g=h$. Hence \begin{align*} \Psi_{S,A}(\Phi_{S,A}(h)) = h. \end{align*} Thus $\Phi_{S,A}$ and $\Psi_{S,A}$ are inverse functions, so $\Phi_{S,A}$ is a bijection. [/guided] [/step] [step:Verify naturality in the object of $\mathcal A$] Let $S$ be a set, let $A,B \in \mathcal A$ be objects, and let $k: A \to B$ be a morphism in $\mathcal A$. We must show that the square \begin{align*} \mathcal A(F(S), A) &\xrightarrow{\Phi_{S,A}} \mathbf{Set}(S, U(A)) \\ \mathcal A(F(S), k)\downarrow \hspace{2.7em} & \hspace{2.7em}\downarrow \mathbf{Set}(S, U(k)) \\ \mathcal A(F(S), B) &\xrightarrow{\Phi_{S,B}} \mathbf{Set}(S, U(B)) \end{align*} commutes, where $\mathcal A(F(S), k)$ sends $h: F(S) \to A$ to $k \circ h$, and $\mathbf{Set}(S, U(k))$ sends $f: S \to U(A)$ to $U(k) \circ f$. For any morphism $h: F(S) \to A$, functoriality of $U$ gives \begin{align*} \Phi_{S,B}(k \circ h) &= U(k \circ h) \circ \eta_S \\ &= (U(k) \circ U(h)) \circ \eta_S \\ &= U(k) \circ (U(h) \circ \eta_S) \\ &= U(k) \circ \Phi_{S,A}(h). \end{align*} Therefore the bijection $\Phi_{S,A}$ is natural in $A$. [/step] [step:Verify naturality in the set of generators] Let $\alpha: S \to T$ be a function of sets and let $A \in \mathcal A$ be an object. We must show that the square \begin{align*} \mathcal A(F(T), A) &\xrightarrow{\Phi_{T,A}} \mathbf{Set}(T, U(A)) \\ \mathcal A(F(\alpha), A)\downarrow \hspace{2.7em} & \hspace{2.7em}\downarrow \mathbf{Set}(\alpha, U(A)) \\ \mathcal A(F(S), A) &\xrightarrow{\Phi_{S,A}} \mathbf{Set}(S, U(A)) \end{align*} commutes, where $\mathcal A(F(\alpha), A)$ sends $h: F(T) \to A$ to $h \circ F(\alpha)$, and $\mathbf{Set}(\alpha, U(A))$ sends $f: T \to U(A)$ to $f \circ \alpha$. For any morphism $h: F(T) \to A$, the defining property of $F(\alpha): F(S) \to F(T)$ gives \begin{align*} U(F(\alpha)) \circ \eta_S = \eta_T \circ \alpha. \end{align*} Using functoriality of $U$ and associativity of composition, we compute \begin{align*} \Phi_{S,A}(h \circ F(\alpha)) &= U(h \circ F(\alpha)) \circ \eta_S \\ &= (U(h) \circ U(F(\alpha))) \circ \eta_S \\ &= U(h) \circ (U(F(\alpha)) \circ \eta_S) \\ &= U(h) \circ (\eta_T \circ \alpha) \\ &= (U(h) \circ \eta_T) \circ \alpha \\ &= \Phi_{T,A}(h) \circ \alpha. \end{align*} Therefore the bijection $\Phi_{S,A}$ is natural in $S$. [guided] Naturality in the set variable says that changing the set of generators before extending gives the same result as extending first and then restricting along the function of generators. Let $\alpha: S \to T$ be a function and let $h: F(T) \to A$ be a morphism in $\mathcal A$. The functoriality hypothesis on the free object construction says that $F(\alpha): F(S) \to F(T)$ is chosen so that its underlying function carries the generators of $F(S)$ to the generators of $F(T)$ indexed by $\alpha$. Formally, \begin{align*} U(F(\alpha)) \circ \eta_S = \eta_T \circ \alpha. \end{align*} Now compute the function associated to the composite $h \circ F(\alpha): F(S) \to A$: \begin{align*} \Phi_{S,A}(h \circ F(\alpha)) &= U(h \circ F(\alpha)) \circ \eta_S \\ &= (U(h) \circ U(F(\alpha))) \circ \eta_S \\ &= U(h) \circ (U(F(\alpha)) \circ \eta_S) \\ &= U(h) \circ (\eta_T \circ \alpha) \\ &= (U(h) \circ \eta_T) \circ \alpha \\ &= \Phi_{T,A}(h) \circ \alpha. \end{align*} The second equality uses that $U$ is a functor, the third and fifth use associativity of function composition, and the fourth uses the defining property of $F(\alpha)$. This is precisely the commutativity condition for naturality in the set variable. [/guided] [/step] [step:Conclude that the bijections define the adjunction $F \dashv U$] For every set $S$ and every object $A \in \mathcal A$, the function \begin{align*} \Phi_{S,A}: \mathcal A(F(S), A) &\to \mathbf{Set}(S, U(A)) \\ h &\mapsto U(h) \circ \eta_S \end{align*} is a bijection. The preceding two steps show that these bijections are natural in both variables $S$ and $A$. Hence the family $(\Phi_{S,A})_{S,A}$ is a natural isomorphism \begin{align*} \mathcal A(F(-), -) \cong \mathbf{Set}(-, U(-)). \end{align*} By definition of an adjunction, this proves that $F$ is left adjoint to $U$, written $F \dashv U$. [/step]