Robinson arithmetic
Encyclopedia
In mathematics
, Robinson arithmetic
, or Q, is a finitely axiomatized fragment of Peano arithmetic (PA), first set out in R. M. Robinson (1950). Q is essentially PA without the axiom schema
of induction
. Since Q is weaker than PA, it is incomplete
. Q is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable and essentially undecidable
.
with identity
, denoted by infix '='. The individuals, called natural number
s, are members of a set called N with a distinguished member 0, called zero. There are three operation
s over N:
The following axiom
s for Q are Q1–Q7 in Burgess (2005: 56), and are also the first seven axioms of second order arithmetic. Variables
not bound by an existential quantifier are bound by an implicit universal quantifier.
The usual strict total order
on N, "less than" (denoted by "<"), can be defined in terms of addition via the rule
(Burgess 2005:230, fn. 24).
Taking "<" as primitive requires adding four axioms to (1)–(7) above:
of Q is the natural numbers and their usual arithmetic. Hence addition
and multiplication
have their customary meaning, identity is equality, and 0 is the natural number zero
.
Q, like Peano arithmetic, has nonstandard models
of all infinite cardinalities. However, unlike Peano arithmetic, Tennenbaum's theorem
does not apply to Q, and it has computable non-standard models. For instance, there is a computable model of Q consisting of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic.
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 (Burgess 2005:56).
Q is interpretable in a fragment of Zermelo's
axiomatic set theory, consisting of extensionality
, existence of the empty set
, and the axiom of adjunction
. This theory is S' in Tarski et al. (1953: 34) and ST in Burgess (2005: 90-91; 223). See general set theory
for 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, and so, all computable function
s are representable in Q (Mendelson 1997: Th. 3.33). The conclusion of Gödel's second incompleteness theorem also holds for Q: no consistent recursively axiomatized extension of Q can prove its own consistency, even if we additionally restrict Gödel numbers of proofs to a definable cut (Bezboruah and Shepherdson 1976; Pudlák 1985; Hájek & Pudlák 1993:387).
The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of Q were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that Q is incomplete and undecidable. This indicates 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
.
Gödel's theorems do not hold when any one of the seven axioms above is dropped. These fragments of Q remain undecidable, but they are no longer essentially undecidable: they have consistent decidable extensions, as well as uninteresting models (i.e., models which do not extend the standard natural numbers).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Robinson arithmetic
Robinson arithmetic
In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in R. M. Robinson . Q is essentially PA without the axiom schema of induction. Since Q is weaker than PA, it is incomplete...
, or Q, is a finitely axiomatized fragment of Peano arithmetic (PA), first set out in R. M. Robinson (1950). Q is essentially PA without the axiom schema
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
of induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
. Since Q is weaker than PA, it is incomplete
Complete theory
In mathematical logic, a theory is complete if it is a maximal consistent set of sentences, i.e., if it is consistent, and none of its proper extensions is consistent...
. Q is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable and essentially undecidable
Decidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
.
Axioms
The background logic of Q is first-order logicFirst-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
with identity
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
, denoted by infix '='. The individuals, called natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, are members of a set called N with a distinguished member 0, called zero. There are three operation
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....
s over N:
- A unary operationUnary operationIn mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
called successor and denoted by prefix S; - Two binary operationBinary operationIn mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
s, additionAdditionAddition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
and multiplicationMultiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
, denoted by infix + and by concatenationConcatenationIn computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
, respectively.
The following axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s for Q are Q1–Q7 in Burgess (2005: 56), and are also the first seven axioms of second order arithmetic. Variables
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
not bound by an existential quantifier are bound by an implicit universal quantifier.
- Sx ≠ 0
- 0 is not the successor of any number.
- (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 functionInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
whose domainDomain (mathematics)In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
is N) needed for non-triviality. The converse of (2) follows from the properties of identity.
- 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
- y=0 ∨ ∃x (Sx = y)
- Every number is either 0 or the successor of some number. The axiom schemaAxiom schemaIn mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
of mathematical inductionMathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
present in arithmetics stronger than Q turns this axiom into a theorem.
- Every number is either 0 or the successor of some number. The axiom schema
- x + 0 = x
- x + Sy = S(x + y)
- (4) and (5) are the recursive definitionRecursive definitionIn mathematical logic and computer science, a recursive definition is used to define an object in terms of itself ....
of additionAdditionAddition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
.
- (4) and (5) are the recursive definition
- x0 = 0
- xSy = (xy) + x
- (6) and (7) are the recursive definitionRecursive definitionIn mathematical logic and computer science, a recursive definition is used to define an object in terms of itself ....
of multiplicationMultiplicationMultiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
.
- (6) and (7) are the recursive definition
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 strict total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
on N, "less than" (denoted by "<"), can be defined in terms of addition via the rule
(Burgess 2005:230, fn. 24).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).
Metamathematics
On the metamathematics of Q, see Boolos et al. (2002: chpt. 14), Tarski, Mostowski, and Robinson (1953), Smullyan (1991), Mendelson (1997: 201-03), and Burgess (2005: §§1.5a, 2.2). The intended interpretationIntended interpretation
One who constructs a syntactical system usually has in mind from the outset some interpretation of this system. While this intended interpretation can have no explicit indication in the syntactical rules - since these rules must be strictly formal - the author's intention respecting...
of Q is the natural numbers and their usual arithmetic. Hence addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
and multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
have their customary meaning, identity is equality, and 0 is the natural number zero
0 (number)
0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
.
Q, like Peano arithmetic, has nonstandard models
Non-standard model
In model theory, a discipline within mathematical logic, a non-standard model is a model of a theory that is not isomorphic to the intended model . If the intended model is infinite and the language is first-order, then the Löwenheim-Skolem theorems guarantee the existence of non-standard models...
of all infinite cardinalities. However, unlike Peano arithmetic, Tennenbaum's theorem
Tennenbaum's theorem
Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of Peano arithmetic can be recursive.-Recursive structures for PA:...
does not apply to Q, and it has computable non-standard models. For instance, there is a computable model of Q consisting of integer-coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic.
The defining characteristic of Q is the absence of the axiom scheme of induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
. 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 (Burgess 2005:56).
Q is interpretable in a fragment of Zermelo's
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...
axiomatic set theory, consisting of extensionality
Extensionality
In logic, extensionality, or extensional equality refers to principles that judge objects to be equal if they have the same external properties...
, existence of the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, and the axiom of adjunction
General set theory
General set theory is George Boolos's name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.-Ontology:...
. This theory is S' in Tarski et al. (1953: 34) and ST in Burgess (2005: 90-91; 223). See general set theory
General set theory
General set theory is George Boolos's name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.-Ontology:...
for 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
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
is representable in PA. The only use this proof makes of the PA axiom schema of induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
is to prove a statement that is axiom (3) above, and so, all computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
s are representable in Q (Mendelson 1997: Th. 3.33). The conclusion of Gödel's second incompleteness theorem also holds for Q: no consistent recursively axiomatized extension of Q can prove its own consistency, even if we additionally restrict Gödel numbers of proofs to a definable cut (Bezboruah and Shepherdson 1976; Pudlák 1985; Hájek & Pudlák 1993:387).
The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of Q were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that Q is incomplete and undecidable. This indicates that the incompleteness and undecidability of PA cannot be blamed on the only aspect of PA differentiating it from Q, namely the axiom schema
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
of induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
.
Gödel's theorems do not hold when any one of the seven axioms above is dropped. These fragments of Q remain undecidable, but they are no longer essentially undecidable: they have consistent decidable extensions, as well as uninteresting models (i.e., models which do not extend the standard natural numbers).
See also
- General set theoryGeneral set theoryGeneral set theory is George Boolos's name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.-Ontology:...
- Gentzen's consistency proofGentzen's consistency proofGentzen's consistency proof is a result of proof theory in mathematical logic. It "reduces" the consistency of a simplified part of mathematics, not to something that could be proved , but to clarified logical principles.-Gentzen's theorem:In 1936 Gerhard Gentzen proved the consistency of...
- Gödel's Incompleteness Theorem
- List of first-order theories
- Peano axiomsPeano axiomsIn mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
- Second-order arithmeticSecond-order arithmeticIn mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. It was introduced by David Hilbert and Paul Bernays in their...
- Set-theoretic definition of natural numbersSet-theoretic definition of natural numbersSeveral ways have been proposed to define the natural numbers using set theory.- The contemporary standard :In standard, Zermelo-Fraenkel set theory the natural numbers...