Q - Robinson Arithmetic

Now that we are familiar with Baby Arithmetic (BA), we can make its language more expressive by allowing variables and quantifiers back into its logical vocabulary. When we do this, we simply obtain the interpreted language L_A, that was described earlier.

Since we now have variables and quantifiers, we can replace the schemata of BA with regular axioms (see below). The resulting formal system of arithmetic is called Robinson Arithmetic and is often denoted by the letter Q, as described in Chapter 8 of Peter Smith's book. Here is his definition of Q:

Baby arithmetic

Since chapter 7 in Peter Smith's book is so short, I'll summarize it quickly and then start discussing chapter 8.

Chapter 7 starts by comparing the two incompleteness theorems discussed in previous chapters (let's call these "Smith's theorems") to Gödel's first incompleteness theorem as follows:

Consistent, sufficiently strong formal systems of arithmetic are incomplete

In Chapter 6, Peter Smith proves another incompleteness theorem. To place this theorem in context, let's review some definitions about axiomatized formal theories (or AFTs) from earlier posts.

Let T be some AFT.

• T is consistent iff (if and only if) there is no sentence φ such that T proves both φ and ¬ φ.
• T is sound iff every theorem that T proves is true according to the interpretation that is built into T's language.
• T is (negation-)complete iff for every sentence φ in T's language, T proves either φ or ¬ φ.
• T is decidable iff there is an algorithm that, given any sentence φ in T's language, determines whether or not T proves φ.
• If needed, go here to review what it means for T's language to express a numerical property P or a numerical relation R.
• If needed, go here to review what it means for T to capture a numerical property P or a numerical relation R. 
• If needed, go here to review what it means for T's language to be sufficiently expressive.

We'll use the following abbreviations:

Sound formal systems with sufficiently expressive languages are incomplete

In chapter 5, Peter Smith uses a counting argument to prove that sound axiomatized formal theories (AFTs) that can express a good amount of arithmetic are incomplete. In short: since their set of theorems is effectively enumerable but their set of true sentences is not, the two sets must be different. In a sound theory, the theorems are all true. Therefore, some truths must remained unproved in such theories.

Let's start with a definition. The language of an AFT of arithmetic is sufficiently expressive if and only if:

1. It can express quantification over numbers, and
2. It can express every effectively decidable two-place numerical relation.

Now, to the pivotal theorem of this chapter:

An enumerable but not effectively enumerable set

Let's focus on the first half of chapter 5 in Peter Smith's book. First, Smith describes a new characterization of effectively enumerable sets. Second, Smith gives an example of a set of integers that is not effectively enumerable.

Let's define the numerical domain of an algorithm as the set of natural numbers with the following property: when the algorithm takes one of these numbers as input, it terminates and returns a result. Every algorithm has a numerical domain. If the input to some algorithm is not a single natural number, then the numerical domain of this algorithm is the empty set. Otherwise, the numerical domain is the set of those natural numbers on which the algorithm does not crash and does not go into an infinite loop.

It turns out that each numerical domain is effectively enumerable. In fact, the converse is also true, according to the following theorem:

Capturing numerical properties in a formal language of arithmetic

Peter Smith starts Chapter 4 by describing L_A, a formal language that is at the core of several AFTs (axiomatized formal theories) of arithmetic. Then Smith explains what it means for a formal language of arithmetic to "express" a numerical property and the stronger notion of "capturing" a numerical property.

Here is the definition of L_A:

Formal systems or axiomatized formal theories

In chapter 3, Peter Smith defines formal systems or, as he calls them, axiomatized formal theories (I will use AFT as an abbreviation for this phrase).

A theory T is an AFT if...

Effective computability, decidability and enumerability

In Chapter 2, Smith covers familiar ground. So this post will be short. Here is a quick summary, section by section.

Section 1 reviews terminology pertaining to functions, namely the notions of domain and range, as well as special cases of functions, namely injective (or one-to-one) functions, surjective (or onto) functions and bijective functions (or one-to-one correspondences).

Peter Smith's overview of Gödel's incompleteness theorems

Finally! As was my initial goal, I now turn my attention to Peter Smith's book on the proof of Gödel's incompleteness theorems (by the way, I own the first edition of his book; so that is the one I will be referring to). I did not expect to spend that much time on Nagel and Newman's book. But it was worthwhile in getting the big picture.

Chapter 1 is an introductory and user-friendly discussion of topics that were mentioned in earlier posts, such as basic arithmetic, formal systems, (in)completeness, consistency, the statement of Gödel's incompleteness theorems and some of their implications. Therefore, in this post, I will just highlight the points where Smith provides new information or has a different perspective.

Proof sketch of Gödel's incompleteness theorems

In this post, I will follow the outline of the proof given in Section VII of Nagel and Newman's book. Recall that:

• a formal system F is consistent if there is no well-formed formula (wff) w such that F proves both w and ¬ w, and
• a formal system is (semantically) complete if it can prove all of the true wff's that it can express.

Now, Gödel's first incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic is both incomplete and "incompletable."

and Gödel's second incompleteness theorem can be paraphrased as:

Any consistent formal system that is expressive enough to model arithmetic cannot prove its own consistency.

According to Nagel and Newman, a proof of the first theorem can be sketched in 4 steps:

Mappings and the arithmetization of meta-mathematics

In an earlier post, we discussed mappings in general and then described Gödel numbering, which is a mapping between the set of well-formed formulas (wff's) in a formal system and the set of positive integers.

In part B of section VII, Nagel and Newman describe a more interesting mapping used in Gödel's proof. In this mapping, the domain is the set of meta-mathematical statements about structural properties of wff's, while the co-domain is the set of wff's. This post describes how this mapping enabled Gödel to arithmetize meta-mathematics.

Mappings and Gödel numbering

Section VI of Nagel and Newman's book describes mappings. A mapping is an operation that applies to two sets called the domain and the co-domain. More specifically, a mapping associates to each element of the domain one or more elements of the co-domain.