• Unless otherwise stated, you do not have to justify your answers. Show relevant work for partial credit. • Problems that do require justification will be graded on both the correctness of your answer and the quality of your justification. • You may use any results from lectures, notes, homework, exams, or the textbook without proof. Be sure it is clear which result you are applying. • You may use the results from other parts of this exam-regardless of whether or not you solved that part-without proof, provided you cite them by problem number. • Circular logic is not permitted. 1. Let A = {a, b, c, d, e, f}. Define the relation R= {(a, a), (a, c), (b, d), (c, d), (c, a), (c, c), (d, d), (e, f), (f, e)} %3D on A. (a) Find the smallest reflexive relation R such that R C R1. (b) Find the smallest symmetric relation R2 such that RC R2. (c) Find the smallest transitive relation R3 such that R C R3. (d) Find the smallest equivalence relation R4 such that RC R4. (e) Find an antisymmetric relation R5 C R with the greatest possible cardinality. 2. Determine whether the following functions f are injective but not surjective, surjective but not injective, bijective, or neither. (a) f: R (e, o0) defined by f(x) = e(e(e*)) (b) f: Zx R-→ R defined by f(n, x) = x". (c) f: Zx Z P(P(Z)) defined by (a, b) {{a}, {a, b}}. (d) Let A be the set of surjections {a, b, c} → {a, b}. Let B be the set of injections {a, b} → {a,b, c}. Let C be the set of all maps {a, b, c} → {a, b, c}. Define f : Ax B→ C by f(a, B) = B o a. (e) f : R – {0} Rx {-1,1} defined by f(x)= (x², |¤|/x). %3D %3D %3D 3. Let A, B,CCU and f,g: U → U. Prove the following set identity by applying known set identities: g-1 (Tnf(AnB)) (f(B)) = 9=(C)ng-"(f(A))ng-(f(B). %3D You must show each step for full credit, but you do not have to cite or name the set identities you use. 4. Let f : A-B and g: B C. (a) Prove that g of is injective if and only if f is injective and Vc EC g-1({c})n f(A) < 1. (b) Prove that gof is surjective if and only if g is surjective and Ve E C g-1({c})n f(A) #0. 5. Fix sets A, B. Let S be a set and 71 : S A and T2: S B be maps. Call the triple of objects (S, T1, T2) special if the following property is satisfied: given any set T and maps fi : T A, f2:T B, there is a unique map o : T S such that T1 o 0 = fi and T2 0 0 = f2. (a) Define p : Ax B A and p2 : A x B B by pi(a, b) = a and p2(a,b) = b. Prove that (Ax B,p1,P2) is special. (b) Assume (S, T1, T2) is special. Since (S, T1, 72) is special, there is a unique map o : Ax B S such that Tı ° ¢ = p1 and 720 0 = p2. Since (A x B,p1, P2) is special, there is a unique map v:S → A x B such that pi o = T, and p2 o v = T2. Prove that o and are inverses. %3D %3D