I already asked this question but it seems there was some confusion, so I am trying again being more careful with my language.
Intuition
Assume we have a smooth 2D manifold $M$ embedded in 3D. Assume that there is a smooth, differentiable, function $f : M \rightarrow \mathbb{R}$ for example, let's say $f$ measures the heat of the surface at every point.
Assume there is a single point in the entire surface that is the hottest and that as we move away from it things become colder, i.e. the temperature of a point is related to its surface distance to the hottest point. This implies that starting at any point, I can look at an epsilon round it and fin the hottest point in that neighbourhood, then move towards it. I can then repeat that over and over again and thus converge to the hottest point.
This is gradient descent on the surface of the manifold. The existence of the above algorithm implies the existence of a tangent vector at every point that points to the direction of largest change in temperature on the surface.
Proof there is a gradient vector
Take an arbitrary point $p$. The surface is manifold, by definition there is an epsilon neighbourhood around $p$ that is isomorphic to the 2D plane. So let's evaluate $f$ on $E \subset M$, the epsilon neighbourhood. Because this region is isomorphic to the 2D plane through an isomorphism $I: E \rightarrow\mathbb{R}^2$ we can do the composition $f(X_E) = f(I(X_{\mathbb{R}^2}))$ where $X_E \in E$.
In plain English, we can evaluate $f$ directly on $\mathbb{R}^2$ so in other words $f(X_E) = f(x,y)$ for some $x,y \in \mathbb{R}$. So $f$ is now a smooth, differentiable, scalar valued function in 2 variables, so it objectively has a gradient vector in the domain $\mathbb{R}^2$ for any point $X$.
A more straightforward way to show that this gradient exists in $\mathbb{R}^2$ is purely algebraically:
We are given a parametric surface $s = <(X(u,v), Y(u,v), Z(u,v))>$ and a function $f: s\rightarrow\mathbb{R}$. This implies that $f(s(u,v)) = F(u,v)$ for some function $F:\mathbb{R}^2 \rightarrow \mathbb{R}$.
The gradient of $F$ is merely $\nabla F = <\frac{\partial F}{\partial u}, \frac{\partial F}{\partial v}>$
This implies that:
$\nabla f = <\frac{\partial f}{\partial X}\frac{\partial X}{\partial u} + \frac{\partial f}{\partial Y}\frac{\partial Y}{\partial u} + \frac{\partial f}{\partial Z}\frac{\partial Z}{\partial u}, \frac{\partial f}{\partial X}\frac{\partial X}{\partial v} + \frac{\partial f}{\partial Y}\frac{\partial Y}{\partial v} + \frac{\partial f}{\partial Z}\frac{\partial Z}{\partial v}>$
Thus $\nabla f$ is the gradient of $f$ as expressed in $\mathbb{R}^2$
Problem
Ok so hopefully any miss understanding from the prior attempt has been cleared off. A gradient vector must exist given the constraints. However What I have found is the gradient as expressed in the parametric domain $(u, v)$ However what I am looking for is the gradient expressed as a tangent vector to the surface, such that it points to the direction of greatest change, locally at any point.
This is where I am getting lost.
Definition
Well I technically found the answer after some more search, but this doesn't give me the proof.
The actual answer is that one just takes the gradient of $f$ in $\mathbb{R}^3$ and then projects it onto the tangent plane of the point. Which, ok, trivially this will be contained in the tangent plane of the surface. And it's certainly related to the gradient. But I don't immediately see that the orthogonal projection of $\nabla f$ onto the tangent plane is necessarily the direction of greatest change along the surface.
Like it makes sense, I just want to formalize it, prove it.
TL;DR I want to prove that $\nabla f - (\nabla f \cdot \vec{n}) \vec{n}$ (the gradient of $f$ minus its orthogonal component to the tangent plane) is the direction of greatest change along the surface $M$.