Infinite Subclasses of Recursively Enumerable Classes
J. B. Florence · Proceedings of the American Mathematical Society · 1967
P. R. Young [l] has constructed an infinite recursively enumerable (r.e.) class with no proper infinite r.e.subclasses, and has asked if infinite r.e.classes with m + 1 infinite r.e.subclasses exist for every #2 = 0.It can further be asked what is the most general partially ordered set we can represent by the infinite r.e.subclasses of such a class (under inclusion).These questions are answered by the theorem below.The author wishes to thank A. H. Lachlan for his guidance and encouragement.Our construction is based on a formulation of Young's due to Lachlan.