Doubt regarding countable and uncountable sets

Question

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.

Comments

What do you mean by "0^any countably infinite set"? What is "0" here exactly?

---

Oops, I meant 0 ^ any countably infinite ( zero raised to the power any countably infinite set). I am not even sure if it has any significance but since 2 ^ any countably infinite is uncountably infinite, I had a doubt what if we replace 2 by 0 or 3 (or 4,5 etc).

---

$2^{anyset} $ denotes the power set of a set.

See this: https://math.stackexchange.com/questions/1874399/power-set-notation

According to the above source

In set theory, given two sets A,B the notation $A^B $ is often used to denote the set of all functions f:B→A

So, as you say, if we take 2={0,1} then $2^S$ is the set of functions f:S→{0,1}

Hence if you want to say A is a set of a finite number of elements and B is a countable infinite set then yes the resultant set will be uncountably infinite.

Answer 1

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.