Qualifying Examination in Foundations

Jan 12, 1994

The examination consists of seven problems. All the problems have equal weight. Budget your time accordingly.

1. Let N be a set defined recursively as:

(base) 0 ∈ N.

(rec) s(x) ∈ N for x ∈ N.

So, N = {0, s(0), s(s(0)), ...}. Define the function A : N × N → N by:

(base) A(0, y) = y for y ∈ N.

(rec) A(s(x), y) = s(A(x, y)) for x, y ∈ n.

Prove the following statements about A and s.

(a) A(x, s(y)) = s(A(x, y)) for all x, y ∈ N.

(b) A(x, y) = A(y, x) for all x, y ∈ N.

2. Let M_{i} denote the partial function computed by the ith Turing machine in a standard enumeration M_{0}, M_{1}, … of Turing machines. Is the set

{i|M_{i}(x) diverges for all inputs x }

recursive? Is it recursively enumberable? Justify your answers without citing Rice’s theorems.

3. Is the language

L = {a^{n}b^{m}|n ≤ m ≤ 2n}

regular? Is it context-free? Justify your answers.

4. Let L be a lattice. An element x ∈ L is compact ( or finite) iff for all sets A ⊆ L such that x ⊑ ⨆ A there exists finite subset B ⊆ A such that x ⊑ ⨆ B. Either prove or disprove (by giving a counterexample) the following statement: if a and b are compact elements of L, a ⊔ b is compact. (The notation ⊔A means the “least upper bound of A”. Similarly, the notation a ⊔ b means the the “least upper bound of a and b”.)

5. Define a function that is continuous but not computable.

6. Construct two closed terms M and N in the λ-calculus that are βη equivalent (M =_{βη} N) but not β equivalent (M =_{β} N). Recall the η conversion rule:

M = λx.Mx

where the usual restrictions on capture apply.

7. In a first order language without equality, the following theorem (proved by Lowenheim) holds: if a set A of sentences has a finite model with k elements, then it has a finite model with n elements for every natural number n > k. Does the same theorem hold for first order languages with equality? Prove it or give a counterexample.