# Robinson arithmetic

This article includes a list of general references, but it lacks sufficient corresponding inline citations. (August 2021) |

In

^{[1]}It is usually denoted

**Q**.

**Q**is almost

^{[clarification needed]}PA without the axiom schema of mathematical induction.

**Q**is weaker than PA but it has the same language, and both theories are incomplete.

**Q**is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable and essentially undecidable

## Axioms

The

**N**:

- A prefix
*S*; - Two binary operations, addition and multiplication, denoted by infix
**+**and**·**, respectively.

The following

*Sx*≠**0****0**is not the successor of any number.

- (
*Sx*=*Sy*) →*x*=*y*- If the successor of
*x*is identical to the successor of*y*, then*x*and*y*are identical. (1) and (2) yield the minimum of facts about**N**(it is anconverseof (2) follows from the properties of identity.

- If the successor of
*y*=**0**∨ ∃*x*(*Sx*=*y*)- Every number is either
**0**or the successor of some number. The axiom schema of mathematical induction present in arithmetics stronger than**Q**turns this axiom into a theorem.

- Every number is either
*x*+**0**=*x**x*+*Sy*=*S*(*x*+*y*)- (4) and (5) are the recursive definition of addition.

*x*·**0**=**0***x·Sy*= (*x·y*) +*x*- (6) and (7) are the recursive definition of multiplication.

### Variant axiomatizations

The axioms in Robinson (1950) are (1)–(13) in Mendelson (2015, pp. 202–203). The first 6 of Robinson's 13 axioms are required only when, unlike here, the background logic does not include identity.

The usual strict total order on **N**, "less than" (denoted by "<"), can be defined in terms of addition via the rule *x* < *y* ↔ ∃*z* (*Sz* + *x* = *y*). Equivalently, we get a definitional conservative extension of **Q** by taking "<" as primitive and adding this rule as an eighth axiom; this system is termed "*Robinson arithmetic* **R**" in Boolos, Burgess & Jeffrey (2002, Sec 16.4).

A different extension of **Q**, which we temporarily call **Q+**, is obtained if we take "<" as primitive and add (instead of the last definitional axiom) the following three axioms to axioms (1)–(7) of **Q**:

- ¬(
*x*< 0) *x*<*Sy*↔ (*x*<*y*∨*x*=*y*)*x*<*y*∨*x*=*y*∨*y*<*x*

**Q+** is still a conservative extension of **Q**, in the sense that any formula provable in **Q+** not containing the symbol "<" is already provable in **Q**. (Adding only the first two of the above three axioms to **Q** gives a conservative extension of **Q** that is equivalent to what Burgess (2005, p. 56) calls **Q***. See also Burgess (2005, p. 230, fn. 24), but note that the second of the above three axioms cannot be deduced from "the pure definitional extension" of **Q** obtained by adding only the axiom *x* < *y* ↔ ∃*z* (*Sz* + *x* = *y*).)

Among the axioms (1)–(7) of **Q**, axiom (3) needs an inner existential quantifier. Shoenfield (1967, p. 22) gives an axiomatization that has only (implicit) outer universal quantifiers, by dispensing with axiom (3) of **Q** but adding the above three axioms with < as primitive. That is, Shoenfield's system is **Q+** minus axiom (3), and is strictly weaker than **Q+**, since axiom (3) is independent of the other axioms (for example, the ordinals less than forms a model for all axioms except (3) when *Sv* is interpreted as *v* + 1). Shoenfield's system also appears in Boolos, Burgess & Jeffrey (2002, Sec 16.2), where it is called the "*minimal arithmetic*" (also denoted by **Q**). A closely related axiomatization, that uses "≤" instead of "<", may be found in Machover (1996, pp. 256–257).

## Metamathematics

On the metamathematics of **Q** see

Any model (structure) that satisfies all axioms of **Q** except possibly axiom (3) has a unique submodel ("the standard part") isomorphic to the standard natural numbers (**N**, +, ·, S, 0). (Axiom (3) need not be satisfied; for example the polynomials with non-negative integer coefficients forms a model that satisfies all axioms except (3).)

**Q**, like

**Q**, and it has computable non-standard models. For instance, there is a computable model of

**Q**consisting of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic.

A notable characteristic of **Q** is the absence of the axiom scheme of induction. Hence it is often possible to prove in **Q** every specific instance of a fact about the natural numbers, but not the associated general theorem. For example, 5 + 7 = 7 + 5 is provable in **Q**, but the general statement *x* + *y* = *y* + *x* is not. Similarly, one cannot prove that *Sx* ≠ *x*. ^{[2]} A model of **Q** that fails many of the standard facts is obtained by adjoining two distinct new elements *a* and *b* to the standard model of natural numbers and defining *Sa* = *a*, *Sb* = *b*, *x* + *a* = *b* and *x* + *b* = *a* for all *x*, *a* + *n* = *a* and *b* + *n* = *b* if *n* is a standard natural number, *x*·0 = 0 for all *x*, *a*·*n* = *b* and *b*·*n* = *a* if *n* is a non-zero standard natural number, *x*·*a* = *a* for all *x* except *x* = *a*, *x*·*b* = *b* for all *x* except *x* = *b*, *a*·*a* = *b*, and *b*·*b* = *a*.^{[3]}

**Q** is interpretable in a fragment of

**Q** is a finitely axiomatized

**Q**axioms (1)–(7) above by noting just what PA axioms are required

^{[4]}to prove that every computable function is representable in PA.

^{[5]}The only use this proof makes of the PA axiom schema of induction is to prove a statement that is axiom (3) above, and so, all computable functions are representable in

**Q**.

^{[6]}

^{[7]}

^{[8]}The conclusion of Gödel's second incompleteness theorem also holds for

**Q**: no consistent recursively axiomatized extension of

**Q**can prove its own consistency, even if we additionally restrict Gödel numbers of proofs to a definable cut.

^{[9]}

^{[10]}

^{[11]}

The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of **Q** were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that **Q** is incomplete and undecidable. This indicates that the incompleteness and undecidability of PA cannot be blamed on the only aspect of PA differentiating it from **Q**, namely the axiom schema of induction.

Gödel's theorems do not hold when any one of the seven axioms above is dropped. These fragments of **Q** remain undecidable, but they are no longer essentially undecidable: they have consistent decidable extensions, as well as uninteresting models (i.e., models that are not end-extensions of the standard natural numbers).^{[citation needed]}

## See also

- Gentzen's consistency proof
- Gödel's incompleteness theorems
- List of first-order theories
- Peano axioms
- Presburger arithmetic
- Skolem arithmetic
- Second-order arithmetic
- Set-theoretic definition of natural numbers
- General set theory

## References

**^**Robinson 1950.**^**Burgess 2005, p. 56.**^**Boolos, Burgess & Jeffrey 2002, Sec 16.4.**^**Mendelson 2015, p. 188, Proposition 3.24.**^**A function is said to be*representable*in if there is a formula such that for all**^**Odifreddi 1989.**^**Mendelson 2015, p. 203, Proposition 3.33.**^**Rautenberg 2010, p. 246.**^**Bezboruah & Shepherdson 1976.**^**Pudlák 1985.**^**Hájek & Pudlák 1993, p. 387.

## Bibliography

- Bezboruah, A.; Shepherdson, John C. (June 1976). "Gödel's Second Incompleteness Theorem for Q". JSTOR 2272251.
- .
- .
- Hájek, Petr; Pudlák, Pavel (1993).
*Metamathematics of first-order arithmetic*(2nd ed.).Springer-Verlag. - Jones, James P.; Shepherdson, John C. (1983). "Variants of Robinson's essentially undecidable theoryR".
*Archiv für mathematische Logik und Grundlagenforschung*.**23**: 61–64. . - Lucas, John R.
*Conceptual Roots of Mathematics*. Routledge. - Machover, Moshé (1996).
*Set Theory, Logic, and Their Limitation*. Cambridge University Press. - ISBN 9781482237726.
- .
- Pudlák, Pavel (June 1985). "Cuts, consistency statements and interpretations".
*.* - ..
- Robinson, Raphael M. (1950). "An Essentially Undecidable Axiom System".
*Proceedings of the International Congress of Mathematics*: 729–730. - Shoenfield, Joseph R. (1967).
*Mathematical logic*. Addison Wesley. (Reprinted by Association for Symbolic Logic and A K Peters in 2000). - Smullyan, Raymond (1991).
*Gödel's Incompleteness Theorems*. Oxford University Press. - Tarski, Alfred; Mostowski, Andrzej; Robinson, Raphael M. (1953).
*Undecidable theories*. North Holland. - Vaught, Robert L. (1966). "On a Theorem of Cobham Concerning Undecidable Theories".
*Studies in Logic and the Foundations of Mathematics*.**44**: 14–25.ISBN 9780804700962.