There is the following well known and very useful heuristic principle: **Assume one has a natural map from the space of $k$-tuples of functions in $n$ variables into the space of $K$-tuples of functions in $N$ variables such that either (a) $n<N$ or (b) $n=N$ and $k<K$. Then this map cannot be onto. Also natural maps in the opposite direction cannot be injective.**


**I would like to have rigorous theorems making this principle precise.**


Let me state few examples of precise statements for which I would like to have a rigorous proof.


*Example 1.* On an $n$-dimensional manifold $M$, $n>2$, there exists a Riemannian metric which cannot be realized isometrically as a hypersurface in $\mathbb{R}^{n+1}$. (Here we have the obvious map from the space of imbeddings of $M$ to $\mathbb{R}^{n+1}$ to the space of metrics on $M$. The former space is an open subset in the space of $(n+1)$-tuples of functions in $n$ variables; the latter space is the space of $n(n+1)/2$-tuples of functions in $n$ variables. But for $n>2$ one has $n(n+1)/2>n+1$.)


*Example 2.* Let $n>3$. Consider the map from metrics on $\mathbb{R}^n$ to sections of the tensor bundle $Sym^2(\wedge^2T^\*\mathbb{R}^n)$ sending the metric to its Riemann curvature tensor. Then this map cannot be onto. (This example for discussed at this post [Equations satisfied by the Riemann curvature tensor](https://mathoverflow.net/questions/202211/equations-satisfied-by-the-riemann-curvature-tensor))


*Example 3.* There exist systems of ordinary differential equations of second order on $\mathbb{R}^n$ which cannot be considered as Euler-Lagrange equations for any Lagrangian.


*Example 4.* Consider the Radon transform between spaces of functions on two real Grassmannians $Gr$ and $Gr'$. If $\dim Gr> \dim Gr'$ then it must have nontrivial kernel.


Finally let me state few rigorous results contradicting the principle stated at the beginning of this post.


1) The Hilbert spaces of $L^2$-functions on any two Riemannian manifolds are isomorphic.


2) The Banach spaces of continuous functions on any two compact manifolds of any positive dimension are isomorphic (it fact, for any uncountable compact metric spaces). (Milyutin's theorem.)


3) The Frechet spaces of infinitely smooth functions on torii of any positive dimension are isomorphic.



Rigorous justification that overdetermined systems do not have a solution
There is probably no single proof that would provide a rigorous justification of the OP's principle in all cases. Moreover, without specifying more clearly what is meant by a 'natural map', the principle itself turns out not to hold in general. 


For example, every smooth (complex-valued) function $f$ on the unit circle $S^1\subset\mathbb{C}$ can be written uniquely in the form
$$
f(e^{i\theta}) = f\_0(e^{2i\theta}) + e^{i\theta}\,f\_1(e^{2i\theta}),
$$
and the (natural?) 'even-odd' decomposition mapping $f(e^{i\theta})\mapsto \bigl(f\_0(e^{i\theta}),f\_1(e^{i\theta})\bigr)\ $ is one-to-one and onto.


