I have stuck with these problems. Please help me!! 1/ Let S be the set of all fi
ID: 3108673 • Letter: I
Question
I have stuck with these problems. Please help me!! 1/ Let S be the set of all finite-length strings composed of the capital letters A,B,C,...,z ZAAABABX' and 'Y' are two examples of such strings). Prove that S is countably infinite. (Note that you need to prove both that S is infinite and that S is countable. You may wish to use the Theorem C below. Theorem C: If V1,V2,... are each finite or countably infinite countable sets, then their union U (from k 1 to infinity) V(k) also either inifity or countably infinity. You may use this theorem on this assignment without proving it. The proof isjust a gener alization of Cantor's diagonalization process 2/ Let I 1,1], and let J [0,10] So I and J are subsets of R). Prove that I and J have the same cardinality. 3/Give an example of a function f Z N that is exactly "two-to-one", meaning that for every y E N there are exactly two elements (no more and no less) x1, x2 EZsuch that foxi y. int: You might find it easiest to use piecewise notation to define such a function.)Explanation / Answer
3) Solution :
Let f be a function. We say that f is two-to-one provided for each bimfbimf there are exactly two elements a1,a2dom(f) s.t. f(a1) = f(a2) = b. For a positive integer n, let A be a 2n-element set and B be an n-element set.
Since |A| = 2n and |B| = n, a two-to-one function f from A to B must map A onto B. In effect you’re just dividing A into n pairs of elements and then letting ff send each pair to a different element of B.
For example, if n = 3, A = {0,1,2,3,4,5}, and B = {0,1,2}, one possible two-to-one function f is the one defined by :
f(0)=f(1)=0
f(2)=f(3)=1
f(4)=f(5)=2
To count these function, let B = {b1,…,bn}. There are (2n choose 2) ways to choose the two elements of A that are to be sent to b1. Once that’s been done, there are 2(n1) elements of A left, so there are (2(n1) choose 2)ways to choose a pair to be sent to b2.