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

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. Prove that S has infinite cardinality. 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.

Solution

Ans(1.a):

Cardinality of any set is defined as number of elements in that set.

Let\'s assume that set S is finite. Then set S must have some fixed number of a\'s or b\'s so that number of words formed by all possible different arrangement\'s of a\'s and b\'s is limited to some fixed number.

like say maximum number of a\'s is 5.

But definition of S doesn\'t restrict numbers of a\'s or b\'s so we can again use more number of a\'s like 6 a\'s.

In that case we get more possible words using a\'s and or b\'s.

Which contradicts our assumption that set S is finite.

Then set S must be infinite.

Since S is infinite hence it has infinite cardinality.