Let me remind you briefly of how Godel's proof works. You start with an axiomatic system (i.e., a list of allowed characters -- a language -- and a list of axioms in that language) that includes all the usual operations involving natural numbers. Because of the unique prime factorization property, you can assign each string in the language a unique number (called its Godel number) as follows: first assign each allowed character a number, then encode the string as 2^(number of first character) x 3^(number of second character) x 5^(...). E.g. if the language were English, you could encode the string "babe" as 2^2 x 3^1 x 5^2 x 7^5 = some large number. You could recover the word from the number by counting the 2's in its (unique) prime factorization to get your first character, then counting the 3's for your second character, and so on. Now you can start making self-referential statements within your language, you can say something like "the string with Godel number N has certain properties," which would mean "the string 'blah' has certain properties." You could drop "the string" as that's implied by the quotes.
It turns out that one of these sentences is essentially Quine's version of the liar's paradox:
- “Yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.
Now the point is that none of this would have worked without the uniqueness of prime factorization. And it's hard to see why a physical theory of everything -- if it were axiomatizable -- would have prime factorization in it. Consider the following simple theory of everything, which is of course incorrect but is probably structurally similar to what the real one would look like -- it has a finite list of things, 1 through N, each with a charge and a mass; the forces acting on each of them in any given configuration follow from Maxwell's equations, and how they react to the force is determined by Newton's laws of motion. (Throw in gravitation as well, it doesn't matter.) The point is that you now have all the prerequisites for an axiomatic system in which one can ask all sorts of questions about what the velocities, positions, position-velocity correlations, etc. of the particles are at any time, i.e., this is Laplace's universe. The key point is that the minimal set of mathematical rules you need to make sense of this theory are rules about arithmetical operations on the real numbers. Although the reals include the naturals, they are infinitely simpler because everything divides everything else. Natural numbers do not enter the language of the theory at all -- yes, you need natural numbers to list the particles while constructing the language of the theory, but that's in the meta-language. Ergo no prime factorization, ergo no self-referential statements, ergo no incompleteness theorem. While we do not know quite what the theory of everything would be it seems almost certain to be structurally rather like the one I just described. (You might say, well, isn't quantum mechanics "grainy" and doesn't it therefore have something to do with the integers; the graininess doesn't enter into the fundamental equations, but even if this were the case, you only add and never multiply quanta so you wouldn't need all of Peano arithmetic so you wouldn't have an incompleteness theorem.)
I think this is all true so far as it goes but there's a potential loophole in the argument, which is that one might want to ask questions about the world that are not phraseable in the language of the theory. For example one might want to ask questions about thermodynamics, involving macroscopic quantities like pressure and temperature in my toy axiomatic system. I could, in principle, define pressure in terms of a sum over all the velocities of the particles near the walls divided by the number of particles (or something like that), but really what I want to talk about when I'm talking about pressure is a property that becomes well-defined only for systems, and I can't even construct my toy theory of everything for an infinite system. Therefore, what I'm really doing when I construct thermodynamics is setting up an entirely new axiomatic system by a process of taking limits over larger and larger versions of the original theory of everything.
Basically what this says is that a theory of everything in the ordinarily understood sense is not a theory in which a lot of the questions that physicists in practice work on would be well-defined. Could these "effective" theories, or the union of them, be strong enough to include PA? Maybe. In particular, a lot of natural-number arithmetic comes in from the topological properties of wavefunctions, the spaces they live in, etc. I'm still doubtful that you'd ever have to multiply natural numbers, but it's not beyond the bounds of possibility.