ABSTRACT
In Section 2.2 it was commented that the common popular formulation of the incompleteness theorem as applying to any formal system of “sufficient complexity” is misleading at best, since there are very complex systems to which the theorem does not apply and very simple ones to which it does apply. Most often in such misleading formulations of the incompleteness theorem, “complexity” is perhaps used in an informal sense. In such a case it suffices to look at a system like Robinson arithmetic (defined in the Appendix) to see that very simple systems can encompass the “certain amount of arithmetic” needed for the incompleteness theorem to apply. In the other direction, it is a simple matter to formulate complete and consistent theories of impenetrable complexity. So if we use “complexity” in an informal sense, there is no correlation between complexity and incompleteness.
