Decidable Languages over an alphabet

Question

How can we prove that exist as many decidable languages over {1, 0} as over the alphabet {0}.

I understand that the number of turing machines over an alphabet is countable. But how can we formulate a proof for this case?

Answer 1

As there are only countably many Turing machines over a finite alphabet, there can only be countably many decidable languages over that same alphabet.

There are infinitely many decidable languages over the alphabet $\{0\}$: for example, consider the family of languages $L_n$ consisting of a single string $$L_n = \{\underbrace{00\dots0}_n\}$$ of $n$ zeroes. These are all decidable, and there are infinitely many of them. As we've mentioned there can only be countably many decidable languages over $\{0\}$, this means there are countably infinitely many decidable languages over $\{0\}$; i.e., there are as many decidable languages over $\{0\}$ as there are natural numbers.

Since $\{0,1\}$ is a bigger alphabet, it must have at least as many decidable languages (any decidable language over $\{0\}$ is decidable over $\{0,1\}$). Therefore, it has at least countably infinitely many decidable languages. However, it can only have countably many decidable languages, as before, so the number of decidable languages over $\{0,1\}$ must also be countably infinite; i.e., as numerous as the natural numbers.

Since both sets of decidable languages are as numerous as the natural numbers, there must be as many decidable languages over $\{0\}$ as over $\{0,1\}$.

In summary, the reason is because there is only one cardinality that is both countable and infinite.