1. (10 points) Show that the set N x N ((0,0), (0, 1),... is countable. Note tha
ID: 3733206 • Letter: 1
Question
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.Explanation / Answer
Solution:
The first question is done as per Chegg guidelines, please repost others.
1)
A set S is countable if there exists an injective function f from S to the natural numbers N = {0, 1, 2, 3, ...}.
injective function means one to one. f from X to Y is injective if for every element of x we have one element in Y as per f(x).
In this case we have a set = {(0,0), (1,0).....} Now if we consider a function
such that f(x1,x2) = x1 + x2. Now looking at this function we have for every (x1,x2) in the set we have a value in N. As we proved the existencse of such an injective function we can say that the given set S is countable.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.