I cannot figure out how to prove this lemma, at least partly because I'm still unfamiliar with the concepts and notation involved. Below I will write down my thoughts on how to go about it, and perhaps someone can guide me to connect the dots.
Exercise:
Statement of the lemma:
Discussion:
We want to establish a bijection between $\mathsf{Nat} \big( \mathsf C (-, X), F \big)$ and $FX$. First question: how I do know that $\mathsf{Nat} \big( \mathsf C (-, X), F \big)$ is only a set's worth of natural transformations?
I need a function $\mathsf{Nat} \big( \mathsf C (-, X), F \big) \to FX$. That means that for every $\eta \in \mathsf{Nat} \big( \mathsf C (-, X), F \big)$, I need $\eta \mapsto y$ where $y \in FX$.
Each natural transformation $\eta \colon \mathsf C(-, X) \to F$ is itself a collection (not necessarily a set, I think) of morphisms $\eta_A \colon \mathsf C(A, X) \to FA$ for every object $A$ in $\mathsf C$ (which is the same as $\mathsf C^{\text{op}}$, at least in terms of objects). The morphisms must be such that the diagram below commutes for every morphism $f \colon X \to Y$ in $\mathsf C$.
\begin{align*} \begin{matrix} \mathsf C(Y, X) & \xrightarrow{f^*} & \mathsf C(X, X) \\ \downarrow \eta_Y & \ & \downarrow \eta_X\\ FY & \xrightarrow{Ff} & FX \end{matrix} \end{align*}
(Sorry for the ugly diagram.)
Regarding the hint given in the exercise, I know $\mathsf C(X, X)$ has an element $\text{id}_X$. This is part of the definition of a category. I am not sure what the notation $\eta \text{ id}_X$ means. Is it composition? I am not sure that makes sense because $\eta$ is not a function: it's a collection of morphisms. I know that functors are supposed to send the identity to the identity for the ``output'' object.
Looking at this answer to what I think is a very similar question, the suggestion (in the notation I use) seems to be to define the map such that $\eta \mapsto \eta_X (\text{id}_X)$. I don't understand what this means; $\eta_X \colon \mathsf C(X, X) \to FX$ is a morphism (function) between objects in $\mathsf{Set}$. I guess that means $\eta_X (\text{id}_X) \in FX$.
So the function $\mathsf{Nat} \big( \mathsf C (-, X), F \big) \to FX$ we were seeking is (tentatively) the one such that $\eta \mapsto \eta_X (\text{id}_X)$. If this is true then all I have to do is find an inverse function $FX \to \mathsf{Nat} \big( \mathsf C (-, X), F \big)$, and prove that it's an inverse.
I am thinking about what kind of function I could devise that would send $\eta_X (\text{id}_X)$ to $\eta$, but I think this is misleading because any given element $x \in FX$ won't necessarily be in that form. As far as I know, I can't assume bijectivity of any of the constituent morphisms of any natural transformation.
I tried looking at the Wikipedia page on the Yoneda lemma, but I think it discusses the covariant form, and translating to the contravariant form and translating into my notation completely scrambles my brain.
This is worth going through carefully and ideally with a bunch of examples so you can see what's going on more clearly. Let's carefully write down what a natural transformation $\eta : C(-, X) \to F(-)$ is. It assigns to every object $Y \in C$ a function
$$\eta_Y : C(Y, X) \to F(Y)$$
which is natural in the sense that if $f : Y \to Z$ is a morphism, then the following composites are equal:
$$\left( C(Z, X) \xrightarrow{C(f, X)} C(Y, X) \xrightarrow{\eta_Y} F(Y) \right) = \left( C(Z, X) \xrightarrow{\eta_Z} F(Z) \xrightarrow{F(f)} F(Y) \right).$$
The basic idea behind the Yoneda lemma is that naturality means that $\eta_Y$, which a priori is a lot of information, is extremely redundant. Specifically, practically the only thing we're guaranteed about the homsets $C(Y, X)$ is that when $Y = X$ the homset $C(X, X)$ has a distinguished element, namely the identity $\text{id}_X$. That suggests that the element
$$\eta_X(\text{id}_X) \in F(X)$$
is special in some way, and in fact it's so special it ends up determining $\eta$ entirely. To see this, set $Z = X$ in the naturality condition above, which gives that if $f : Y \to X$ is a morphism, then
$$\left( C(X, X) \xrightarrow{C(f, X)} C(Y, X) \xrightarrow{\eta_Y} F(Y) \right) = \left( C(X, X) \xrightarrow{\eta_X} F(X) \xrightarrow{F(f)} F(Y) \right).$$
Now apply both sides to $\text{id}_X \in C(X, X)$. $C(f, X)$ applied to $\text{id}_X$ just produces $f$ again, and we get
$$\eta_Y(f) = (F(f) \circ \eta_X)(\text{id}_X) = F(f)(\eta_X(\text{id}_X)).$$
Because $Y$ and $f$ are arbitrary, the LHS, when varied over all choices of $Y$ and $f$, is a complete description of the natural transformation $\eta$. On the RHS, we see that the action of $\eta$ on an aritrary morphism is completely determined by 1) the action of $\eta$ on $\text{id}_X$ and 2) the functoriality of $F$ itself.
So this is the desired inverse: given an element $u \in F(X)$, show that defining $\eta_Y(f) = F(f)(u)$ gives a natural transformation $\eta : C(-, X) \to F(-)$ such that $\eta_X(\text{id}_X) = u$. There's a small detail left to check from here but it's not so bad.
A larger question is what the hell this argument means, and that's a longer story. The element $\text{id}_X \in C(-, X)$ has a special name: it's called the universal element of the representable functor $C(-, X)$. What the Yoneda lemma says is that a natural transformation out of a representable functor is uniquely and freely determined by what it does to the universal element.
The name "universal element" is, I think, best understood through seeing a list of examples of representable functors and their universal elements. Here's one that's relatively easy to understand:
The presheaf $P : \text{Set}^{op} \to \text{Set}$ sending a set $X$ to the set of subsets of $X$ (and sending a function $f : X \to Y$ to the inverse image function $f^{-1} : P(Y) \to P(X)$) is represented by the $2$-element set $2$, so we have a natural isomorphism $P(X) \cong \text{Set}(X, 2)$; explicitly, if we think of $2 = \{ 0, 1 \}$, the natural isomorphism sends a subset $S \subseteq X$ to its indicator function $1_S : X \to 2$, which is equal to $1$ on $S$ and $0$ on the complement. The universal element is the identity $\text{id}_2 : 2 \to 2$, which corresponds to $1$ regarded as a subset of $2 = \{ 0, 1 \}$. This means $1 \subset 2$ is the universal subset; every subset $S$ of every set $X$ arises as the inverse image of $1$ under a canonical map $X \to 2$ (precisely the indicator function $1_S$).
There are examples in algebra and algebraic topology and algebraic geometry worth understanding also. There are universal bundles, universal cohomology classes, universal elliptic curves, all sorts of fun stuff.