AbstractsPhilosophy & Theology

Three contributions to the theory of recursively enumerable classes.

by John Blair. Florence




Institution: Simon Fraser University
Department:
Year: 1967
Record ID: 1518235
Full text PDF: http://summit.sfu.ca/item/625


Abstract

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.