Restricted set-theoretical definitions in arithmetic
Raphael M. Robinson · Proceedings of the American Mathematical Society · 1958
Notice that sets of ordered pairs of natural numbers are used in this definition. Here and throughout this paper the logical symbols A (and), v (or), -* (if * * * then * * * ), -+ (if and only if), A (for every), and V (there exists) are used; negation does not occur explicitly. The concepts just mentioned, together with identity, are considered as the logical notions. On the other hand, it is known that it is not possible to give an explicit arithmetical definition of addition in terms of successor, that is, a definition using only the concepts of logic, and excluding the concepts of set theory. In fact, from a formula containing (besides parentheses and variables ranging over the natural numbers) only logical symbols and the symbol for successor, we can eliminate all quantifiers, if we allow the symbol 0 to be introduced.' From this, it follows that the only sets of natural numbers which are definable are the finite sets and their complements. In particular, the set of even numbers is not definable. It is then clear that addition also is not definable in this way. Alfred Tarski has proposed (in lectures) consideration of an intermediate type of definition, in which sets of natural numbers but no other sets are allowed. Thus we will have variables a, b, c, * * * which represent natural numbers, and variables A, B, C, * * * which repre-