Three Recursion Theoretic Concepts of Genericity
Walter Dean
Abstract:
This paper develops and contrasts three recursion-theoretic notions of
genericity: one for sets below 0', and two for the recursively enumerable
(r.e.) sets. The first is the classical notion of 1-genericity, developed
in the context of the finite extension method first developed by Kleene
and Post to study degrees below 0'. We review several established
facts about 1-generic sets showing that they are bi-immune, generalized
low and have Turing incomparable even and odd halves. We then generalize
the definition of 1-genericity to obtain a non-effective version of a
result of Sacks which states that for any r.e. non-recursive C there is
a simple set A such that C <=_T A. We next develop a new notion of
genericity based on the Ellentuck-Mathias [EM] topology on 2^\omega.
EM-generic sets are shown to be simple and have Turing incomparable
even and odd halves. Finally we introduce and generalize a concept of
Jockusch known as e-genericity and show how it can be modified so as to
obtain the full results of Sacks stated above.