I've gotten to the point of the book Godel, Escher, Bach which really gets into demonstrating the mechanisms of Godel's incompleteness proof. I've had to go back and forth through it a few times, and have been bouncing it off of Cantor's diagonal proof, as the author intends. But I think I've reached a point that is unintended and not sure how to resolve it.
If any natural number is itself a well-formed expression (right? [1]), then there are at least as many well-formed expressions as there are natural numbers. And clearly there are even more well-formed expressions than that, since for example, each $i + 1$ is also a well formed expression.
So piggy backing off the diagonal idea, it seems similarly that the number of well-formed expressions in a formal system is greater than the number of natural numbers. And wouldn't that mean that Godel-numbering itself is impossible in any given formal system?
It seems to be a similar point reached in each proof leads to different outcomes. Why doesn't Godel's proof similarly lead to the result that "Godel-numbering a formal system is impossible"?
Please excuse that I am not a mathematician and only have kind of a tenuous grip on both proofs, or on the idea of "distinct infinities".
[1] I'm not sure if an natural number by itself is a well-formed expression, but it doesn't matter, since each $i = i$ is clearly a well-formed expression.
You must be very careful when arguing with infinities. Consider this part of your argument:
Everything you said is right, but we cannot conclude from this argument that the number of well-formed expressions is greater than the number of natural numbers. For finite sets, your argument would be correct, but not in the case of infinite sets. Remember that if $A$ and $B$ are sets, then the definition of $|A| < |B|$ (i.e., there are more elements in $B$ than $A$) is that there is an injective map from $A$ to $B$, but there is no map from $A$ to $B$ which is both injective and surjective. (Please look up the definitions of those terms if you are not familiar with them.)
Now let's state your argument formally.
Let $A$ be the set of natural numbers.
Let $B$ be the set of well-formed expressions.
Your argument states that there is an injective map $f : A \to B$, sending each natural number $n$ to a well-formed expression $n$. And then you have stated that there are even more well-formed expressions which are not in the image of $f$, i.e., $f$ is not surjective. That is all correct.
If $A$ and $B$ were finite sets, this would be enough to conclude that $|A| < |B|$, but not in the case of infinite sets. For in the infinite case, the existence of the injective map $f$ is not enough to preclude the existence of a different map $g: A \to B$ which is both injective and surjective.
To see an example of this, let $\mathbb{N} = \{0,1,2,\ldots\}$ be the natural numbers. Consider a map $f : \mathbb{N} \to \mathbb{N}$ defined by $f(n) = n+1$. Then $f$ is clearly injective, and $f$ is not surjective because 0 is not the image of $f$.
However, it is obviously not true that $|\mathbb{N}| < |\mathbb{N}|$, because there is another map $g : \mathbb{N} \to \mathbb{N}$ which is both injective and surjective, namely $g(n) = n$.