nLab
Robinson arithmetic

Robinson arithmetic

Robinson arithmetic

Idea

Robinson arithmetic (after Raphael M. Robinson) is a finitely axiomatized weakening of Peano arithmetic in which the induction schema is dropped and minimal axioms remain.

Definition

Robinson arithmetic, also denoted by Q, is a first-order theory whose signature is that of first-order Peano arithmetic: it consists of a constant 00, an unary function symbol ss, and binary function symbols +,+, \cdot. The axioms are

  1. x¬s(x)=0\forall_x \neg s(x) = 0;

  2. x,ys(x)=s(y)x=y\forall_{x, y} s(x) = s(y) \Rightarrow x = y;

  3. xx=0 yx=s(y)\forall_x x = 0 \vee \exists_y x = s(y);

  4. xx+0=x\forall_x x + 0 = x,

  5. x,yx+s(y)=s(x+y)\forall_{x, y} x + s(y) = s(x+y);

  6. xx0=0\forall_x x \cdot 0 = 0;

  7. x,yxs(y)=xy+x\forall_{x, y} x \cdot s(y) = x \cdot y + x.

There is no induction scheme.

One sometimes adds axioms for order; however, this is also definable. (Citation in Wikipedia; I can't quite make it work.)

Theorems

Despite the considerable weakening of what can be proved, the formulas are the same as in Peano arithmetic, and all the background number theory (the Chinese remainder theorem? and the like) needed to develop Gödel codings, incompleteness theorems, and so on is still there. In some sense the axioms are a minimal set needed to carry out this program (and in fact this was in large part the motivation for Robinson).

Models

Unlike the case for Peano arithmetic, system QQ admits tractable computable nonstandard? models.

The simplest consists of a single nonstandard number \infty (in addition to all of the standard numbers, which exist in every model), with the rules (where nn is a standard number):

  • s()=s(\infty) = \infty,
  • n+,+n,+=n + \infty, \infty + n, \infty + \infty = \infty,
  • 0,0=00 \cdot \infty, \infty \cdot 0 = 0, s(n),s(n),=s(n) \cdot \infty, \infty \cdot s(n), \infty \cdot \infty = \infty.

References

Last revised on December 3, 2019 at 18:04:32. See the history of this page for a list of all contributions to it.