Math. 109A, Friday, December1, 2000

Problems due Friday, December 8. I will grade them.

1. The proof of Gödel’s Incompleteness Theorem involved the construction of a sentence which effectively has the intuitive meaning “I am not provable.” This is done using the Diagonal Lemma. In similar fashion, construct a sentence with the meaning “If I have a proof, then there is a smaller proof of my negation.” You can use the formula neg(x, y), which has the property that for each formula φ,

⊢ ∀u(neg(\overline{^{⌜}φ^{⌝}}, u) ↔ u ≈ \overline{^{⌜}¬φ^{⌝}})

2. Find a formula that represents the set of terms:

(i) \overline{0} is a term.

(ii) Every variable is a term.

(iii) If τ, π are terms, so are Sτ, τ + π, τ · π, τ ↑ π, (τ).

(iv) Nothing is a term except as required by (i), (ii), (iii).

You will probably want to use the formulas

“y = length(x)” “y is the number of 5-bit bytes in x”

concat(u, v, y) “y is the concatenation of u, v”, i.e., if α, β are two strings of symbols, then their concatenation is αβ, and we have

⊢ ∀y(concat(\overline{^{⌜}α^{⌝}}, \overline{^{⌜}β^{⌝}}, y) ↔ y ≈ \overline{^{⌜}αβ^{⌝}})

3. Show that if the functions f(k, m, n), g(n) are represented by the formulas φ(v, x, y), ψ(y), respectively, then there is a formula θ(x, y) representing the function h defined by recursion:

h(0, n) = g(n)
h(m + 1, n) = f(h(m, n), m, n)

(You don’t have to actually prove representability; just give a formula that should work.)