1. Suppose that S is the set of all strings of one or more a’s and b’s. For exam

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.