Computability, Unsolvability, Randomness Math 497A: Homework #13

Stephen G. Simpson Due Monday, December 3, 2007

Recall that A is said to be strongly random if A does not belong to any Π_{2}^{0} set of measure 0.

1. (a) Suppose A⊕B is strongly random. Prove that inf(a, b) = 0 where

a = deg_{T} (A) and b = deg_{T} (B).

(b) What if we assume only that A ⊕ B is random?

2. Prove the following. If A is random and A ≤_{T} B and B is strongly random, then A is strongly random.

3. Prove that the following conditions are equivalent.

(a) A is random relative to 0^{(n)} for all n.

(b) A does not belong to any arithmetical set of measure 0.

In this case we say that A is arithmetically random.