Countable Set & Formal Grammar

Question

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers.

I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary alphabet. every one would please help me and add some hints for each one, or if I'm wrong correct me !! thanks to all.

1) Each arbitrary Language on $\Sigma$ is Countable.

2) the set of all language from $\Sigma$ is Countable.

3) for Each arbitrary Language on $\Sigma$ we have a generative formal grammar.

4) Each arbitrary Language on $\Sigma$ that generated by formal grammar, is recursive.

Answer 1

1. If $\Sigma$ is any finite alphabet (or even countably infinite), then $\Sigma^*$ is countable, hence so is any language on $\Sigma$

2. Let $a\in\Sigma$ be an arbitrary letter. Then for any subset $A\subseteq\mathbb N$, we have the language $\{\,a^n\mid n\in A\,\}$. As there are uncoutably many subsets of $\mathbb N$, there are uncountably many languages.

3. Grammars are allowed to have only finitely many rules and metavariabables, hence there are only countably many grammars - less than there are languages.

4. Indeed, one can transform a grammar into a Turing machine that shows recursiveness.