Page 1 of 1

COSC 6113 3.0—Fall 2002

Posted: Sep 28, 2002 Due: End of October [Exact date TBA]

Problem Set No. 1

(1) Express each of the functions max(x, y) and min(x, y) by substitution \underline{using only}

the functions x + y and x −^{·} y.

(2) Find in closed form the pairing function λxy.J(x, y) (and its projections λz.K(z), λz.L(z)) that enumerates pairs (x, y) by increasing max(x, y), and in each group with max(x, y) = a it enumerates in the order

(0, a), (1, a), …, (a − 1, a), (a, a), (a, 0), (a, 1), …, (a, a − 1)

(3) Write a very complete proof of #25 on p.82. You may of course consult the reference.

(4) Do #32, #33, p.82.

(5) Do #36, #37, p.82. For #36 let me first remove an ambiguity: Clause (c) on p.82 must be “⟨0, n, m, 2⟩ ∈ ℱ̃iff 1 ≤ m ≤ n (it stands for U1^{n}; 1^{m})”.

Hint. You may want to peek into the web notes (Normal Form Theorems) to get a feel for how “coding-decoding” is handled in the context of the inductive definition of function sets.

COSC 6113. George Tourlakis. Fall 2002