# There are more languages than programs?

I am reviewing some Turing machine material...and I come across this

the set of all programs are countable (convert them into binary string, each of which represent an integer) whereas the set of all languages over {0,1} are not

I know that the set of all possible words(call it X) over {0,1} (this is the same as set of all binary string) is countable...but the set of all languages over {0,1} isn't it the power set of X, ie the set of all subset of X?

I also know that for an finite set, order of power set of X is $2^{|X|}$, so are we saying that $2^{\infty} \gt \infty$? How can I distinguish relationship between infinity in general? For instance, we have on the contrary: 2*\infty = \infty since set of all positive even integers has the same cardinality all positive integers...

I feel like this has something to do with the infinite set theory, and the prove I saw is the diagonalization argument which I am still having trouble digesting, does there exist better proofs?

Also, see Cantor's theorem on power sets set and the continuum hypothesis. You will see infinities are of different orders, for example, there are more real numbers than natural numbers. In fact if you let $n_0 =|\mathbb{N}|$ and $n_1 =|\mathbb{R}|$, then using that $2^{\mathbb{N}}$ is in bijective correspondence with $\mathbb{R}$, you can say that $2^{n_0} = n_{1}$. There's actually a hierarchy of infinities that you can build in similar manner.