型推栄の5分で定理 #1

以下、自然数とは1以上の整数のことをいい、$\mathbb{N}$で自然数全体を指すものとする。
またアルファベットの集合$\Sigma$に対し、$2^\Sigma$は（冪集合でなく）$\Sigma$上の語全体がなす集合を表す。

$L$ をアルファベット $\Sigma$ 上の勝手な形式言語とすると、 $ L \subseteq 2^\Sigma$ である。ここで $\Sigma$ は可算であるから、要素である各文字は自然数によって $s_1, s_2, \ldots \in \Sigma$ と付番できる。

さて、ここで正の整数 $k$ に対して $[k]$ で $k$ 以下の自然数からなる集合を表す。$\Sigma$ 上の長さ $n > 0$ の語 $w$ が写像 $f: [n] \to \mathbb{N}$により $w \equiv s_{f(1)} \cdots s_{f(n)}$ と表せるとする。なお、そのような $f$ は長さ1以上のどんな語 $w$ に対しても必ず存在する。

ところで素数は可算無限個存在するから、素数を小さい順に $p_1, p_2, p_3, \ldots$ と付番する（例えば $ p_1 = 2, p_2 = 3, p_3 = 5$ である）。そこで写像 $g: 2^{\Sigma} \to \mathbb{N}$ を次の通り定義する。

\begin{equation} g(s_{f(1)} \cdots s_{f(n)}) := p_1^{f(1)} \cdots p_{n}^{f(n)} \end{equation}

ただし、空語$\lambda$に対しては$g(\lambda) = 1$と約束する。

この方法により任意の $w \in 2^\Sigma$ に自然数 $g(w)$ を対応づけることができ、また素因数分解の一意性から $g$ は明らかに単射である。よって $|2^\Sigma| \le |\mathbb{N}|$ であるから、 $L$ もやはり高々可算である。