[25]

(a) Show that there exists an infinite set having no infinite computably enumerable subset. Such sets have been called immune by J.C.E. Dekker.

(b) If a set with this property has a computably enumerable complement, then this complement was called simple by E.L. Post in 1944. Show that there exists a simple set.

Comments. By definition a simple set is computably enumerable. A simple set is not computable, since its complement is infinite but not computably enumerable (Lemma 1.7.3, Item (i)). Source: [H. Rogers, Jr., Ibid.].