In this paper, we are concerned with the arithmetical definability of certain notions of integers and rationals in terms of other notions. The results derived will be applied to obtain a negative solution of corresponding decision problems.In Section 1, we show that addition of positive integers can be defined arithmetically in terms of multiplication and the unary operation of successorS(whereSa=a+ 1). Also, it is shown that both addition and multiplication can be defined arithmetically in terms of successor and the relation (...) of divisibility | (wherex|ymeansxdividesy). (shrink)

An elementary theory of concatenation,QT+, is introduced and used to establish mutual interpretability of Robinson arithmetic, Minimal Predicative Set Theory, quantifier-free part of Kirby’s finitary set theory, and Adjunctive Set Theory, with or without extensionality. The most basic arithmetic and simplest set theory thus turn out to be variants of string theory.

In this paper two different formulations of Robinson's arithmetic based on relevant logic are examined. The formulation based on the natural numbers (including zero) is shown to collapse into classical Robinson's arithmetic, whereas the one based on the positive integers (excluding zero) is shown not to similarly collapse. Relations of these two formulations to R. K. Meyer's system R# of relevant Peano arithmetic are examined, and some remarks are made about the role of constant functions (...) (e.g., multiplication by zero) in relevant arithmetic. (shrink)

Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π 1 sentence, valid in the standard model of the Natural Numbers and denoted as V, such that if α is any finite consistent extension (...) of Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property. Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ 0 , as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].). (shrink)

In this paper we give a positive answer to Julia Robinson's question whether the definability of + and · from S and ∣ that she proved in the case of positive integers is extendible to arbitrary integers (cf. [JR, p. 102]).

This book develops arithmetic without the induction principle, working in theories that are interpretable in Raphael Robinson's theory Q. Certain inductive formulas, the bounded ones, are interpretable in Q. A mathematically strong, but logically very weak, predicative arithmetic is constructed. Originally published in 1986. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These paperback editions preserve the original texts of these important (...) books while presenting them in durable paperback editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905. (shrink)

In this paper we show how to interpret Robinson’s arithmetic Q and the theory R of Tarski, Mostowski, and Robinson as theories of cardinals in very weak theories of relations over a domain.

Relations between some theories of semigroups (also known as theories of strings or theories of concatenation) and arithmetic are surveyed. In particular Robinson's arithmetic Q is shown to be mutually interpretable with TC, a weak theory of concatenation introduced by Grzegorczyk. Furthermore, TC is shown to be interpretable in the theory F studied by Tarski and Szmielewa, thus confirming their claim that F is essentially undecidable.

Edward Nelson published in 1986 a book defending an extreme formalist view of mathematics according to which there is an impassable barrier in the totality of exponentiation. On the positive side, Nelson embarks on a program of investigating how much mathematics can be interpreted in Raphael Robinson's theory of arithmetic Q. In the shadow of this program, some very nice logical investigations and results were produced by a number of people, not only regarding what can be interpreted in (...) Q but also what cannot be so interpreted. We explain some of these results and rely on them to discuss Nelson's position. (shrink)

In [2] John Burgess describes predicative versions of Frege's logic and poses the problem of finding their exact arithmetical strength. I prove here that PV, the simplest such theory, is equivalent to Robinson's arithmetical theory Q.

We give necessary conditions for a set to be definable by a formula with a universal quantifier and an existential quantifier over algebraic integer rings or algebraic number fields. From these necessary conditions we obtain some undefinability results. For example, N is not definable by such a formula over Z. This extends a previous result of R. M. Robinson.