Agnes Scott College

Julia Robinson

Definability and Decision Problems in Arithmetic
The Journal of Symbolic Logic, Vol. 14, No. 2 (June 1949), 98-114

Introduction

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 successor S (where Sa = a+1). Also, it is shown that both addition and multiplication can be defined arithmetically in terms of successor and the relation of divisibility | (where x|y means x divides y). Thus the elementary theory of integers with S and • (or S and | ) as the only primitive notions, which may seem rather narrow, is sufficient to express every idea or result which can be expressed in elementary number theory, i.e., the arithmetic of integers with + and •. An axiomatic problem concerning the system of positive integers with S and • is discussed in Section 2.

In Section 3, we show that the notion of an integer can be defined arithmetically in terms of the notion of a rational number and the operations of + and • on rationals. Hence the arithmetic of rationals is adequate for the formulation of all problems of elementary number theory.

Since the solution of the decision problem is known to be negative for elementary number theory, it follows from our results that the solution of the decision problem is negative for any of the related theories mentioned above. As a further consequence, we see that the solution of the decision problem for the arithmetical theory of arbitrary fields is also negative. These problems will be discussed in Section 4.