Abstract

In [S, pp. 77–88], Smullyan introduced the class of rudimentary relations, and showed that they form a basis for the recursively enumerable sets. He also asked [S, p. 81] if the addition and multiplication relations were rudimentary. In this note we answer one of these questions by showing that the addition relation is rudimentary. This result was communicated to Smullyan orally in 1960 and is announced in [S, p. 81, footnote 1]. However, the proof has not yet appeared in print. Let us begin by reviewing Smullyan's definition [S, p. 10] of dyadic notation for the positive integers. Each positive integerais identified with the unique stringanan−1…a1a0of 1's and 2's such thata= Σin=0ai2iBecause of this identification, we are able to speak of typographical properties of numbers.