Math 597B – Homework #2

February 19, 2007

Endow ℕ with the discrete topology.

Endow ℕ^{ℕ} with the product topology.

1. Prove that U ⊆ ℕ^{ℕ} is open if and only if U is Σ_{1}^{0,g} for some g ∈ ℕ^{ℕ}.

2. Prove that P ⊆ ℕ^{ℕ} is G_{δ} (i.e., P = ⋂_{n=1}^{∞} U_{n} for some sequence of open sets U_{1}, U_{2}, …) if and only if P is Π_{2}^{0,g} for some g ∈ ℕ^{ℕ}.

3. Clearly the total functional Ψ : ℕ^{ℕ} → ℕ^{ℕ} given by

Ψ(f)(x) = f(x) + f(x + 1)

is computable. Write an oracle program which computes Ψ.

4. Consider a total functional Φ : ℕ^{ℕ} → ℕ^{ℕ}. Prove that Φ is continuous if and only if Φ is computable relative to some fixed oracle g ∈ ℕ^{ℕ}. This means that there exists e ∈ ℕ such that, for all f ∈ ℕ^{ℕ} and x ∈ ℕ,

Φ(f)(x) = φ_{e}^{(1),f⊕g}(x).

5. What is the appropriate generalization of the previous result to partial functionals Φ :⊆ ℕ^{ℕ} → ℕ^{ℕ}? State and prove this generalization.