2
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ "finite formal system" may be ambiguous. The formal system is identified by its language and axioms: Robinson Arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic and it is incomplete. But you are speaking of infinity of natural numbers: thus, it seems that you are considering a formal system having only finite models. $\endgroup$ – Mauro ALLEGRANZA Jun 17 '20 at 7:35
  • $\begingroup$ Goedel's first incompleteness theorem applies to all theories that are strong enough for the representation theorem. If you mean with "finite" a system containing only a finite amunt of integers, then of course such a system would be complete, but I doubt that finite many integers can build such a theory at all. $\endgroup$ – Peter Jun 17 '20 at 8:40
  • $\begingroup$ The problem with ultrafinitistic arguments about completeness is that you are not taking into account the length of proofs, or the number of statements. Normally, you'd argue that since a theory has only finite models, there is a finite number of them (up to isomorphism), and then you can recursively decide everything. But these proofs tend to forego the fact that the proof by recursion may utilise statements that are "too long" for the ultrafinitistic framework. $\endgroup$ – Asaf Karagila♦ Jun 17 '20 at 14:05
  • $\begingroup$ And ZFC - Infinity cannot be complete, because removing axioms cannot make a theory complete. Only adding axioms. $\endgroup$ – Asaf Karagila♦ Jun 17 '20 at 14:06
  • $\begingroup$ Perhaps replacing the axiom of infinity with its negation? $\endgroup$ – Trevor Hickey Jun 17 '20 at 15:42
5
$\begingroup$

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:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.