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.