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.
Contents |
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 unary function called successor and denoted by prefix S;
- Two binary operations, addition and multiplication, denoted by infix + and by concatenation, respectively;
- The distinguished member 0.
In the following axioms for Q, variables not bound by an existential quantifier are bound by a tacit universal quantifier.
- Sx ≠ 0
- 0 is not the successor of any number.
- x ≠ 0 → ∃y[Sy = x]
- Every nonzero number is the successor of some number. Hence N is an infinite set bounded from below by 0. The axiom schema of induction present in arithmetics stronger than Q turns this axiom into a theorem.
- (Sx = Sy) → x = y
- If the successor of x is identical to the successor of y, then x and y are identical. Hence S is an injective function. The converse of (3) follows from the properties of identity.
- x + 0 = x
- x + Sy = S(x + y)
- x0 = 0
- xSy = (xy) + x
- (6) and (7) are the recursive definition of multiplication.
Variations on the axioms
The above axioms are Q1-Q7 in Boolos and Jeffrey (2002: 158). The axioms in Robinson (1950) are (1)-(13) in Mendelson (1997: 201). The first 6 of Robinson's 13 axioms are required only when, unlike here, the background logic does not include identity. Machover (1996: 256-57) dispenses with (2) from the list above. Additional axioms are required if "less than" is taken as a primitive binary relation.
Metamathematics
The definitive treatment of Q and its metamathematics is probably Boolos et al (2002: chpt. 14). Also see Tarski, Mostowski, and Robinson (1953), Smullyan (1991), 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 natural 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. Similarly, one cannot prove that Sx ≠ x, since the cardinal numbers (including infinite cardinals) are a model of Q.[1] 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 like Peano arithmetic is incomplete and incompletable in the sense of Gödel's Incompleteness Theorems, and 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. However Gödel's Incompleteness Theorem does not hold for the seven fragments of Q formed by dropping any one of the seven axioms above. In fact, these 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. Q can be derived from a fragmentary axiomatic set theory consisting of extensionality, existence of null set, and the axiom of adjunction. This theory is S' in Tarski et al (1953: 34). See general set theory for more details.
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
- list of first-order theories
- Second-order arithmetic
- Peano axioms
- Gödel's Incompleteness Theorem
- Set-theoretic definition of natural numbers
- general set theory
Notes
- ^ Burgess, p. 56
References
- George Boolos, John P. Burgess, and Richard Jeffrey, 2002. Computability and Logic, 4th ed. Cambridge Univ. Press.
- John P. Burgess, Fixing Frege. Princeton University Press, 2005.
- Lucas, J. R., 1999. Conceptual Roots of Mathematics. Routledge. Mulls over the philosophical implications of Q.
- Machover, Moshe, 1996. Set Theory, Logic, and Their Limitation. Cambridge Univ. Press. Sets out the elementary metamathematics of a system very similar to Q.
- Mendelson, Elliott, 1997. Introduction to Mathematical Logic, 4th ed. Chapman & Hall.
- R. M. Robinson, 1950, "An Essentially Undecidable Axiom System" in Proceedings of the International Congress of Mathematics: 729-730.
- Raymond Smullyan, 1991. Gödel's Incompleteness Theorems. Oxford Univ. Press.
- Swoyer, C., 2004, "First-Order Theories." Source for the above axiom system.
- Alfred Tarski, A. Mostowski, and R. M. Robinson, 1953. Undecidable theories. North Holland.
