Files in this item
Files  Description  Format 

application/pdf 8114437.pdf (5MB)  (no description provided) 
Description
Title:  PGenericity for Recursively Enumerable Sets 
Author(s):  Ingrassia, Michael Anthony 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  1generic sets possess all properties which can be obtained through "sufficiently simple" KleenePost constructions, but no recursively enumerable (r.e.) set can be 1generic. Pgenericity is the result of a generalization of 1genericity, and pgeneric sets have many of the properties which can be obtained through finite injury priority arguments. Specifically, A is pgeneric if for every 1quantifier 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. pgeneric sets exist. We thus may consider the notion of pgenericity only for r.e. sets in the dissertation. A 1quantifier property of the form ((FOR ALL)x)P(x,X) is equivalent to an r.e. list of statements of the form C (LHOOK) 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 pgenericity by calling A (m,n) pgeneric if A is pgeneric for the class of (m,n) properties. A is (<(INFIN),n) pgeneric if for every m A is (m,n) pgeneric. We allow both m and n to take on the values "<(INFIN)" and "(INFIN)". In chapter II we show that (1,n) pgenericity is equivalent to (<(INFIN),n) pgenericity. 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)) (UPARR) (UPARR) (UPARR) (UPARR) (UPARR) ((INFIN),0) (<) . . . (<) ((INFIN),n) (<) ((INFIN),n+1) (<) . . . (<) ((INFIN),<(INFIN)) (<) ((INFIN),(INFIN)) (pgeneric) For r.e. sets, (<(INFIN),0) pgenericity is the same as simplicity, and ((INFIN),0) pgenericity is the same as hypersimplicity. (1,(INFIN)) pgenericity is a strong form of nonautoreducibility. Hyperhypersimplicity does not fit in a nice way into the above diagram, since pgeneric sets need not be hyperhypersimple. All maximal sets are (<(INFIN),1) pgeneric, although they need not be ((INFIN),2) pgeneric. ((INFIN),<(INFIN)) pgeneric sets occur in all nonzero r.e. degrees, but by a result of R. E. Ladner (<(INFIN),(INFIN)) pgeneric sets do not occur in all nonzero r.e. degrees. In chapter V we exhibit a complete pgeneric set, and in chapter VI we show that the nonzero r.e. degrees containing pgeneric 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 
Type:  Text 
Language:  English 
Description:  162 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1981. 
URI:  http://hdl.handle.net/2142/68181 
Other Identifier(s):  (UMI)AAI8114437 
Date Available in IDEALS:  20141214 
Date Deposited:  1981 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois