Countable set

Question

If power set of natural number is uncountable , and that is why non RE,

then how is it possible set of natural number is countable and RE?------give some reason

Comments

a set is countable if there exist an enumeration method using which all the elements of set can be generated and for any particular element ,it takes only finite no. of steps to generate it .these finite steps taken to generate an element can be used as it's index.

set of all natural no. can be generated by this enumeration method-

for(i=0 to infinity)

{ k=i

generate (k)

}

Answer 1

Countable means that there exists one to one mapping between elements of the set to natural numbers and is called RE because since there exists a 1-1 mapping, you can enumerate the elements. So set of natural numbers is trivially countable. But the power set of $N$ is $2^{N}$ and $|2^{N}| > |N|$, so you can't map powerset of natural numbers to set of natural numbers and therefore it is uncountable.

A simple way to prove this is:

lets $N$ is set of Natural numbers and lets assume $P(N)$ is countable and let the mapping be:
$(x_{1} \subseteq P(N) )\rightarrow 1$

$(x_{2} \subseteq P(N) )\rightarrow 2$

$(x_{3} \subseteq P(N) )\rightarrow 3$

.

.

.

where $x_{i}$ is any arbitrary subset of $N$

Then the union of all the subsets i.e. $\bigcup x_{i}$ is a unique set which is in $P(N)$ but isn't mapped to any natural number. Hence our assumption is wrong.

Answer 2

i think above answers are equallt nice ,here is my prespective, i will take an example

say alphabets are {a,b} then all the  strings on the alphbaets can  be given as ( a + b )*

now since the above langauage is countable ( as each strings can be enumerated by a natural number )

now the way of proceeding will be , we will show that there a countable TM , but uncountable language and if we are able to show the above result then we can deduce that , as TM recognises REL so REL are countable , and  NON-REL is subset of a uncountable set which is uncountable thus all NON REL are uncountable.

 => power set of natural number is uncountable , and  (a+b)* is countable so power set of a countable set is uncountable here power set of (a+b)* is set of all the language generated  over {a,b} , which are uncountable. now TM are countable ( as TM machines have finite representation , hence they could be represented by countably finite set of configuration , also called encoding of TM as (0,1). } ,