Robinson arithmetic

From Wikipedia, the free encyclopedia

In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic (PA), first set out in Robinson (1950). Q is essentially PA without the axiom schema of induction. Even though Q is much weaker than PA, it is still incomplete in the sense of Gödel.

Contents

[edit] 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, with distinguished member 0. There are three operations over N:

The following axioms for Q are Q1-Q7 in Burgess (2005: 56), and the first seven basic axioms of second order arithmetic. Variables not bound by an existential quantifier are bound by an implicit universal quantifier.

  1. Sx ≠ 0
    • 0 is not the successor of any number.
  2. (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 an infinite set bounded by 0) and S (it is an injective function whose domain is N) needed for nontriviality. The converse of (2) follows from the properties of identity.
  3. y=0 ∨ ∃x[Sx = y]
    • Every number is either 0 or the successor of some number. The axiom schema of induction present in arithmetics stronger than Q turns this axiom into a theorem.
  4. x + 0 = x
  5. x + Sy = S(x + y)
  6. x0 = 0
  7. xSy = (xy) + x

[edit] Variant axiomatizations

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 axiom (3).

The usual total order on N, "less than" (denoted by infix "<"), can be defined in terms of addition as:

x<y \leftrightarrow \exist z[x+Sz=y].[1]

Taking "<" as primitive requires adding four axioms to (1)-(7) above:

  • ~(x<0)
  • 0=x ∨ 0<x
  • x<y ↔ (Sx<y ∨ Sx=y)
  • x<Sy ↔ (x<y ∨ x=y).

[edit] Metamathematics

On the metamathematics of Q, see Boolos et al (2002: chpt. 14), Tarski, Mostowski, and Robinson (1953), Smullyan (1991), Mendelson (1997: 201-03), Swoyer (2004: 2.5), and Burgess (2005: §§1.5a, 2.2). The intended interpretation 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.

The defining 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, since the cardinal numbers (including infinite cardinals) are a model of Q.[2]

Q is interpretable in a fragment of Zermelo's 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) and ST in Burgess (2005: 90-91; 223). General set theory has more details.

Q fascinates because it is a finitely axiomatized first-order theory that is considerably weaker than Peano arithmetic (PA), and whose axioms contain only one existential quantifier, yet like PA is incomplete and incompletable in the sense of Gödel's Incompleteness Theorems, and essentially undecidable. Robinson (1950) derived the Q axioms (1)-(7) above by noting just what PA axioms are required to prove (Mendelson 1997: Th. 3.24) that every computable function is representable in PA. The only use this proof makes of the PA axiom schema of induction is to prove a statement that is axiom (3) above.

Gödel's theorems only apply to axiomatic systems defining sufficient arithmetic to carry out the coding constructions (of which Gödel 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 (Mendelson 1997: Th. 3.33).

Q proves 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. However Gödel's Incompleteness Theorem does not hold when any one of the seven axioms above is dropped. In fact, these seven fragmentary theories are uninteresting; they either have no interesting models or are decidable. (For example, removing either axiom 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.

[edit] 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.

[edit] See also

[edit] Notes

  1. ^ Burgess (2005), p. 230, fn. 24.
  2. ^ Burgess (2005), p. 56.

[edit] References

  • George Boolos, John P. Burgess, and Richard Jeffrey, 2002. Computability and Logic, 4th ed. Cambridge Univ. Press.
  • Burgess, John P., 2005. Fixing Frege. Princeton University Press.
  • 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."
  • Alfred Tarski, A. Mostowski, and R. M. Robinson, 1953. Undecidable theories. North Holland.
Languages