33 votes 33 votes Let $\Sigma$ be a finite non-empty alphabet and let $2^{\Sigma^*}$ be the power set of $\Sigma^*$. Which one of the following is TRUE? Both $2^{\Sigma^*}$ and $\Sigma^*$ are countable $2^{\Sigma^*}$ is countable and $\Sigma^*$ is uncountable $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable Both $2^{\Sigma^*}$ and $\Sigma^*$ are uncountable Theory of Computation gatecse-2014-set3 theory-of-computation normal countable-uncountable-set + – go_editor asked Sep 28, 2014 edited Jun 26, 2017 by Silpa go_editor 9.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments ayush3298 commented Dec 10, 2020 reply Follow Share Arjun sir, I too think it should be in toc, countability. 0 votes 0 votes Pranavpurkar commented Oct 26, 2022 i edited by Pranavpurkar Oct 26, 2022 reply Follow Share @Mk Utkarsha bijective mapping or one to one correspondence to natural numbers must be there for a set to be countable. 0 votes 0 votes Deepak Poonia commented Sep 24, 2023 reply Follow Share $\color{red}{\text{Detailed Video Solution, with Proof:}}$ https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=2515s 1. For EVERY alphabet $\Sigma$, the language $\Sigma^*$ is countable. Proof HERE OR HERE.2. For EVERY $\Sigma,$ the set of all languages is uncountable.The set of all languages over $\Sigma$ is the powerset of $\Sigma^*$ i.e. $P(\Sigma^*).$Proof:By Cantor’s theorem, we know: If $S$ is ANY infinite set, then $P(S)$ is always uncountable. (Or we can say, NO infinite powerset is countable.)Since, for every $\Sigma$, $\Sigma^*$ is infinite, hence, $P(\Sigma^*)$ is uncountable.Learn Cantor’s Theorem & its Consequences HERE.Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared 1 votes 1 votes Please log in or register to add a comment.
–1 votes –1 votes Option (C) 2^ (Σ *) is uncountable and Σ *is countable ,is the correct answer. Warrior answered Jul 29, 2017 Warrior comment Share Follow See all 0 reply Please log in or register to add a comment.