1. Suppose that S is the set of all strings of one or more as and bs. 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 cant count the number of elements in an infinite countable set. However, everyone uses this word, so we must use it too.