# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Computational Completeness of Equations Over Sets of Natural Numbers

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Jeż, A., & Okhotin, A. (2014). Computational Completeness of Equations Over Sets
of Natural Numbers.* Information and Computation,* *237*,
56-94. doi:10.1016/j.ic.2014.05.001.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-5594-1

##### 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.