型推栄の5分で定理 #1

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

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

さて、ここで正の整数 $k$ に対して $[k]$ で $k$ 以下の自然数からなる集合を表す。$\mathrm{\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,\dots$ と付番する（例えば $p_1=2,p_2=3,p_3=5$ である）。そこで写像 $g:2^{\mathrm{\Sigma }}\to \mathbb{N}$ を次の通り定義する。

$$g(s_{f(1)}\cdots s_{f(n)}):=p_1^{f(1)}\cdots p_n^{f(n)}$$

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

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