in Theory of Computation edited by
9,490 views
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

  1. Both $2^{\Sigma^*}$ and $\Sigma^*$ are countable
  2. $2^{\Sigma^*}$ is countable and $\Sigma^*$ is uncountable
  3. $2^{\Sigma^*}$ is uncountable and $\Sigma^*$ is countable
  4. Both $2^{\Sigma^*}$ and $\Sigma^*$ are uncountable
in Theory of Computation edited by
9.5k views

4 Comments

Arjun sir, I too think it should be in toc, countability.

0
0
edited by

@Mk Utkarsh

a bijective mapping or one to one correspondence to natural numbers must be there for a set to be countable.

0
0

$\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
1

5 Answers

44 votes
44 votes
Best answer

A set is countable means there exist a enumeration procedure to generate each of its elements and  for a given element of set, it take finite step to generate it using the enumeration procedure.

Let $\Sigma = \{a,b \}$ and there exist a enumeration procedure to generate all the string of the language  $\Sigma^*$.

$\Sigma^{*}=\{ \epsilon , a , b , aa, ab, ba, bb , aaa , \ldots \}$

Here, enumeration procedure is simply the generating string of the language  by length for the fixed length string are in alphabetical order.

This way $\Sigma^{*}$ is countably infinite & $2^{\Sigma ^{*}}$ will be uncountable set

Because the power set of any countably infinite set is uncountable.

Ref: http://www.cs.xu.edu/csci250/06s/Theorems/powerSetuncountable.pdf

Correct Answer: $C$

edited by

2 Comments

In terms of mathematics, a set S is countable if there exists a bijection to the set of Natural Numbers N

$f(S) \to f(N)$ such that each member of set S can be given a finite index.
1
1

Proof explained very well here:

https://www.youtube.com/watch?v=cS51eYcGZZM

2
2
5 votes
5 votes
c,by diagonalisation theorem
1 vote
1 vote

Ans is C

see refence :-  http://www.pling.org.uk/cs/toc.html

by
0 votes
0 votes

Theorem- S is a countably infinite set, 2 S (the power set) is uncountably infinite.

Proof: We show 2 S is uncountably infinite by showing that 2 N is uncountably infinite. (Given the natural bijection that exists between 2 N and 2 S –because of the bijection that exists from N to S– it is sufficient to show that 2 N is uncountably infinite.) Assume that the set 2 N is countably infinite. The subsets of N can be listed A0, A1, A2, . . . so that every subset is Ai for some i. We define another set A = {i|i ≥ 0 and i 6∈ Ai} which contains those integers i which are not members of their namesake set Ai . But A is a subset of N, and so A = Aj for some j. But this means 1. If j ∈ A, then j 6∈ A. 2. If j 6∈ A, then j ∈ A. We have a contradiction, since j must either be in the set A or not in the set. Therefore 2 N is not countably infinite. ⋄ The Theorem that the power set of a countably infinite set is an uncountable set indicates that the set of all languages over any alphabet Σ, |Σ| 6= 0 is uncountable. (2 Σ∗ is an uncountable set.)

Answer:

Related questions