Equations over sets of integers with addition only

• Investigating equations with sets of natural numbers (or any integers) as unknowns.
• The only operation is element-wise addition of sets.
• For natural numbers, these equations are computationally universal.
• For integers, any hyper-arithmetical set can be encoded in a solution.
• Solution existence, uniqueness, etc., are undecidable.

Systems of equations of the form X=Y+ZX=Y+Z and X=CX=C are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C   is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set S⊆NS⊆N there exists a system with a unique (least, greatest) solution containing a component T   with S={n|16n+13∈T}S={n|16n+13∈T}. Testing solution existence for these equations is Π10-complete, solution uniqueness is Π20-complete, and finiteness of the set of solutions is Σ30-complete. A similar construction for integers represents any hyper-arithmetical set S⊆ZS⊆Z by a set T⊆ZT⊆Z satisfying S={n|16n∈T}S={n|16n∈T}, whereas testing solution existence is Σ11-complete.