Computability Theory

Connections to Logic 111

Exercises

1. (a) Show that {x | W

x

is infinite} is 5

2

.

(b) Show that {x | W

x

is infinite} is 5

3

.

2. Show that {x | W

x

is a computable set} is 6

3

.

3. Show that every 5

2

set of natural numbers is many-one reducible to Tot.

Suggestion: For a set {x | ∀u∃v R(x, u, v)}, look at the function hu, xi 7→

µv R(x, u, v) and apply the parameter theorem.

4. Show that the binary relation {hx, yi | W

x

⊆ W

y

} is a 5

2

relation.

5. Let Z be the set of indices for the function that is constantly zero:

Z = {t | [[t]](x) = 0 for all x}

(a) Show that Z is 5

2

.

(b) Show that Z is not 5

1

.

(c) Show that Z is not even 6

2

.

5.2 Definability in Arithmetic

A number is prime ...