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.