## Immunity and non-cupping for closed sets## Douglas Cenzer, Takayuki Kihara, Rebecca Weber, Guohua Wu
We extend the notion of immunity to closed sets and to Π
^{0}_{1}
classes in particular in two ways: immunity meaning the
corresponding tree has no infinite computable subset, and
tree-immunity meaning it has no infinite computable
subtree. We separate these notions from each other and that of
being special, and show separating classes for computably
inseparable c.e. sets are immune and perfect thin classes are
tree-immune. We define the notion of prompt immunity and
construct a positive-measure promptly immune Π^{0}_{1} class. We show
that no immune-free Π^{0}_{1} class P cups to the Medvedev
complete class DNC of diagonally noncomputable sets, where P cups
to Q in the Medvedev degrees of Π^{0}_{1} classes if there is a class
R such that the product P \otimes R ≡_{M} Q. We characterize
the interaction between (tree-)immunity and Medvedev meet and join,
showing the (tree-)immune degrees form prime ideals in the Medvedev
lattice. We show that every random closed set is immune and not
small, and every small special class is immune.
Tbilisi Mathematical Journal, Vol. 2 (2009), pp. 77-94 |