Homework #1

Note:  In this ASCII version of the homework, assume that "^" is an intersection
       operator when applied to sets, and "v" is a union operator.
       Also note that I will either use f:AxB or f:A->B to denote a function
       mapping elements of set A to elements of set B.  I will use the
       notation a_i to denote symbol a with subscript i and the notation
       a^i to denote symbol a with superscript i or raised to the power i.

1.  Prove the following:
    A - (B ^ C) = (A - B) v (A - C)

2.  Give functions f: N->N that satisfy
    a) f is one-to-one but not onto
    b) f is onto but not one-to-one
    c) f is a bijection

3.  Prove that the union of two countable sets is countable.

4.  Let R1 and R2 be any two partial orders on the same set A.  Show that
    R1 ^ R2 is a partial order.

5.  Let R be a binary relation on the set A = the set of all English words;
    (a,b) in R if and only if a is longer than b.
    Is R a partial order?  Is R a total order?  Justify your answer.
    What are the minimal element(s)?

6.  Consider the set of elements S = {1,2,3} and a relation R defined on
    these elements

    R = {(1,2), (2,1), (2,2), (2,3), (3,2)}.

    Show R2 (R2 is R.R, or R composed with itself)
    and the reflexive, transitive closure of R (R*).

7.  Are the following sets closed under the following operations?  If not,
    name a set of which the property is a closure property.

    a) The even integers under division
    b) The positive integers under multiplication.