3. Consider alphabets 1 = {a, b, c} and 2 = {p, q, r, s, t} .

Consider alphabets ,-{a,b,c} and ,-{p,q, r, s, t} s; consists of all finite strings over 1. Similarly 29. We want to determine whether or not and 2 have the same size. One way of proving that they do is to set up a bijection between them. This can be done, but it is tricky Clearly | P31. Hence, what remains is to determine whether or not | 2 . This is true if and only if there is a mapping (encoding) f : such that each string in is mapped to a unique string in . (It might not be a bijection because some strings in might not get mapped to.) In other words, can you use strings over | to name all strings over 2. If you think that such mapping exists, explain why and give pscudo code for computing f. If you think that no such mappings f exists, carefully explain why. Recall that Jeff says that a set is countably- infinite in size if and only if each element in the set has a unique finite description. 3