Robinson arithmetic is a weak incomplete arithmetic theory.

Definition

Robinson arithmetic has seven axioms on a constant term symbol \(0\) and three function symbols \(S\), \(+\), and \(\cdot\) of arity \(1\), \(2\), and \(2\) respectively. The axioms are:

  • \(Sx \neq 0\) (0 is not the successor of any number.)
  • \((Sx = Sy) \rightarrow x = y\) (If the successor of x is identical to the successor of y, then x and y are identical.)
  • \(y = 0 \lor \exists x (Sx = y)\) (Every number is either 0 or the successor of some number.)
  • \(x + 0 = x\)
  • \(x + Sy = S(x+y)\)
  • \(x \cdot 0 = 0\)
  • \(x \cdot Sy = (x \cdot y) + x\)

Semantics

The standard model \(\mathbb{N}\) of Peano arithmetic forms a model of Robinson arithmetic with respect to the following interpretation:

Unlike Peano arithmetic, Robinson arithmetic does not prove the induction schema. In particular, the existence of the maximum element with respect to the ordering \(x < y\) given as \(\exists z(y = x+S(z))\), which is inconsistent with the induction schema, is consistent with Robinson arithmetic. For example, \(\mathbb{N} \cup \{\)\(\omega\)\(\}\) also forms a model of Robinson arithmetic with respect to a natural extension of the interpretations.

See also

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\zeta,\Sigma,\gamma\) (ordinals on infinite time Turing machine) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Buchholz's function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(V\) · \(L\) · \(\textrm{On}\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Community content is available under CC-BY-SA unless otherwise noted.