Files in this item



application/pdf8114437.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:P-Genericity for Recursively Enumerable Sets
Author(s):Ingrassia, Michael Anthony
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract:1-generic sets possess all properties which can be obtained through "sufficiently simple" Kleene-Post constructions, but no recursively enumerable (r.e.) set can be 1-generic. P-genericity is the result of a generalization of 1-genericity, and p-generic sets have many of the properties which can be obtained through finite injury priority arguments. Specifically, A is p-generic if for every 1-quantifier property P true of A, P follows from a finite set of true negative information about A and a coinfinite r.e. set of true positive information. Because we allow the set of positive information in the definition to be r.e., we can prove that r.e. p-generic sets exist. We thus may consider the notion of p-genericity only for r.e. sets in the dissertation.
A 1-quantifier property of the form ((FOR ALL)x)P(x,X) is equivalent to an r.e. list of statements of the form C (L-HOOK) X (--->) D (INTERSECT) X (NOT=) (SLASHCIRC). Call it an (m,n) property if the cardinality of C is bounded by m and the cardinality of D bounded by n for statements on the list. Then we may refine the notion of p-genericity by calling A (m,n) p-generic if A is p-generic for the class of (m,n) properties. A is (<(INFIN),n) p-generic if for every m A is (m,n) p-generic. We allow both m and n to take on the values "<(INFIN)" and "(INFIN)". In chapter II we show that (1,n) p-genericity is equivalent to (<(INFIN),n) p-genericity. We also prove the following implications between properties, and show that no arrows can be reversed.
(<(INFIN),0) (<---) . . . (<---) (<(INFIN),n) (<---) (<(INFIN),n+1) (<---) . . . (<---) (<(INFIN),<(INFIN)) (<---) (<(INFIN),(INFIN))
((INFIN),0) (<---) . . . (<---) ((INFIN),n) (<---) ((INFIN),n+1) (<---) . . . (<---) ((INFIN),<(INFIN)) (<---) ((INFIN),(INFIN))
For r.e. sets, (<(INFIN),0) p-genericity is the same as simplicity, and ((INFIN),0) p-genericity is the same as hypersimplicity. (1,(INFIN)) p-genericity is a strong form of non-autoreducibility. Hyperhypersimplicity does not fit in a nice way into the above diagram, since p-generic sets need not be hyperhypersimple. All maximal sets are (<(INFIN),1) p-generic, although they need not be ((INFIN),2) p-generic.
((INFIN),<(INFIN)) p-generic sets occur in all nonzero r.e. degrees, but by a result of R. E. Ladner (<(INFIN),(INFIN)) p-generic sets do not occur in all nonzero r.e. degrees. In chapter V we exhibit a complete p-generic set, and in chapter VI we show that the nonzero r.e. degrees containing p-generic sets are dense in the ordering of r.e. degress, but not trivially. The proofs are infinite injury arguments of technical interest.
Issue Date:1981
Description:162 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8114437
Date Available in IDEALS:2014-12-14
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics