On equations over sets of numbers and their limitations

Tommi Lehtinen and Alexander Okhotin

Abstract:
Systems of equations of the form $X=Y+Z$ and $X=C$, in which the unknowns are sets of natural numbers, ``$+$'' denotes elementwise sum of sets $S+T=\makeset{m+n}{m \in S, \; n \in T}$, and $C$ is an ultimately periodic constant, have recently been proved to be computationally universal (Je\.z, Okhotin, ``Equations over sets of natural numbers with addition only'', STACS 2009). This paper establishes some limitations of such systems. A class of sets of numbers that cannot be represented by unique, least or greatest solutions of systems of this form is defined, and a particular set in this class is constructed.