One basic issue in several areas of theoretical computer science is to characterize various classes C of functions or sets as those functions/sets that can be created from certain simple initial objects by means of certain operations. For instance, a language is regular if and only if it can be obtained from ∅ and languages of the form {a} by union, concatenation, and the Kleene star, and the usual definition of primitive recursive functions is of a similar kind. More generally, elements of C may be characterized as solutions of systems of functional or set equations φ_j(X₁, …, X_n) = ψ_j(X₁, …, X_n), where the expressions φ_j, ψ_j may involve certain specified types of operations for functions or sets, respectively.

The paper under review considers equation systems of the above form, with X_i ranging over subsets ofω={0, 1, 2, …}, and where the expressions φ_j, ψ_j may contain singleton constants andthe operations of union, intersection and element-wise addition (X+Y={x+y|x∈X∧y∈Y}). The main result states that a set X⊆ω is recursive (r.e., co-r.e.) if and only if X=X_i forsome equation system of the above form with (X₁, …, X_n) as the unique (least, greatest) solution; the terms “least” and “greatest” are understood with respect to the component-wise subset relation. Actually, for given X the equation system constructed has to use only one of the two Boolean operations (union orintersection) besides addition.

Previously, analogous results had been obtained, where the unknowns X_i range over languages, and concatenation takes the role of addition. For the easy part (implication ⇐) the proof carries over, but for the converse implication the case of number sets is substantially more complicated and requires new techniques. Basically, the approach is to apply arithmetization for Turing machines T; given T, appropriate representations are obtained first for the set of (encoding of) computations by T, and then for the set accepted.

In a final section, various natural decision problems about equation systems Σ are classified in thearithmetical hierarchy, namely deciding if Σ has a solution, a unique solution, or only finitely many solutions. These problems are shown to be Π₁-complete, Π₂-complete, and Σ₃-complete, respectively.