## Files in this item

FilesDescriptionFormat

application/pdf

8114437.pdf (5MB)
(no description provided)PDF

## Description

 Title: P-Genericity for Recursively Enumerable Sets Author(s): Ingrassia, Michael Anthony Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics 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))(UPARR) (UPARR) (UPARR) (UPARR) (UPARR)((INFIN),0) (<---) . . . (<---) ((INFIN),n) (<---) ((INFIN),n+1) (<---) . . . (<---) ((INFIN),<(INFIN)) (<---) ((INFIN),(INFIN))(p-generic)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 Type: Text Language: English Description: 162 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981. URI: http://hdl.handle.net/2142/68181 Other Identifier(s): (UMI)AAI8114437 Date Available in IDEALS: 2014-12-14 Date Deposited: 1981
﻿