Indifferent sets
by
Santiago Figueira
University of Buenos Aires
Coauthors: Joseph S. Miller and André Nies

We define the notion of ïndifferent set" with respect to a given class of 0, 1-sequences. Roughly, for a set A in the class, a set of natural numbers I is ïndifferent for A with respect to the class" if it does not matter how we change A at the positions in I: the new sequence continues to be in the given class. We are especially interested in studying those sets that are indifferent with respect to classes containing different types of stochastic sequences.

For the class of Martin-Löf random sequences, we show that every random sequence has an infinite indifferent set and that there is no universal indifferent set. We show that indifferent sets must be sparse, in fact sparse enough to decide the halting problem. We prove the existence of co-ce indifferent sets, including a co-ce set that is indifferent for every 2-random sequence with respect to the class of random sequences.

For the class of absolutely normal numbers, we show that there are computable indifferent sets with respect to that class and we conclude that there is an absolutely normal real number in every 1-degree.

PDF

Date received: February 29, 2008