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 Π01 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 Π01 class. We show that no immune-free Π01 class P cups to the Medvedev complete class DNC of diagonally noncomputable sets, where P cups to Q in the Medvedev degrees of Π01 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