Let \(Σ\) be a finite non-empty alphabet and let \(2^{∑^*}\) be the power set…
2014
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
Attempted by 82 students.
Show answer & explanation
Correct answer: C
Final answer: 2^{Σ*} is uncountable and Σ* is countable.
Why Σ* is countable: Because Σ is finite and non-empty, Σ* = ⋃_{n≥0} Σ^n. Enumerate strings by increasing length (first length 0, then length 1, then length 2, …); within each length, list strings in lexicographic order. This gives a sequence that lists every string, so Σ* is countably infinite.
List all strings of length 0 (the empty string).
Then list all strings of length 1, then length 2, and so on.
Why the power set 2^{Σ*} is uncountable: Cantor's theorem implies that for any set X, the power set P(X) has strictly greater cardinality than X. Since Σ* is countably infinite, its power set has cardinality 2^{ℵ0}, which is uncountable.
Assume for contradiction that all subsets of Σ* can be listed as S1, S2, S3, ….
Define the diagonal subset D = { w in Σ* | w is not in S_k where k is the index of w in some fixed enumeration of Σ* }.
By construction D differs from each listed subset S_k at least on the string with index k, so D cannot be on the list. This contradiction shows the power set cannot be listed and is therefore uncountable.
Thus the correct statement is: the set of all finite strings Σ* is countable, while its power set 2^{Σ*} is uncountable.