Least and Greatest Solutions of Equations over Sets of Integers

摘要

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 m ￡ S, n ￡ T}. These equations were recently studied by the authors ("On equations over sets of integers", STACS 2010), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the E_1~1 sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved form Xi = e_i(X_1,... ,Xn). Least solutions of such resolved systems represent exactly the recursively enumerable sets.