hide
Free keywords:
-
Abstract:
Systems of finitely many equations of the form
φ(X_1, …, X_n)=ψ(X_1, …, X_n)
are considered,
in which the unknowns X_i
are sets of natural numbers,
while the expressions φ,ψ
may contain singleton constants
and the operations of union
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.
The same results are established for equations with addition and intersection.
