Least and greatest solutions of equations over sets of integers

作者：Jez Artur; Okhotin Alexander^*

来源：Theoretical Computer Science, 2016, 619: 68-86.

DOI：10.1016/j.tcs.2016.01.013

• Language equations
• Computability
• Analytical hierarchy

Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, S + T = {m + n vertical bar m is an element of S, n is an element of T}. These equations were recently studied by the authors ("Representing hyper-arithmetical sets by equations over sets of integers", Theory of Computing Systems, 51 (2012), 196-228), and it was shown that the class of sets representable by their unique solutions is exactly the class of hyper-arithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the Sigma(1)(1)-sets in the analytical hierarchy, and all those sets can already be represented by systems in the resolved form X-i = phi(i)(X-1, ... , X-n). Least solutions of such resolved systems represent exactly the recursively enumerable sets.

• 出版日期2016-3-14