Definability in the Degrees of Randomness
Charlotte Vlek
Abstract:
A set or sequence is random when the pre~x-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 de~ne 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 \upharpoonright n ) <=^+
K(B \upharpoonright 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 de~nability in the K-degrees. The
main result we present, is the construction of a non-K-trivial
\Delta^0_2 set that does not bound any non-K-trivial set in a given
Delta^0_2 family of sets. This implies that there is a non-K-trivial
Delta^0_2 set that does not bound any non-K-trivial c.e. set.
Furthermore, this result shows a structural di~erence between the
K-degrees and the LK-degrees.
Similar to the above result, we also show that for all n > 1 there is
a non-K-trivial \Sigma^0_n set that does not bound any non-K-trivial
Delta^0_n set. We present the construction for the particular case of
n = 2, and we show that this speci~c \Sigma^0_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 Delta^0_2 gap function can exist, thus
showing that this method is not suitable for constructing a Delta^0_2
minimal pair in the K-degrees.