- Robinson arithmetic
In

mathematics ,**Robinson arithmetic**, or**Q**, is a finitely axiomatized fragment ofPeano arithmetic (PA), first set out in Robinson (1950).**Q**is essentially PA without theaxiom schema of induction. Even though**Q**is much weaker than PA, it is still incomplete in the sense ofGödel .**Axioms**The background logic of

**Q**isfirst-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**:

*Aunary operation called successor and denoted by prefix "S";

*Twobinary operation s,addition andmultiplication , denoted by infix**+**and byconcatenation , respectively.The following

axiom s for**Q**are Q1-Q7 in Burgess (2005: 56), and the first seven basic axioms ofsecond order arithmetic .Variables not bound by anexistential quantifier are bound by an implicituniversal 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 aninfinite set bounded by**0**) and "S" (it is aninjective function whose domain is**N**) needed for nontriviality. The converse of (2) follows from the properties of identity.

# "y"=**0**∨ ∃"x" ["Sx" = "y"]

#* Every number is either**0**or the successor of some number. Theaxiom schema of induction present in arithmetics stronger than**Q**turns this axiom into a theorem.

# "x" +**0**= "x"

# "x" + "Sy" = S("x" + "y")

#* (4) and (5) are therecursive definition ofaddition .

# "x**"0**=**0**

# "xSy" = ("xy") + "x"

#* (6) and (7) are therecursive definition ofmultiplication .**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:$xexist\; z\; [x+sz="y]"\; .\; math>\; [$

*Burgess (2005), p. 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), [*http://www.ou.edu/ouphil/faculty/chris/foltheories.pdf Swoyer*] (2004: 2.5), and Burgess (2005: §§1.5a, 2.2). Theintended interpretation of**Q**is thenatural numbers and their usual arithmetic. Henceaddition andmultiplication have their customary meaning, identity is equality, "Sx" = "x"+1, and**0**is the natural number zero.**Q**, like thePeano 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**. [*Burgess (2005), p. 56.*]**Q**is interpretable in a fragment of Zermelo'saxiomatic set theory , consisting ofextensionality , existence ofnull 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 thanPeano arithmetic (PA), and whose axioms contain only oneexistential quantifier , yet like PA is incomplete and incompletable in the sense ofGödel's Incompleteness Theorem s, and essentiallyundecidable . 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 everycomputable 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, allcomputable function s are representable in**Q**(Mendelson 1997: Th. 3.33).**Q**proves that theincomplete ness and undecidability of PA cannot be blamed on the only aspect of PA differentiating it from**Q**, namely theaxiom schema of induction. HoweverGö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 aredecidable . (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.**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.**ee also***

General set theory

*Gödel's Incompleteness Theorem

*List of first-order theories

*Peano axioms

*Second-order arithmetic

*Set-theoretic definition of natural numbers **Notes****References***

George Boolos , John P. Burgess, andRichard 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, " [*http://www.ou.edu/ouphil/faculty/chris/foltheories.pdf First-Order Theories.*] "

*Alfred Tarski ,A. Mostowski , andR. M. Robinson , 1953. "Undecidable theories". North Holland.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Second-order arithmetic**— In mathematical logic, second order arithmetic is a collection of axiomatic systems that formalize the natural numbers and sets thereof. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics. The… … Wikipedia**Raphael M. Robinson**— Raphael Mitchel Robinson (November 2 1911, National City California January 27 1995. Berkeley California) was an American mathematician.Born in National City, California, Robinson was the youngest of four children of a lawyer and a teacher. He… … Wikipedia**Presburger arithmetic**— is the first order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who published it in 1929. It is not as powerful as Peano arithmetic because it omits multiplication.OverviewThe language of Presburger… … Wikipedia**Julia Robinson**— Infobox Scientist name = Julia Hall Bowman Robinson box width = imagesize = 200px caption = Julia Robinson in 1975 birth date = December 8, 1919 birth place = St. Louis, Missouri, United States death date = July 30, 1985 death place = Oakland,… … Wikipedia**Sugar Ray Robinson**— Pour les articles homonymes, voir Robinson. Sugar Ray Robinson Sugar Ray Robinson 1965 Fiche d’identité … Wikipédia en Français**Julia Robinson**— Julia Hall Bowman Robinson, geboren als Julia Bowman, (* 8. Dezember 1919, in St. Louis in Missouri; † 30. Juli 1985 in Oakland, Kalifornien) war eine US amerikanische Mathematikerin, die sich mit mathematischer Logik beschäftigte … Deutsch Wikipedia**Mission Robinson**— Missions of the Bolivarian Revolution food housing medicine Barrio Adentro · Plan Bolivar 2000 Hábitat · Mercal education … Wikipedia**List of first-order theories**— In mathematical logic, a first order theory is given by a set of axioms in somelanguage. This entry lists some of the more common examples used in model theory and some of their properties. PreliminariesFor every natural mathematical structure… … Wikipedia**List of algebraic structures**— In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… … Wikipedia**Outline of algebraic structures**— In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… … Wikipedia