I have read that complex axiomatics are Gödel complete, while naturals aren't. Why?

Question

I have read in a book:(G. Martínez, G. Piñieiro: "Gödel para todos") that complex axiomatics are Gödel complete, while naturals aren't. How can this be if Naturals are a subset of Complexes, (or at least, the Naturals are isomorphic to a subset of Complexes?

Answer 1

Perhaps your book didn't explain what it meant by "axiomatics", but you have to learn the precise definitions before it is possible to understand Godel's incompleteness theorems. There is no one formal system for the natural numbers, but there is a widely used one called (first-order) PA. It can prove quite a lot of elementary number theory, but if it is consistent it cannot prove or disprove infinitely many sentences in the language of PA. The language of PA has the signature $(0,1,+,\times)$ at least (one can add the successor function symbol $S$, but it is expressible using the rest by writing "$S(t)$" as "$t+1$"). It turns out that no recursive extension of PA can be complete (there will always be some sentence that can be neither proven nor disproven).

In contrast, the theory of the complex numbers (the first-order theory that consists of all the true sentences over the language of fields), denoted by $Th(\mathbb{C})$, has a recursive axiomatization. The language of fields has the same signature as what I gave above for $PA$. It turns out that one possible recursive axiomatization for $Th(\mathbb{C})$ is the axiomatization ACF0 of algebraically closed fields with characteristic zero, which consists of axioms of fields, plus axioms stating the existence of a root for every non-constant $1$-variable polynomial, plus axioms of the form "$1+\cdots+1 \ne 0$" for all possible number of ones. In fact, one of the easiest way to show that $Th(\mathbb{C})$ has a recursive axiomatization is simply to prove that ACF0 gives a complete theory, by first proving quantifier elimination for ACF0 and then showing that quantifier-free sentences are either proven or disproven by ACF0.

The key point is that PA and ACF0 have different incompatible axioms. PA proves the sentence "$\neg \exists n\ ( n + n = 1 )$" while ACF0 proves its negation "$\exists n\ ( n + n = 1 )$". So it is not at all surprising that they are completely different. Don't forget that PA is supposed to capture the properties of the natural numbers as a whole, and just because we can embed natural numbers into the complex numbers says nothing about the relation between the properties of $\mathbb{N}$ and those of $\mathbb{C}$.

If we attempt to extend the language with a predicate symbol $N$ so that we can axiomatize both $\mathbb{C}$ and its subset $\mathbb{N}$ by including the axioms of ACF0, and the axioms of PA modified such that all quantifiers involved are restricted to $N$, then the resulting theory will no longer be complete because it correctly proves and disproves the same sentences as PA (after they are translated accordingly).

If you are unfamiliar with logic, please see here for resources that I recommend.

Answer 2

The short answer is that the (first-order) arithmetic of the complex numbers is insufficient to even propose the question

• Is this complex number a natural number?

which means it cannot even speak about the kinds of questions that cause problems with integer arithmetic. For example, the problem of Diophantine equations — the theory of complex arithmetic is capable of asking whether systems of equations have real solutions, but cannot go on to discuss the more refined question of whether any of those solutions are integer solutions.

The simplest formulation of a theory of complex arithmetic is probably the theory of real closed fields which, by a theorem of Tarski, is complete.

Note that I am considering complex conjugation as part of the arithmetic of the complexes; the theory of complex arithmetic is able to use complex conjugation to define the real numbers by $z = \bar{z}$, so the theory of complex arithmetic can talk about real arithmetic. Conversely, the theory of real arithmetic can talk about complex arithmetic by mimicking the usual construction of complexes as pairs of real numbers.

The only subsets of the real line you can define the theory of real closed fields are finite unions of intervals whose endpoints are algebraic numbers. (infinite 'endpoints' are allowed; e.g. $(0,\infty)$ is allowed, and is defined by the proposition $x > 0$)

In particular, the natural numbers can only be given as an infinite union of intervals:

$$ \mathbb{N} = [0,0] \cup [1,1] \cup [2,2] \cup \ldots $$

and thus cannot be described in the theory of real closed fields.