edited by
534 views
4 votes
4 votes
Hello,

I have read that Σ* is countably infinite and power set of Σ* (ie. 2^ Σ*) is uncountably infinite.

So by Cantor’s theorem, power set of any countably infinite set is uncountably infinite.

Then what can be said about 0^any countably infinite set or 3^any countably infinite set? Do these things have any significance?

Thank you.
edited by

1 Answer

1 votes
1 votes
Usually, the power set of an n-element set is denoted by 2^n, as power set will have 2^n elements.

Eg.: Take a finite set of elements, A = {1,2,3}. Here n = 3 (number of elements in the set). Then power set of A would be {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. That is there would be 2^3 number of elements in the power set of A. Remember power set of A is set of subsets of A.

In general, for a set of n elements, the number of elements in its power set would be 2^n. The logic behind being, for each element we have a choice of selecting it or not i.e., 2 choices. We have n elements, therefore 2^n choices and 2^n subsets.

But here we have countably infinite set Σ* and its power set is denoted by 2^ Σ*. Such kind of denotation of power set can also be observed in NFA definition.

Related questions

0 votes
0 votes
0 answers
3
aambazinga asked Jul 15, 2018
805 views
How the set of all non-decreasing functions from N to N are countable?How the set of all finite partitions of N are uncountable?