[proofplan] We reduce counting the languages generated by *all* grammars on $\Sigma$ to counting those generated by grammars whose variable set is a specific countable family. First, for a fixed finite variable set $V$, we show that the set of grammars $(\Sigma, V, P, S)$ is countable by bounding the number of rewrite systems over $\Omega = \Sigma \cup V$ and noting that the choice of start symbol contributes only a finite factor. Second, the Renaming Variables theorem lets us replace "any variable set" by "the standard $n$-element set" without changing which language is generated. The global collection of generated languages is therefore a countable union $\bigcup_{n \geq 1} \mathcal{L}_n$, which is countable as a countable union of countable sets. [/proofplan] [step:Reduce to counting grammars with each fixed variable set] Let \begin{align*} \mathcal{L} &:= \{\,\mathcal{L}(G) \;\big|\; G \text{ is a grammar on } \Sigma\,\} \end{align*} be the collection of all languages generated by grammars on $\Sigma$ (with variable sets allowed to vary). Every grammar $G = (\Sigma, V, P, S)$ has a finite variable set $V$, and for each such grammar the cardinality $|V|$ is a positive integer. Grouping grammars by the cardinality of their variable set, we have the decomposition \begin{align*} \mathcal{L} &= \bigcup_{n \geq 1} \mathcal{L}^{(n)}, & \mathcal{L}^{(n)} &:= \{\,\mathcal{L}(G) \;\big|\; G \text{ is a grammar on } \Sigma \text{ with } |V| = n\,\}. \end{align*} We will show that each $\mathcal{L}^{(n)}$ is countable; since $\{n \in \mathbb{N} \mid n \geq 1\}$ is countable, a countable union of countable sets is countable, giving $\mathcal{L}$ countable. [/step] [step:Fix a standard $n$-element variable set via the renaming theorem] For each integer $n \geq 1$, let \begin{align*} V_n &:= \{A_1, A_2, \dots, A_n\} \end{align*} be a fixed $n$-element set disjoint from $\Sigma$ (e.g., $A_i$ can be taken as formal symbols not in $\Sigma$; their precise identity is irrelevant provided the set has cardinality $n$). Let \begin{align*} \mathcal{G}_{V_n} &:= \{\,G = (\Sigma, V_n, P, S) \;\big|\; G \text{ is a grammar}\,\}, \\ \mathcal{L}_{V_n} &:= \{\,\mathcal{L}(G) \;\big|\; G \in \mathcal{G}_{V_n}\,\}. \end{align*} **Claim.** $\mathcal{L}^{(n)} = \mathcal{L}_{V_n}$. The inclusion $\mathcal{L}_{V_n} \subseteq \mathcal{L}^{(n)}$ is immediate because every $G \in \mathcal{G}_{V_n}$ has variable set of cardinality $n$. For the reverse inclusion $\mathcal{L}^{(n)} \subseteq \mathcal{L}_{V_n}$, fix any $L \in \mathcal{L}^{(n)}$. Then $L = \mathcal{L}(G)$ for some grammar $G = (\Sigma, V, P, S)$ with $|V| = n$. Since $|V| = |V_n| = n$, the [Renaming Variables](/theorems/1778) theorem produces $P'$ and $S'$ such that $G' := (\Sigma, V_n, P', S')$ is a grammar and $\mathcal{L}(G) = \mathcal{L}(G')$. Thus $L = \mathcal{L}(G') \in \mathcal{L}_{V_n}$. [/step] [step:Show that the set of rewrite systems on $\Sigma \cup V_n$ is countable] Fix $n \geq 1$ and write $\Omega_n := \Sigma \cup V_n$. Since $\Sigma$ is finite (by hypothesis) and $V_n$ is finite with $|V_n| = n$, $\Omega_n$ is a finite alphabet. The set of finite strings \begin{align*} \Omega_n^\star &= \bigcup_{k \geq 0} \Omega_n^k \end{align*} is a countable union of finite sets (each $\Omega_n^k$ has cardinality $|\Omega_n|^k$), hence countable. A *rewrite system* on $\Omega_n$ is a finite subset $P \subseteq \Omega_n^\star \times \Omega_n^\star$ of production rules. The set $\Omega_n^\star \times \Omega_n^\star$ is a product of two countable sets, so it is countable. The set of finite subsets of any countable set is itself countable: indexing finite subsets by their cardinality, \begin{align*} \{\,F \subseteq \Omega_n^\star \times \Omega_n^\star : F \text{ finite}\,\} &= \bigcup_{k \geq 0} \binom{\Omega_n^\star \times \Omega_n^\star}{k}, \end{align*} each $\binom{X}{k}$ is a subset of $X^k$ (via listing elements in some order) and $X^k$ is countable when $X$ is, so the displayed union is a countable union of countable sets. Hence the set $\mathcal{R}_{V_n}$ of rewrite systems on $\Omega_n$ is countable. [/step] [step:Conclude that $\mathcal{G}_{V_n}$ is countable] A grammar with alphabet $\Sigma$ and variable set $V_n$ is specified by a pair $(P, S)$ consisting of a rewrite system $P \in \mathcal{R}_{V_n}$ and a start symbol $S \in V_n$. The map \begin{align*} \mathcal{R}_{V_n} \times V_n &\to \mathcal{G}_{V_n} \\ (P, S) &\mapsto (\Sigma, V_n, P, S) \end{align*} is a surjection (every grammar with fixed $\Sigma$ and $V_n$ arises this way) from a product of a countable set and a finite set. A product of a countable set with a finite set is countable, so $\mathcal{R}_{V_n} \times V_n$ is countable; the surjective image of a countable set is countable, giving \begin{align*} |\mathcal{G}_{V_n}| &\leq \aleph_0. \end{align*} The assignment $G \mapsto \mathcal{L}(G)$ is a surjection $\mathcal{G}_{V_n} \twoheadrightarrow \mathcal{L}_{V_n}$, so $\mathcal{L}_{V_n}$ is also at most countable. [guided] The key distinction is between the *data* of a grammar (variable set, rule set, start symbol) and the *language* it generates. Two different grammars can generate the same language, so strictly speaking the map $G \mapsto \mathcal{L}(G)$ is not injective — but we only need a surjection to transport countability from the domain to the image. The counting argument has three layers of "countable": 1. The finite alphabet $\Omega_n$ produces countably many finite strings, because $\Omega_n^\star = \bigcup_k \Omega_n^k$ is a countable union of finite sets. 2. Finite subsets of a countable set form a countable set, because subsets of cardinality $k$ can be identified (non-uniquely) with elements of $(\Omega_n^\star \times \Omega_n^\star)^k$ modulo ordering/repetition, and countable products are countable. 3. The product of a countable set (the rewrite systems) with a finite set (the choice of start symbol from $V_n$) is countable. Each layer preserves countability, and layering gives $\mathcal{G}_{V_n}$ countable. The final surjection $G \mapsto \mathcal{L}(G)$ then transports countability from grammars to languages. Why does this fail for $P$ infinite? A grammar is required to have a *finite* rule set; if we allowed infinite $P$ there would be $2^{\aleph_0}$ many rewrite systems (the power set of the countable string-pair space is uncountable) and the argument would collapse at step 3. [/guided] [/step] [step:Assemble the countable union and conclude] Combining the previous steps, \begin{align*} \mathcal{L}^{(n)} &= \mathcal{L}_{V_n} \quad \text{(step 2)}, \\ \mathcal{L}_{V_n} &\text{ is countable} \quad \text{(step 4)}. \end{align*} Hence each $\mathcal{L}^{(n)}$ is countable. From step 1, \begin{align*} \mathcal{L} &= \bigcup_{n \geq 1} \mathcal{L}^{(n)}. \end{align*} A countable union of countable sets is countable, so $\mathcal{L}$ is countable, completing the proof. [/step]