P-Genericity for Recursively Enumerable Sets

Ingrassia, Michael Anthony

Permalink

https://hdl.handle.net/2142/68181 Copy

Description

Title

P-Genericity for Recursively Enumerable Sets

Author(s)

Ingrassia, Michael Anthony

Issue Date

1981

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Mathematics

Language

eng

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.

Graduation Semester

1981

Type of Resource

text

Permalink

http://hdl.handle.net/2142/68181

Owning Collections