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.