A theorem on maximal sets.
Joseph S. Ullian · Notre Dame Journal of Formal Logic · 1961
We presuppose familiarity with [2].Let 21 be the class of recursively enumerable (r.e.) sets with infinite complements.A r.e.set M is maximal if M € 21 and every r.e.superset of M which is in 21 differs only finitely from M. Existence of maximal sets is established in [l].Theorem-.For every maximal set W^, there is a set in 21 every recursive permutation of which lacks at most finitely much of WP roof: Otherwise, there is a maximal set W^ such that for every r.e.set W χ) W e 2I^*(3 y)(φ is a recursive permutation & x y W z ~Φy W χ ) ^ infinite).Since W^ is maximal, W^φ (W χ ) is infinite just in case Φ y W χ ) ~ W^ is finite.Thus W^ e 2ti^(:j y)(φ is a recursive permutation & <£ y (W χ )-:W z is finite).Now it is established in[3] that \x\ φ χ is a recursive permutation} = S^2^€Ϊί 2 , and it is easily verified that {x\φ (W χ ) -W^ is finite} e Σy But then [xj^.h.s. of (1) holds} e Σ 3 , while we know from [2] that \x\ W χ € 21} = This result may be of help in determining whether or not every set in 21 has a maximal superset.