Comment by yohanatan

It doesn't take 'infinite complexity' [your term] to encode the natural numbers. Rather it is only a handful of axioms. See: http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic

Pretty much any system of logic worth looking at (including any which the sciences may be based on and the one running inside each human brain) is going to at least be as complex as this set of axioms.

Also, you really should read the JR Lucas material-- it explains this. And, I'd suggest Nagel & Newman's _Godel's Proof_ for a great introductory explanation of the Incompleteness Theorems.