80-310/610 Logic and Computation Fall 2001

Homework #3

Due Wednesday, September 12

1. Read through section 1.2 of van Dalen.

2. ⋆ Write down explicit definitions of the functions f and g, where

a. f is defined recursively by f(0) = 0, f(n + 1) = 3 + f(n), and

b. g is defined recursively by g(0) = 1, g(n + 1) = (n + 1)^{2}g(n). (Hint: use “factorial” notation: m! = 1 × 2 × … × m.)

3. Write down an explicit definition of the function h, where h(0) = 0 and h(n+1) = 3·h(n)+1. (Hint: compare to the sequence 1, 3, 9, 27, 81, …)

4. ⋆ Suppose g is a function from ℕ to ℕ. Write down a recursive definition of the function f(n), defined by f(n) = ∑_{i=0}^{n} g(i).

5. Do problem 1 on page 30 of the Enderton handout.

6. ∘ Do problem 3 on page 30 of the Enderton handout.

7. ⋆ Suppose, as Section 2.2 of the notes, we are given a set U, a subset B ⊆ U, and some functions f_{1}, …, f_{k}. Say a set is inductive if it contains B and is closed under the f’s, and let C^{∗} be the intersection of all the inductive subsets of U. Show C^{∗} is inductive.

8. ⋆ Define the set of “babble-strings” inductively, as follows:

• “ba” is a babble-string

• if s is a babble-string, so is “ab”ˆ s

• if s and t are babble-strings, so is sˆ t

Prove by induction that every babble-string has the same number of a’s and b’s, and that every babble-string ends with an “a”. Is the set of babble-strings freely generated?