Denability in the degrees of randomness
Charlotte Vlek · 2010
A set or sequence is random when the prefix-free Kolmogorov complexity of its initial segments is relatively high: equal to the length of the segment (up to a constant). Using Kolmogorov complexity of initial segments, we can not only define when a set is random, but we can also compare which of two sets is more random. We say that a set A is K-below (or K-reduces to) a set B if K(A n) ≤ K(B n) for all n. This reducibility gives the structure of the K-degrees. The sets in the lowest degree are called K-trivial sets. This thesis studies arithmetical definability in the K-degrees. The main result we present, is the construction of a non-K-trivial ∆2 set that does not bound any non-K-trivial set in a given ∆2 family of sets. This implies that there is a non-K-trivial ∆2 set that does not bound any non-K-trivial c.e. set. Furthermore, this result shows a structural difference between the K-degrees and the LK-degrees. Similar to the above result, we also show that for all n > 1 there is a nonK-trivial Σ n set that does not bound any non-K-trivial ∆ 0 n set. We present the construction for the particular case of n = 2, and we show that this specific Σ 2 set forms a minimal pair in the K-degrees with any non-K-trivial c.e. set. This improves on the lowest complexity known so far for minimal pairs in the K-degrees. Finally, we investigate the possibility of constructing a minimal pair in the K-degrees via gap functions for K-triviality. We show that no unbounded non-decreasing ∆2 gap function can exist, thus showing that this method is not suitable for constructing a ∆2 minimal pair in the K-degrees.