1 Suppose that S is the set of all strings of one or more as

1. Suppose that S is the set of all strings of one or more a’s and b’s. For example, S contains the strings \"a\", \"b\", \"aa\", \"ab\", \"ba\", \"bb\", \"aaa\", \"aab\", etc.

1a. Prove that S has infinite cardinality. Hint: use a proof by contradiction.

1b. A set is countable if and only if (1) it is finite, or (2) it has the same cardinality as the set of integers greater than 0 (see Rosen, page 171). Prove that S is countable.

Note: the word countable is unfortunate, since we can’t count the number of elements in an infinite countable set. However, everyone uses this word, so we must use it too.

Solution

1 A:- Given is S is set of strings of one or more a\'s and b\'s.

Now let us assume S is finite and S has S={a,b,aab,baa}. Then S cardinality is 4. But now as it is given that S is a set of strings of one or more a\'s and b\'s then aaab should also be there or baaaa should also be there,  this Contradicts  our assumption which is S is finite. Hence S has infinite cardinality.

1B:- A Set is countable if and only if it is finite. We can prove this by taking an example.

Example:- S set of integers greater than 2 and less than 7 then S={3,4,5,6} . So here we can count the number of elements present is set S which is 4. Thus any set which is finite is countable.

Now in our problem we have to proove S is countable. We have already proved that S is having infinite cardinality. The elements of the set S can be mapped to set of integers greater than 0

Set s Integer set

a - - -- ----- -------- ------ ----> 1

b - - -- ----- -------- ------ ----> 2

aab - - -- ----- -------- ------ ----> 3

bba - - -- ----- -------- ------ ----> 4

so on so on

So now the set of integers greater than zero is countable infinite so set S is also countable infinite .

Here the mapping is one to one correspondence . one to one correspondence means a function should be injective and surjective