Systems of equations of the form Φ{sub}j(X{sub}1,...,X{sub}n)=ψ{sub}j(X{sub}1,...,X{sub}n) with 1≤j≤m are considered, in which the unknowns X{sub}i are sets of natural numbers, while the expressions Φ{sub}j, ψ{sub}j may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition S+T={m+n| m∈S, n∈T}. It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy.
展开▼
