Short Answers to Some Problems in HW 0

Homework 0 - Problem 3

Prove: for any sets A,B, if card(A) = card(B) then
card(A) <= card(B) and card(B) <= card(A).

Proof:

card(A) = card(B) mean there is a bijection f:A --> B.

This f is a 1-1 map from A onto B and so f itself shows
card(A) <= card(B).

As f is a bijection, let g = the inverse of f, g is well-defined
and g:B-->A is 1-1, so this shows that  card(B) <= card(A).

Homework 0 - Problem 6

6. Give examples of two different uncountable sets of real numbers. 

There are many. Let L = {real numbers not equal to 0} and M = {real numbers not equal to 1}

Homework 0 - Problem 7

7. Show that the set of strings in {0,1}* which have exactly one 1 in them is countable. 

First note that the set of all finite strings of 0's and 1's is countable. 

Why ? You can enumerate it without repetitions by first listing the empty string, 
then the 2 binary strings of length 1, then the 4 binary strings of length 2, the 8 binary
string s of length 3,....

Now go through the list I just described and cross out all the strings in the list 
which do not have exactly 1 in it.  You are left with a list S of all binary strings
which have exactly one 1 in them. 

Now define f: N --> {0,1}* by f(i) = the ith string in the list S.

f is a bijection between N and all binary strings which have exactly one 1
showing these strings are countable. 

Homework 0 - Problem 8

8. Give an example of two different countable and infinite languages A and B
over {0,1} with A a subset of B and  whose difference B &minus A is infinite.

Again, an easy one. Let B = {0,1}* and A = {all binary strings which have exactly one 1}.

Homework 0 - Problem 9

To show that the set {S | S is a finite set of binary integers}
is countable, it is sufficient to define a function
g:N --> {S | S is a finite set of binary integers} which is onto.

As we worked out in class, we can define a bijection, say f,  between the 
binary strings and the sets of binary integers by,

A binary string B= b0 b1 b2... bn is mapped to the set
I = {i | bi = 1}

So for example, the binary string 011101 is mapped to the
finite set of integers {1, 2,3,5} or the set of binary integers
{1, 10,11,101}.

So now to define the bijection g above it is enough to
define a function h which enumerates all the binary strings. 
We did this in class, but to make it explicit,

Let h(0) = empty string, h(1) =0, h(2)=1, h(3) = 00,....

and in general, for any k,let  h(2^k -1), h(2^k),...,h(2^{k+1} -2)
have as values the 2^k binary strings of length k in lexicographic order. 

So now h maps N onto the set of binary strings and f maps the binary
strings onto {S | S is a finite set of binary integers}.

Thus f composed with h maps N onto {S | S is a finite set of binary integers}
and is the desired function g. 


10.  If you can, do the same as problem 9 but for all the infinite 
sets of integers ?

You can't. 

Why? 

This is an uncountable set. 

Why? 

You can do the same exact direct diagonalization we did to show the set of all 
infinite sequences of decimal digits (0 through 9) are not countable.