On the Possibility of Godel Numbering 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.
 A: You must be very careful when arguing with infinities.  Consider this part of your argument:

If any natural number is itself a well-formed expression (right?), 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.

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$.
