When does a formal system cease to be able to be complete and consistent?

Question

In Gödel, Escher, Bach , Hofstadler contends that certain formal systems may be both consistent and complete, such as his own pq system. However, for certain "sufficiently powerful" formal systems, they cease to be able to be both consistent and complete, as per Gödel. Are there criteria for the "power" of a formal system that make the system inconsistent?

Answer 1

There isn't yet anything I'd call a sharp answer to this question, but there are some pretty good things we can say. The relevant yardstick is interpretability: roughly, we say that one theory $T$ interprets another theory $S$ if there is a way to "embed" the logical structure of $S$ into $T$. Complexity properties of $S$ then translate to complexity properties of $T$. So, for example, we have theorems like:

If $T$ is any consistent recursively axiomatizable theory interpreting Robinson arithmetic, then $T$ is incomplete.

Roughly speaking, being able to implement addition and multiplication of naturals even to a very small degree renders a system subject to Godel's theorem. Both addition and multiplication are needed, however: Presburger arithmetic (= the theory of the natural numbers with addition only) and Skolem arithmetic (= the theory of the natural numbers with multiplication only) are each consistent, complete, and recursively axiomatizable.

---

Note that recursive axiomatizability is crucial here: the full theory of $(\mathbb{N}; +,\times)$ ("true arithmetic," $TA$) is trivially complete and consistent, and this does not lead to a contradiction with Godel since $TA$ is not recursive.