1. (10 points) Show that the set N x N ((0,0), (0, 1),... is countable. Note that if you use picture to demonstrate correspondence and need to skip some elements, you must explain in what situation do you need to skip those element, and why. 2. (10 points) Consider two infinite sets A and B which are countable and AUBt0. Show that the set AUB is countable. Note that if you use picture to demonstrate correspondence and need to skip some elements, you must explain in what situation do you need to skip those element, and why. 3. (10 points) Consider two infinite sets A and B which are countable and AnB- Let f : N A and g : N B be correspondences. From previous question, we already know that AUB is countable. For this qhestion, construct a correspontdence h:N (AU B) using correspondences f and g. Note that N (1,2,3,...) 4. (10 points) Let A be a set of all infinite sequences over (a, b, c). Examples of infinite sequence over (a, b, c are aaaa..., ababab..., abcabc.., and ccaabbccaabb Show that the set A is uncountable using the diagonalization method. 5. (10 points) Consider languages A, B, and C, where A = BUC. Suppose language B and C are decidable, show that the language A is also decidable by construct a Turing machine that decides the language A. Note that you have to show that your TM is a decider as well as a decider for the language A