CS 535
                                                       Fall 2009

                      Assignment #0 (not graded)


Date Due: Thursday, September 10 

Reading: Chapter 1,  pages 1-21, Chapter 2, pages 22-36,  and Chapter 3, pages 41-47

Problems :

1. Problem 1.1 on page 2

2. Problem 1.4 on page 8

3. Either prove or give a counter-example to the following statement,

If card(A) = card(B) then card(A) &le card (B) and card(B) &le card (A).

4. The k-adic representation is defined in section 1.2 of the text.
Consider the 4-adic representation of the integers and show that
the function N4 giving this representation is one-to-one. 

5. Put the formula F = (b &and (not c)) &or ( b &or (not d)) 
in conjunctive normal form.  

6. Give examples of two different uncountable sets of real numbers. 

7. Show that the set of strings in {0,1}* which have exactly one 1 in them is countable. 

8. Give an example of two different countable and infinite languages A and B
over {0,1} with A a subset of B and  whose difference B &minus A is infinite.

9. List (that is enumerate, that is give a method to enumerate, see page 8) 
all the finite sets of natural numbers.

10. If you can, do the same as problem 9 but for all the infinite 
sets of integers ?