UC Davis Transition to Advanced Mathematics Problems

The screenshots of questions are attached. Please complete it within 24 hrs.

1. The symmetric difference of sets A and B is A?B = (A B) ? (B A). Let A be a set and recall that P(A) is the power set of A. a) Prove that A?A = ? and that A?? = A.

b) It can be shown that is associative (it is not necessary to verify this). Use this and the previous part to prove that (P(A);?) is an abelian group.

2. Recall that the Pigeonhole Principle states that if n > r, then there are no injective functions Nn ? Nr. This problem will prove a dual result, that there are no surjective functions Nr ? Nn if n > r (recall that Nn = {1,2,……,n}:

(a) For the base case, prove that there are no surjective functions N1 ? N2.

(b) Our inductive hypothesis is to assume that the result holds for some n 2, that is, that there are no surjective functions Nr ! Nn if r < n. We now consider a function f : Nr ! Nn+1, where r < n + 1. Complete the proof of the statement by assuming that f is surjective and using the inductive hypothesis to derive a contradiction. (Hint: Try restricting f to Nr f^-1({n + 1}).)

3. Let f : A ? B be a function.

(a) Prove that the relation R on A given by x R y if f(x) = f(y) is an equivalence relation.

(b) Let a ? A and b = f(a). Prove that [a]R = f^-1({b}), where [a]R is the equivalence class of a with respect to R.

(c) Use the previous part to prove that the collection { f^-1({b}) | b ? B } is pairwise disjoint.

4. Give two proofs that n^2 + n + 3 is odd for every n ? N (you may use in either proof that the sum of an odd number and an even number is odd):

(a) Give a direct proof.

(b) Give a proof using mathematical induction.

5. Extra Credit (2 points) True or false? (No justication is necessary, all must be correct for credit.)

(a) The empty relation is a strict partial ordering on any set.

(b) The intersection of the empty family of sets is empty.

(c) The empty set is an inductive set.

(d) The empty subset of any ring is closed under addition and multiplication.

(e) The empty set has the same cardinality as its power set.