*L*, that was described earlier.

_{A}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*, together with the interpretation_{A}*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 successor.

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*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_{A}*I*with two new elements_{A}*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

And, sure enough, Q can do that. For example, Q

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.

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.

## No comments:

## Post a Comment