Kolmogorov complexity of initial segments of sequences and arithmetical definability

The structure of the K-degrees provides a way to classify sets of natural numbers or infinite binary sequences with respect to the level of randomness of their initial segments. In theK-degrees of infinite binary sequences, X is below Y if the prefix-free Kolmogorov complexity of the first n bits of X is less than the complexity of the first n bits of Y, for each n. Identifying infinite binary sequences with subsets of N, we study the K-degrees of arithmetical sets and explore the interactions between arithmetical definability and prefix-free Kolmogorov complexity.We show that in the K-degrees, for each n>1, there exists a non-zero degree which does not bound any non-zero degree. An application of this result is that in the K-degrees there exists a degree which forms a minimal pair with all degrees. This extends the work of Csima and Montalbán (2006) [8], and Merkle and Stephan (2007) [17]. Our main result is that, given any family C of sequences, there is a sequence of non-trivial initial segment complexity which is not larger than the initial segment complexity of any non-trivial member of C. This general theorem has the following surprising consequence. There is a -computable sequence of non-trivial initial segment complexity, which is not larger than the initial segment complexity of any non-trivial computably enumerable set.Our analysis and results demonstrate that, examining the extend to which arithmetical definability interacts with the K reducibility (and in general any ‘weak reducibility’) is a fruitful way of studying the induced structure.