As a (perhaps) more serious example, by the [Nash-Kuiper $C^1$-isometric embedding theorem](http://en.wikipedia.org/wiki/Nash_embedding_theorem), any smooth Riemannian metric $g$ in dimension $n$ can be locally isometrically embedded into $\mathbb{R}^{n+1}$ by a $C^1$-mapping. Since metrics in dimension $n$ depend on $\tfrac12n(n{+}1)$ functions of $n$ variables while maps into $\mathbb{R}^{n+1}$ depend on $n{+}1$ functions of $n$ variables, this violates your heuristic principle when $n>2$. (To be sure, the Nash-Kuiper theorem was greeted with astonishment when it first appeared in 1954.) 


It would be hard to argue that the mapping $\Phi(f) = \mathrm{d}f\cdot\mathrm{d}f = g$, where $f:M^n\to\mathbb{R}^{n+1}$ and $g$ is a metric on $M$ is not natural, but, of course, one can object that the differing degrees of differentiability on $f$ and $g$ should be taken into account in any careful formulation of a heuristic principle along the lines that the OP wants.


Now, there *is* a wide class of equations that includes the OP's Examples 1, 2, and 3 and explains the failure of surjectivity of each of them, namely the class of *smooth nonlinear differential operators*, $\Phi:C^\infty(E)\to C^\infty(F)$, where $E$ and $F$ are bundles over a common base manifold $M$.


To formulate this notion precisely, recall that, given a smooth bundle $E\to M$ of fiber rank $p$, say, and where $M$ is a smooth manifold of dimension $n$, one has the bundle $J^k(E)\to M$ of $k$-jets of sections of $E$, which is a smooth bundle of fiber rank $p{{n+k}\choose n}$. 


Given another smooth bundle $F\to M$ of fiber rank $q$, say, a (smooth) nonlinear differential operator of order at most $s$, say $\Phi:C^\infty(E)\to C^\infty(F)$
is a mapping of the form $\Phi(u) = \Phi^s\bigl(j^s(u)\bigr)$ for all $u\in C^\infty(E)$
where $\Phi^s: J^s(E)\to F$ is a smooth bundle mapping. (In practice, one often only has $\Phi^s$ defined on an open subbundle $A^s\subset J^s(E)$, in which case one says that a section $u:M\to E$ is *$A^s$-admissible* if its associated $s$-jet section $j^s(u):M\to J^s(E)$ has its image lying in $A^s$. Then, one only gets a mapping $\Phi:C^\infty(E,A)\to C^\infty(F)$, where $C^\infty(E,A)\subset C^\infty(E)$ is the subset of $A^s$-admissible sections. The reader can deal with the details of that situation.) 


In this case, the OP's heuristic principle would suggest that $\Phi$ cannot be surjective, even locally, if the rank of $F$ is greater than the rank of $E$. Indeed, this turns out to be the case, and can be proved rigorously by the argument below.


First, though, note that the OP's Example 1 is a nonlinear differential operator of order $1$, where $E = M\times \mathbb{R}^{n+1}$ and $F = S^2(T^\*M)$ and $\Phi^1(u) = \mathrm{d}u\cdot\mathrm{d}u$. Here, $(p,q) = \bigl(n{+}1, {{n+1}\choose2}\bigr)$.
Similarly, the OP's Examples 2 and 3 are nonlinear differential operators of order $2$, with 
$(p,q) = \bigl({{n+1}\choose2}, \frac{n^2(n^2-1)}{12}\bigr)$ in the case of Example 2, and
$(p,q) = \bigl(1, \frac{n}2\bigr)$ in the case of Example 3 (here, the underlying manifold is $T\mathbb{R}^{n/2} = \mathbb{R^n}$, on which the Lagrangian for curves would be defined).


To prove the promised nonsurjectivity, suppose given such a smooth differential operator. One then has canonical *prolongations* $\Phi^k:J^k(E)\to J^{k-s}(F)$ for $k\ge s$, which are defined by the property that 
$$
\Phi^k\bigl(j^k(u)\bigr) = j^{k-s}\bigl(\Phi^s(j^s(u))\bigr)
$$
for all $k\ge s$ and all (local) sections $u\in C^\infty(E)$. 


*The crucial consequence of this equation is that the $(k{-}s)$-jets of sections $v:M\to F$ that are of the form $v = \Phi(u) = \Phi^s(j^s(u))$ for some $u\in C^\infty(E)$ have to lie in the image of $\Phi^k$.* 


Now, if $p<q$, then for all $k$ sufficiently large, one has
$$
\dim J^k(E) = n + p{{n+k}\choose n} < n+ q{{n+k-s}\choose n} = \dim J^{k-s}(F).
$$
Thus, the prolongation map $\Phi^k:J^k(E)\to J^{k-s}(F)$ cannot be surjective for $k$ sufficiently large, and this implies that the equation $v = \Phi^s(j^s(u))$ has no solution, even locally, for the generic section $v:M\to F$, i.e., $\Phi:C^\infty(E)\to C^\infty(F)$ is not surjective.


Finally, note that this argument heavily uses the assumption of infinite differentiability. This is not surprising because, as the Nash-Kuiper theorem shows, this non-surjectivity can indeed fail spectacularly without such assumptions.


