4. (5 marks) Let an denote the sequence that counts the number of distinct ways of building a 2 x n wall using bricks , which may be positioned horizontally or vertically. I. Give a recursive definition of the sequence Il. State the value of a3, 04, 451. (10 marks) Let f : A > B. Prove that f is one-to-one if and only if for every subset E (_: A, f_1(f(E)) = E. NOTE: do not assume that the inverse function exists; here f_1(X) denotes the pre-image of X. 2. {5 marks) Let X be some universal set and Ea be subsets of X, for all or in some indexing set A. Prove U E = n Ea. 0:64 0:611 NOTE: this question is easier than it looks. Start from the denition of set equality. 3. (10 marks) Let f : A - Band g : C - D be one-to-one and onto functions. 1. Prove that : A X C - B X D defined by p(a, c) := (f(a), g(c)), Va E A, Vc E C is a one-to-one and onto function Il. Conclude that if A, B, C, D are any sets such that | A| = [ B| and |C| = [ D|, then | A x C| = [B X D|, where (X] denotes the cardinality of the set X. NOTE: your argument should make sense even if the sets are of infinite cardinality