Math 558 – Homework #3

Due October 29, 2009

1. Find a pair of numbers r, a such that β(r, a, 0) = 11, β(r, a, 1) = 19, β(r, a, 2) = 30, β(r, a, 3) = 37, β(r, a, 4) = 51.

Hint: First find an appropriate a by hand. Then write a small computer program to find r by brute force.

2. Recall that ℕ = {0, 1, 2, …} = the natural numbers, ℤ = {…, −2, −1, 0, 1, 2, …} = the integers, and ℝ = (−∞, ∞) = the real numbers. According to Matiyasevich’s Theorem, we can find a polynomial

f(w, x_{1}, …, x_{k})

with integer coefficients, such that the set of a ∈ ℕ for which the equation f(a, x_{1}, …, x_{k}) = 0 has a solution in ℕ is noncomputable.

(a) Discuss the analogous question in which “solution in ℕ” is replaced by “solution in ℤ”.

(b) Discuss analogous questions in which “solution in ℕ” is replaced by “solution in ℝ”.

3. Prove König’s Theorem:

Let ⟨κ_{i}⟩_{i∈I} and ⟨λ_{i}⟩_{i∈I} be indexed sets of cardinal numbers with the same index set I. If κ_{i} < λ_{i} for all i ∈ I, then ∑_{i∈I} κ_{i} < ∏_{i∈I} λ_{i}.