Question

Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is true?

• A. Both 2Σ* and Σ* are countable.
• B. 2Σ* is countable and Σ* is uncountable.
• C. 2Σ* is uncountable and Σ* is countable.
• D. Both 2Σ* and Σ* are uncountable.

Hint:

Remember Cantor’s theorem: the power set of any set has strictly greater cardinality than the set itself.

Answer 1

The Correct Option is C

Σ∗, representing all finite strings over a finite alphabet Σ, is countable as it is a countable union of finite sets. Its power set, 2Σ∗, is uncountable, since the power set of a countable set is always uncountable (Cantor’s theorem).