|
In mathematics, Robinson arithmetic, or Q, is a fragment of the theory of the natural numbers, set out in R. M. Robinson (1950). Q is essentially Peano arithmetic without the axiom schema of induction.
Axioms The background logic of Q is first order logic with identity, denoted by infix '='. The individuals, called "numbers," are members of a set called N. There are four operations over N: The above axioms are Q1-Q7 in Boolos and Jeffrey (2002: 158). Robinson's (1950) axioms are (1)-(13) in Mendelson (1997: 201). Robinson's axioms (1)-(6) are required only when, unlike here, the background logic does not include identity. Machover (1996: 256-57) dispenses with (2) above. The entry second-order arithmetic includes four more axioms for the primitive binary relation "less than." Metamathematics The definitive treatment of Q and its metamathematics is probably Boolos and Jeffrey (2002: chpt. 14). Also see Tarski et al (1953) (Tarski and Robinson were colleagues) and Swoyer (2004: 2.5). The intended interpretation (standard model) of Q is the natural numbers and their usual arithmetic. Hence addition and multiplication have their customary meaning, identity is equality, Sx = x+1, and 0 is the number zero.Q, like the Peano axioms, has nonstandard models of all infinite cardinalities. In Q, it is often possible to prove every concrete 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. Q is a fascinating example of a finitely axiomatized first order theory that is considerably weaker than Peano arithmetic, and whose axioms contain only one explicit existential quantifier, yet is also, like Peano arithmetic, incomplete and incompletable in the sense of Gödel's Incompleteness Theorems, and also essentially undecidable. Gödel's theorems only apply to axiomatic systems that define sufficient arithmetic to carry out the coding constructions (of which Godel numbering forms a part) needed for the proof of Gödel's first theorem. "Sufficient arithmetic" is precisely those facts about addition and multiplication over the natural numbers that Q formalizes. Moreover, all computable functions are representable in Q. Q proves that the incompleteness and undecidability of Peano arithmetic cannot be blamed on the only aspect of that arithmetic differentiating it from Q, namely the axiom schema of induction. But omit any one of the seven axioms above and Gödel's Theorem ceases to hold. In fact, the resulting seven fragmentary theories are of no metamathematical interest: they either have no interesting models or are decidable. (For example, removing either (6) or (7) yields, in effect, Presburger arithmetic minus induction.) Just why these seven fragments of Q are uninteresting when Q itself is incomplete and incompletable (and hence very interesting), is not known. For more on the metamathematics of Q and related "weak arithmetics," see second-order arithmetic. Addition eliminable See Boolos et al (2002: 219). Let a=Sx, b=Sy, and c=SSz. Then addition is definable in terms of multiplication and successor as follows: x+y=z iff S(ac) S(bc) = S(S(ab) cc). For this reason, Skolem arithmetic is not simply a Dedekind algebra with recursively defined multiplication; successor must be discarded as well. The metamathematics of this minimalist system have yet to be explored. See also | ||||||||
|
| |||||||||
 |
|
| |