Math 597B – Homework #6

April 20, 2007

A set U ⊆ 2^{ℕ} is said to be dense if U ∩ N_{σ} ≠ ∅ for all σ ∈ 2^{<ℕ}. A point X ∈ 2^{ℕ} is said to be weakly generic if X ∈ U for all dense Σ_{1}^{0} sets U ⊆ 2^{ℕ}. A point X ∈ 2^{ℕ} is said to be weakly random if X ∉ P for all Π_{1}^{0} sets P ⊆ 2^{ℕ} of measure 0.

1. (10 points) The concept of weak genericity was used in class to solve some of the problems which were in the Homework #4 problem set. Specifically, we sketched proofs of the following facts:

(a) The set {X ∈ 2^{ℕ} | X is weakly generic} is dense.

(b) If X is weakly generic, then X is weakly random.

(c) If X is weakly generic, then X does not obey the Strong Law of Large Numbers, i.e.,

lim_{n→∞} \frac{|\{m < n | X(m) = 1\}|}{n} ≠ \frac{1}{2} .

In fact, the limit in question does not exist, because the lim sup is 1 and the lim inf is 0.

(d) We can find X, Y ∈ 2^{ℕ} such that X ⊕ Y is weakly generic yet X ≡_{T} Y.

Please work out the detailed proofs of these facts.

2. (10 points) Given a point X ∈ 2^{ℕ}, we write dim(X) = the effective Hausdorff dimension of X, defined by

dim(X) = lim inf_{n→∞} \frac{K(X ↾ n)}{n} = lim inf_{n→∞} \frac{C(X ↾ n)}{n} .

Prove the following:

(a) For all X we have 0 ≤ dim(X) ≤ 1.

(b) For all r in the interval 0 ≤ r ≤ 1, there exists X such that dim(X) = r.

(c) If X is random, then dim(X) = 1.

(d) If X is weakly generic, then dim(X) = 0.

3. (5 points) Define X to be 2-random if X ∉ ⋂_{n} U_{n} whenever U_{n} ⊆ 2^{ℕ} is uniformly Σ_{2}^{0} with μ(U_{n}) ≤ 1/2^{n} for all n.

Prove that X is 2-random if and only if X is random relative to 0′.

4. (5 points) Prove that if X is 2-random then X′ ≡_{T} X ⊕ 0′.

5. (5 points) In Problem 4, what if we assume only that X is strongly random?