[39] (a) Show that for every set A x there is a set S x with K(S) K(A) + O(log (A)) and log d(S)

[39]

(a) Show that for every set A x there is a set S x with K(S) ≤ K(A) + O(log Λ(A)) and log d(S) = log d(A) − K(A|x) +

O(log Λ(A)).

(b) Show that for every set A x there is a set S x with K(S) ≤

K(A) − K(A|x) + O(log Λ(A)) and log d(S) = log d(A). Recall that

Λ(A) = K(A) + log d(A).

Comments. Item

(b) implies Item (a), which in turn proves Equation 5.23 on page 416, and hence finishes the proof of Theorem 5.5.1.

Source:

[N.K. Vereshchagin and P.M.B. Vit´anyi, IEEE Trans. Inform. Theory, 50:12(2004), 3265–3290]