 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(August 2021) (Learn how and when to remove this message) |
Inmathematics,Robinson arithmetic is afinitely axiomatized fragment of first-orderPeano arithmetic (PA), first set out byRaphael M. Robinson in 1950.[1] It is usually denotedQ.
Q is PA without theaxiom schema ofmathematical induction.Q is weaker than PA but it has the same language, and both theories areincomplete.Q is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable andessentially undecidable.
Thebackground logic ofQ isfirst-order logic with identity, denoted by infix '='. The individuals, callednatural numbers, are members of aset calledN with a distinguished member0, calledzero. There are threeoperations overN:
The followingaxioms forQ are Q1–Q7 inBurgess (2005, p. 42) (cf. also the axioms offirst-order arithmetic).Variables not bound by anexistential quantifier are bound by an implicituniversal quantifier.
The axioms inRobinson (1950) are (1)–(13) inMendelson (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 stricttotal order onN, "less than" (denoted by "<"), can be defined in terms of addition via the rulex <y ↔ ∃z (Sz +x =y). Equivalently, we get a definitional conservative extension ofQ by taking "<" as primitive and adding this rule as an eighth axiom; this system is termed "Robinson arithmeticR" inBoolos, Burgess & Jeffrey (2002, Sec 16.4).
A different extension ofQ, which we temporarily callQ+, is obtained if we take "<" as primitive and add (instead of the last definitional axiom) the following three axioms to axioms (1)–(7) ofQ:
Q+ is still a conservative extension ofQ, in the sense that any formula provable inQ+ not containing the symbol "<" is already provable inQ. (Adding only the first two of the above three axioms toQ gives a conservative extension ofQ that is equivalent to whatBurgess (2005, p. 56) callsQ*. See alsoBurgess (2005, p. 230, fn. 24), but note that the second of the above three axioms cannot be deduced from "the pure definitional extension" ofQ obtained by adding only the axiomx <y ↔ ∃z (Sz +x =y).)
Among the axioms (1)–(7) ofQ, 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) ofQ but adding the above three axioms with < as primitive. That is, Shoenfield's system isQ+ minus axiom (3), and is strictly weaker thanQ+, since axiom (3) is independent of the other axioms (for example, theordinals less than forms a model for all axioms except (3) whenSv is interpreted asv + 1). Shoenfield's system also appears inBoolos, Burgess & Jeffrey (2002, Sec 16.2), where it is called the "minimal arithmetic" (also denoted byQ). A closely related axiomatization, that uses "≤" instead of "<", may be found inMachover (1996, pp. 256–257).
On the metamathematics ofQ seeBoolos, Burgess & Jeffrey (2002, chpt. 16),Tarski, Mostowski & Robinson (1953),Smullyan (1991),Mendelson (2015, pp. 202–203) andBurgess (2005, §§1.5a, 2.2). Theintended interpretation ofQ is thenatural numbers and their usual arithmetic in whichaddition andmultiplication have their customary meaning, identity isequality,Sx =x + 1, and0 is the natural numberzero.
Any model (structure) that satisfies all axioms ofQ 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 thepolynomials with non-negative integer coefficients forms a model that satisfies all axioms except (3).)
Q, likePeano arithmetic, hasnonstandard models of all infinitecardinalities. However, unlike Peano arithmetic,Tennenbaum's theorem does not apply toQ, and it hascomputable non-standard models. For instance, there is a computable model ofQ consisting of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic.
A notable characteristic ofQ is the absence of the axiom scheme ofinduction. Hence it is often possible to prove inQ every specific instance of a fact about the natural numbers, but not the associated general theorem. For example, 5 + 7 = 7 + 5 is provable inQ, but the general statementx +y =y +x is not. Similarly, one cannot prove the general statementSx ≠x.[2] A model ofQ that fails many of the standard facts is obtained by adjoining two distinct new elementsa andb to the standard model of natural numbers and definingSa =a,Sb =b,x +a =b andx +b =a for allx,a +n =a andb +n =b ifn is a standard natural number,x·0 = 0 for allx,a·n =b andb·n =a ifn is a non-zero standard natural number,x·a =a for allx exceptx =a,x·b =b for allx exceptx =b,a·a =b, andb·b =a.[3]
Q is interpretable in a fragment ofZermelo'saxiomatic set theory, consisting ofextensionality, existence of theempty set, and theaxiom of adjunction. This theory is S' inTarski, Mostowski & Robinson (1953, p. 34) and ST inBurgess (2005, pp. 90–91, 223). Seegeneral set theory for more details.
Q is a finitely axiomatizedfirst-order theory that is considerably weaker thanPeano arithmetic (PA), and whose axioms contain only oneexistential quantifier. Yet like PA it is incomplete and incompletable in the sense ofGödel's incompleteness theorems, and essentially undecidable.Robinson (1950) derived theQ axioms (1)–(7) above by noting just what PA axioms are required[4] to prove that everycomputable function is representable in PA.[5] The only use this proof makes of the PA axiom schema ofinduction is to prove a statement that is axiom (3) above, and so, all computable functions are representable inQ.[6][7][8] The conclusion of Gödel's second incompleteness theorem also holds forQ: no consistent recursively axiomatized extension ofQ 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 whichGödel numbering forms a part). The axioms ofQ 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 thatQ is incomplete and undecidable. This indicates that the incompleteness and undecidability of PA cannot be blamed on the only aspect of PA differentiating it fromQ, namely theaxiom schema ofinduction.
Gödel's theorems do not hold when any one of the seven axioms above is dropped. These fragments ofQ 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]
{{cite book}}:|journal= ignored (help)| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list), paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language, syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
