Qualifying Examination in Foundations May 17, 1994

The examination consists of 6 problems totaling 95 points. The problems do not have equal weight. Budget your time accordingly.

1. (10 pts.) Prove that the following formula holds for any natural number n and any non-zero real number a:

∑_{k=0}^{n−1} a^{k} = \frac{1 − a^{n}}{1 − a} .

2. (20 pts.) In the following question, let G_{1}, G_{2}, ... be an effective enumeration of all context free grammars and let M_{1}, M_{2}, ... be an effective enumeration of all Turing machines. Determine whether or not the following sets are (i) recursive, (ii) r.e. (recursively enumerable), or (iii) not r.e. Justify your answers.

(a) The set {i| L(G_{i}) is finite}.

(b) The set {i| L(M_{i}) is finite}.

3. (15 pts.) Let L = (0 + 1)^{∗}10(00)^{∗}1(0 + 1)^{∗}, the language with at least one pair of 1’s separated by an odd number of 0’s.

R_{L} is equivalence relation over (0 + 1)^{∗} defined by

x R_{L} y ⇔ ∀z[xz ∈ L ⇔ yz ∈ L]

Find the equivalence classes of R_{L} and express your answers as regular expressions. Hint: Find the minimum DFA for L.

Show all the major steps in deriving your answer.

4. (10 pts.) Let N_{⊥} be the Scott-domain consisting of the natural numbers N and the divergent element ⊥ under the usual approximation ordering:

x ⊑ y ⇔ x = ⊥ or x = y

Let F be N_{⊥} → N_{⊥}, the Scott-domain of continuous functions over N_{⊥}. How does the cardinality of F compare with the cardinality of the set of computable functions from N_{⊥} to N_{⊥}? Justify your answer.

5. (15 pts.) A term M in the λ − calculus has the form defined by the grammar:

M ::= V | (M M) (1)
V ::= x | (λx.M) (2)

where x ranges over a set of variables. The β axiom is

((λx.M)N) = M[N/x]

where M[N/x] is the capture-avoiding substitution of N for the free occurrences of x in M. The resulting equational theory, is called λλ .

There is a variation on the β axiom, called the β-value axiom, that yields a different equational theory over the terms of the λ − calculus. The β-value axiom has the form:

((λx.M)V) = M[V/x]

where V is restricted to the form given the grammar above and M[V/x] is the captureavoiding substitution of V for the free occurrences of x in M. The resulting equational theory is called λλ_{v}.

Both theories are Church-Rosser. Find two terms that are equivalent in λλ but not in λλ_{v}. Justify your answer.

6. (25 pts.) A graph G is a pair (V, E) consisting of a (possible infinite) nonempty set of nodes V and a binary relation E ⊆ V^{2}. G is finite if V is finite. A path of length k in G between nodes u and v is a sequence u_{0}, ..., u_{k} of nodes in V where k > 0 such that u_{0} = u, u_{k} = v, and (u_{i}, u_{i+1}) ∈ E for 0 ≤ i < k. In this case, we say that the distance between u and v is at most k. G is connected if there is a path between every ordered pair of distinct nodes u and v in V.

A graph vocabulary consists of a binary predicate symbol \overline{E} whose intended interpretation is the binary relation E. Thus, we can express graph properties using first-order sentences over the graph vocabulary. For example, the first-order sentence ∀x∃y(\overline{E}(x, y) ∨ \overline{E}(y, x)) says that there are no isolated nodes in G. A graph property is first-order definable if there is a first-order sentence φ_{P} (with equality) over the graph vocabulary whose set of models is precisely the class of graphs satisfying the property P.

(a) Show that the first-order sentence

∀x, y, z∃u(\overline{E}(x, u) ∧ (\overline{E}(x, y) ∧ \overline{E}(y, z) → \overline{E}(x, z)) ∧ ¬\overline{E}(x, x))

has no finite models.

(b) Describe a formula φ(x, y) expressing the fact that the distance between x and y is at most k for k > 0.

(c) Prove that connectivity is not first-order definable.