2026-09-22T18:09:40Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/68181 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

U of I Only 162 p. Ingrassia, Michael Anthony 2014-12-14T13:09:49Z 2014-12-14T13:09:49Z 10000-01-01 1981 1981 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. Made available in DSpace on 2014-12-14T13:09:49Z (GMT). No. of bitstreams: 1 8114437.pdf: 4843276 bytes, checksum: 8468ba6adcbedf378dc5f723c3f309b1 (MD5) Previous issue date: 1981 Embargo set by: Seth Robbins for item 68359 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981. http://hdl.handle.net/2142/68181 (UMI)AAI8114437 eng Mathematics P-Genericity for Recursively Enumerable Sets text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.