Abstract:
We show that a set is bi-immune if and only if there are no computable permutations that arrange the set into a generically computable set or an effectively densely computable set. An example of a coarsely computable bi-immune set is constructed. It is also proved that for any set there is a permutation from the same Turing degree that arranges the set into an effectively densely computable set. The upper densities of some sets are studied.