Exercise 6: We define functions fx where its argument are finite sets S C N of k (different) natural numbers (natural numbers start at (). Let S = {S | S C N. [S| = k} be the set of possible arguments to f. We assign numbers to such sets by defining f* : Sk - N as follows: f*(S) = _ si ci where s; is the i" smallest element in S i {1,.... s) otherwise For example, fs({0,5, 7}) = 0+ (2) +() =1+10+35 = 46. In this exercise, we work towards proving that the fx's are bijective. (a) Prove that f1 is a bijection. (b) Choose S to be a set of size k with Vs E S. s n?Explain your answers. Note: This question asked you to give the cardinality of: [s | SC {0, ....n -1}. [S| = k} = Sknip({0. ..., n -1}). (c) Prove by induction on n: VK. k 21 An > k = nti- k- Hint: You might prove k = 1 as a separate case and use this theorem (Pascal's identity): For any natural number n E N, and & E N with k 0 and Vs E S. s