0
$\begingroup$

Given the theorem:

Let $\Sigma$ be an alphabet. The set $\mathcal{P} \left( \Sigma^{\star} \right) $ is uncountable. In other words, there are uncountably infinite languages over any alphabet.

Can someone explain to me how does it hold for $| \Sigma | = 1$ ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The thing you need to remember is that even if Σ has only one symbol , Σ* still has infinite strings over that one symbol , even if Σ = {a} , Σ* = {ε,a,aa,aaa,....} , (a^n , n≥ 0) , Σ* has infinite strings just like with any other alphabet , and so we can form infinite languages over an alphabet with a single symbol just like other alphabet , if now you are convinced that Σ* is infinite even if |Σ|=1 just like any other alphabet , then just as you believe that P(Σ*) for |Σ| >1 is uncountably infinite , hopefully you can see now that P(Σ*) for |Σ| = 1 is also uncountably infinite , since in both cases it is P(some infinite language) , which in both cases is uncountably infinite

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see how it answers the question. There is even no word "uncountable" in your answer. $\endgroup$
    – user114966
    Nov 16, 2020 at 17:24
  • $\begingroup$ The question doubts that P(Σ*) holds true for |Σ| = 1 , but beleives it holds true for alphabets with more than one symbol , by showing that Σ* is infinite for |Σ| = 1 just as any other alphabet with more than one symbol , we show that the same argument used for alphabets with more than one symbol can be used for alphabet with only one symbol , since in both cases Σ* would be infinite , and thus in both cases we will have P(some infinite language) which is uncountably infinite , as for how to show that there are uncountably infinite languages over some alphabet , this is another question $\endgroup$
    – Moslem
    Nov 16, 2020 at 17:46
  • $\begingroup$ It is hard to understand what's the main point of your comment, but it seems that the main part is that P(infinite language) is uncountably infinite. If so, you should add this to the answer (referencing the Cantor's theorem). $\endgroup$
    – user114966
    Nov 16, 2020 at 20:14
  • $\begingroup$ Thank you for your comments , I reread my answer and I thought I should have explained further why the language is uncountable and not just why it is infinite , the main point I want to make is that Σ* is infinite , for |Σ| ≥ 1 , and so P(Σ*) is uncountable for |Σ| ≥ 1 $\endgroup$
    – Moslem
    Nov 16, 2020 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.