Does infinity cause incompleteness in formal systems? Is a finite formal system complete?

Question

Like most, I'm having a hard time understanding the consequences of Gödel's Incompleteness Theorems.
In particular, I'd like to understand their connection to the concept of infinite mathematical structures.
In doing so, I hope to formulate a better opinion on the merits of constructivism and finitism in regards to Gödel's theorems.

Without being philosophical, I want to know whether a given formal system built from constructionist principals (finite mathematical objects), would be complete, and whether Gödel's arguments say anything about these kinds of systems.

Taken together, the two theorems can be informally stated as followed:

First incompleteness theorem (Godel-Rosser): Any consistent formal system S within which a certain amount of elementary arithmetic can be carried out is incomplete with regard to statements of elementary arithmetic: there are such statements which can neither be proved, nor disproved in S.

Second incompleteness theorem (Godel): For any consistent formal system S within which a certain amount of elementary arithmetic can be carried out, the consistency of S cannot be proved in S itself.

(I'm quoting from a book called Gödel's Theorem: An Incomplete Guide to Its Use and Abuse)

In both of these cases they say "a certain amount of elementary arithmetic".
But what does that mean in regards to "infinity"? Does that mean a requirement for incompleteness is an infinite amount of objects capable of arithmetic (i.e. like an infinite amount of numbers (i.e. the natural numbers))?

Or maybe stated in terms of Peano arithmetic: "For every natural number n, S(n) is a natural number."

There is incompleteness in the arithmetic of this system because you can always call a successor function to get another number?

---

These are the specific questions I have around the subject:

1. If a system has a finite amount of numbers for arithmetic, can the system be complete?
2. If ZFC does not have the axiom of infinity, can the system be complete?

I have an infinitesimal amount of experience in mathematics, so I appreciate your indulgence.

Answer 1

Incidentally, you may find the following questions relevant: 1, 2.

---

Let me begin by making a couple comments on the precise formulation of the first incompleteness theorem (until it's understood there's really no point in looking at the second). I suspect these elaborations will by themselves help clarify some issues.

The first point is that there's a hypothesis in the incompleteness theorem which hasn't been explicitly articulated in the formulation above (rather, it's implicit in the term "formal system" but as such it's very easy to miss). Really, the "right" way to state the theorem is the following:

Suppose $T$ is a set of sentences in first-order logic which is consistent, computably axiomatizable, and interprets Robinson arithmetic. Then $T$ is incomplete.

The bolded condition above is the hidden hypothesis: the set of all true sentences about the natural numbers, for example, is clearly strong enough to do basic arithmetic and is consistent and complete, but it does not constitute a counterexample to Godel's theorem since it cannot be given a computable axiomatization. (Meanwhile, the phrase "interprets Robinson arithmetic" is a precisiation of the vague phrase "a certain amount of elementary arithmetic can be carried out.")

The second point is a reframing issue. Incompleteness by itself isn't that interesting a condition; rather, what Godel's theorem is really about is essential incompleteness. A computably axiomatizable theory is essentially incomplete if all computablly axiomatizable theories interpreting it are incomplete (this is usually phrased as "all computably axiomatizable theories containing it are incomplete," which a priori looks weaker, but the two phrasings are in fact equivalent). Basically, mere incompleteness of a theory leaves open the possibility of "fixing" it with a small change, while essential incompleteness makes incompleteness unavoidable ... at least, without making the theory extremely complicated (namely, not computably axiomatizable).

---

OK, now let's look at what is and is not needed for the incompleteness theorem to apply to a given theory.

First, note that the number of axioms is entirely irrelevant. For example, Robinson arithmetic is finitely axiomatizable but essentially incomplete but the theory of algebraically closed fields of characteristic $0$ is not finitely axiomatizable but is complete and computable as mentioned below.

The size of the models of the theory is much more important; in particular, all models being infinite is a necessary feature in the following sense: if $M$ is a finite structure in a finite language, then there is a single sentence $\varphi$ which pins $M$ down up to isomorphism (that is, the structures in which $\varphi$ is true are exactly the structures isomorphic to $M$). A fortiori then the theory with the single axiom $\varphi$ is consistent, complete, and computable. So in particular, if $T$ is a theory which has a finite model, then $T$ is not essentially incomplete.

However, merely having only infinite models is not enough to guarantee essential incompleteness, or even mere incompleteness. Each of the following theories is complete, is computable, and only has infinite models:

• The theory of an infinite pure set.

• The theory of real closed fields.

• The theory of algebraically closed fields of characteristic $0$.

• The theory of dense linear orders without endpoints.

• The theory of natural-number arithmetic with just addition (or natural-number arithmetic with just multiplication).

Basically, even amongst the infinite structures there are fundamental dividing lines in terms of complexity: on the one hand you have structures like $(\mathbb{R};+,\cdot)$ whose whole theory is computable (these are the decidable structures), while on the other hand you have structures like $(\mathbb{N};+,\cdot)$ whose theory isn't only non-computable but also has finitely axiomatizable essentially incomplete subtheories. Ultimately what makes a structure "Godelian" is its ability to implement computations.