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(X1, …, Xn) = ψj(X1, …, Xn), 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 Xi 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=Xi forsome equation system of the above form with (X1, …, Xn) 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 Xi 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 Π1-complete, Π2-complete, and Σ3-complete, respectively.
