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:

• The interpreted language of Robinson Arithmetic is simply the language L_A, together with the interpretation I_A. 
• The deductive apparatus (inference rules) of Robinson Arithmetic will be some version of first-order logic with identity. We'll settle on a specific logic in a future post.
• The axioms of Robinson Arithmetic are:
• Axiom 1: ∀x (0 ≠ Sx)
• Axiom 2: ∀x∀y (Sx = Sy → x = y)
• Axiom 3: ∀x (x ≠ 0 → ∃y (x = Sy))
• Axiom 4: ∀x (x + 0 = x)
• Axiom 5: ∀x∀y (x + Sy = S(x + y))
• Axiom 6: ∀x (x × 0 = 0)
• Axiom 7: ∀x∀y (x × Sy = (x × y) + x)

Each axiom above, except for axiom 3, is a direct rewriting in first-order logic of a schema in the definition of BA. Axiom 3 is added to make sure that there is no element besides zero that does not have a predecessor.

Then Smith proves the following theorem:

 Q is not negation-complete.

Proof sketch: Let φ be the sentence ∀x (0 + x = x)

• Q is sound, since its axioms are all true and its logic is truth-preserving.
• Q cannot derive φ: 
• One way to prove this fact is to come up with an alternative interpretation for L_A that makes Q's axioms true but φ false. Since Q is sound, it cannot derive φ. (Note: The alternative interpretation used in Smith's proof is an extension of I_A with two new elements a and b in the domain such that a is its own successor, b is its own successor, and addition and multiplication are extended in such a way that 0 + a is equal to b and 0 + b is equal to a, thereby falsifying φ.)
• Q cannot derive ¬ φ:
• This is because Q is sound and ¬ φ is false under the original interpretation I_A.

So this chapter contains yet another proof of incompleteness that is much simpler than Gödel's proof.

Since φ represents a trivial fact about addition that Q cannot prove, it must be the case that Q is a weak theory of arithmetic.

Nevertheless, Q is interesting because Smith promises to prove (in a future chapter) that Q is sufficiently strong. Recall that this property is defined in terms of capturing properties and relations using case-by-case proofs.

And, sure enough, Q can do that. For example, Q can derive all of the sentences 0 + 0 = 0, 0 + S0 = S0, 0 + SS0 = SS0, etc. It simply cannot derive the universally quantified sentence φ that covers this infinite set in one fell swoop.

Finally (for this chapter anyway), Smith points out that any consistent theory that extends Q will also be sufficiently strong and therefore negation incomplete.

The next chapter presents Robinson Arithmetic in much greater detail and will probably take us several posts to dissect.