- Robinson arithmetic
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 schemaof induction. Even though Q is much weaker than PA, it is still incomplete in the sense of Gödel.
The background logic of Q is
first-order logicwith 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:
unary operationcalled successor and denoted by prefix "S";
binary operations, additionand multiplication, denoted by infix + and by concatenation, respectively.
axioms for Q are Q1-Q7 in Burgess (2005: 56), and the first seven basic axioms of second order arithmetic. Variablesnot bound by an existential quantifierare 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 setbounded by 0) and "S" (it is an injective functionwhose 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. The
axiom schemaof 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 the
recursive definitionof addition.
# "x"0 = 0
# "xSy" = ("xy") + "x"
#* (6) and (7) are the
recursive definitionof multiplication.
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).
total orderon N, "less than" (denoted by infix "<"), can be defined in terms of addition as:
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