Three contributions to the theory of recursively enumerable classes.
Institution: | Simon Fraser University |
---|---|
Department: | |
Year: | 1967 |
Record ID: | 1518235 |
Full text PDF: | http://summit.sfu.ca/item/625 |
Priority arguments are applied to three problems in the theory of rce. classes. Chapter I: A conjecture of P. R. Young in A Theorem on Recursively Enumerable Classes and Splinters, PAMS 17,5 (1966), pp. 1050-1056, that an r.e. class can be constructed with any pre-assigned finite number of infinite r.e. subclasses, is answered in the affirmative. Chapter II: Standard classes and indexable classes were introduced by A. H. Lachlan (cf. On the Indexing of Classes of Recursively Enumerable Sets, JSL 31 (1966-),, pp. 10-22). A class C- of r.e. sets is called sequence enumerable if the r.e. (3- is indexable => fl. is subclass enumerable, but none of the implications can be reversed. Chapter. Ill: A partially ordered set (&,<} is represented by the r.e. class G- if (&,<} is isomorphic to (C-,E). Sufficiently many p.o. sets are proved representable to verify a conjecture of A. H. Lachlan that representable p.o. sets and arbitrary p.o. sets are indistinguishable by elementary sentences.