CS 4114, Assignment 1 - Due January 30, 2008

Please show all your work!

  1. Let S be a set containing n elements. Show that S has 2n subsets.

  2. Find the error in the "proof" of the following assertion.
    Any set of n elements has the property that all n elements are identical.

    PROOF: By induction on n.

    BASIS: n = 1 The set has one element a, and clearly a = a.

    INDUCTION: Assume true for all sets of up to n - 1 elements and consider any subset of {a1, a2, ..., an}. If we form the subset {a1, a2, ..., an-1}, then by assumption a1 = a2 = ... = an-1. Also form the set {a2, a3, ..., an}. Collecting results, we have that a1 = a2 = ... = an-1 = an.

  3. Prove that the set of nonnegative rational numbers is denumerable.

  4. Prove that there are an uncountable number of total functions from N to {0, 1}.

  5. Give a recursive definition of multiplication of natural numbers using the successor function and addition.

  6. Prove that if X and Y are countable sets, then so is X × Y.

  7. Express using a concise mathematical statement the function from N to N × N in Example 1.4.2.

  8. Prove Theorem 1.4.2 (Schröder-Bernstein).

  9. Let R be the relation on N+ × N+ given by (a,b) R (c,d) iff a/b = c/d. Show that R is an equivalence relation. What are its equivalence classes?

NOTE: Your problem solutions are due at 5:00 on the above date.