In 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 schema of induction. Since Q is weaker than PA, it is obviously incomplete in the sense of Godel, but the crucial point is that this weak finitely axiomatized theory is already incompletable and essentially undecidable as described below.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 Godel'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.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.