Report Number: CS-TR-72-269

Institution: Stanford University, Department of Computer Science

Title: Arithmetic properties of certain recursively defined sets.

Author: Klarner, David A.

Author: Rado, Richard

Date: March 1972

Abstract: Let R denote a set of linear operations defined on the set P
of positive integers; for example, a typical element of R has
the form $\rho (x_1, \ldots ,x_r) = m_0 + m_1 x_1 + \ldots +
m_r x_r where m_0, \ldots ,m_r$ denote certain integers.
Given a set A of positive integers, there is a smallest set
of positive integers denoted which contains A as a
subset and is closed under every operation in R. The set
can be constructed recursively as follows: Let $A_0$ =
A, and define
$A_{k+1} = A_k \cup \{\rho (\bar{a}): \rho \in R,\bar{a}\in
A_k \times \ldots \times A_k\}$ (k = 0,1,\ldots ),
then it can be shown that = $A_0 \cup A_1 \cup \ldots
$. The sets sometimes have an elegant form, for
example, the set <2x + 3y: 1> consists of all positive
numbers congruent to 1 or 5 modulo 12. The objective is to
give an arithmetic characterization of elements of a set
, and this paper is a report on progress made on this
problem last year. Many of the questions left open here have
since been resolved by one of us (Klarner).

http://i.stanford.edu/pub/cstr/reports/cs/tr/72/269/CS-TR-72-269.pdf