The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.9k views

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
asked in Set Theory & Algebra by Veteran (112k points)
edited by | 1.9k views
0
If in question they ask summation is infinite set then what is the answer give with explanation
+10

Definition - A set S is called countable if there exists an injective(one to one) function f from S to the natural numbers N.

Let Σ = a then Σ* = {∈,a, aa, aaa, aaaa, aaaaa,..........} this is similar to the set of natural numbers {0,1,2,3.......}
Hence there exist a one to one function for every element in Σ* hence Σ* is countable.

Theorem- S is a countably infinite set, then power set is uncountably infinite.

then $2^{\sum ^{*}}$ is uncountable

0
Does the set of natural numbers is countably infinite?
0

5 Answers

+23 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 $∑ = {a,b }$ and there exist a enumeration procedure to generate all the string of the language  $∑$$^{*}$.

$∑$$^{*}$.$=$ ${ ∈$ , a , b , aa, ab, ba, bb , aaa , ........ }$

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

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

Because the power set of countably infinite set are uncountable.

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

answered by Loyal (7.8k points)
edited by
+4 votes
c,by diagonalisation theorem
answered by (335 points)
+1 vote

Ans is C

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

answered by Active (1.1k points)
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.)

answered by Loyal (8.7k points)
–2 votes

Option (C) 2^ (Σ *​​​​​​​)​​​​​​​ is uncountable and Σ *is countable ,is the correct answer.

answered by Loyal (7.1k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,317 questions
49,817 answers
164,583 comments
65,869 users