Oracle dependent properties of the lattice of NP-sets
We consider under the assumption
questions concerning the structure
of the lattice of
sets together with the sublattice
. We show that
two questions which are slightly more complex than the known splitting
properties of this lattice cannot be settled by arguments which relativize.
The two questions which we consider are whether every infinite
contains an infinite
subset and whether there exists an
We construct several oracles, all of which make
, and which in
addition make the above-mentioned statements either true or false. In
particular we give a positive answer to the question, raised by Bennett and
Gill 1981), whether an oracle
and such that
every infinite set in
has an infinite subset in
constructions of the oracles are finite injury priority arguments.
Reference: S. Homer and W. Maass.
Oracle dependent properties of the lattice of NP-sets.
Theoretical Computer Science, 24:279-289, 1983.