解答例  本問の主旨は，集合や数の性質の分析ではなく，第１章の主旨である記 号$\mathrm{\Sigma }$による情報の表現の原理と限界を理解することである． そこで，以下数学的な性質などを極力避け，$\mathrm{\Sigma }$による情報の表現の観点 から具体的な分析を行う．

1. 1.

   以下の方針で$\mathrm{\Sigma }{}^{*}$の要素に$0$から始まる通し番号をつけることができる．

   1. (a)

      $\mathrm{\Sigma }{}^{*}=\bigcup \{\mathrm{\Sigma }{}^k|k\ge 0\}$であり， $k\ne l$なら$\mathrm{\Sigma }{}^k\cap \mathrm{\Sigma }{}^k=\mathrm{\varnothing }$であるから， $\mathrm{\Sigma }{}^{*}$は，$\{\mathrm{\Sigma }{}^k|k\ge 0\}$に分割できる．

   2. (b)

      $\mathrm{\Sigma }$の要素数を$n$とし，$\mathrm{\Sigma }=\{a{}_0,\mathrm{\cdots },a{}_{n-1}\}$とする． $\mathrm{\Sigma }{}^k$の要素数は$n{}^k$である． この$n{}^k$個の各要素を，$a{}_0$から$a{}_{n-1}$を $n$個の数字とする $k$桁の$n$進数表現と見做すことにより， $0$から$n{}^k-1$の数を一意に割り当てることができる． ただし，$ϵ\in \mathrm{\Sigma }{}^0$には$0$を割り当てる． この要素$w\in \mathrm{\Sigma }{}^k$に割り当てられた数を$num(w)$と書く．

   3. (c)

      $\mathrm{\Sigma }{}^0\cup \mathrm{\Sigma }{}^1\cup \mathrm{\cdots }\mathrm{\Sigma }{}^{k-1}$の要素数は $1+n{}^1+\mathrm{\cdots }+n{}^{k-1}=\frac{n{}^k-1}{n-1}$である． $\mathrm{\Sigma }{}^{*}$の要素$w$に対して， $w$が$\mathrm{\Sigma }{}^k$に属するなら， その通し番号を$num(w)+\frac{n{}^k-1}{n-1}$とする．

   例えば$\mathrm{\Sigma }=\{0,1\}$の場合の通し番号のいくつかを以下に示す．

   $w\in \mathrm{\Sigma }{}^{*}$	$ϵ$	$0$	$1$	$00$	$01$	$10$	$11$	$000$	$001$	$\mathrm{\cdots }$
   通し番号	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$\mathrm{\cdots }$

   実際，$001\in \mathrm{\Sigma }{}^3$の通し番号は，$num(001)=1$であるから$1+\frac{2{}^3-1}{2-1}=8$である． この通し番号は連続しており，重なりがないから， $\mathrm{\Sigma }{}^{*}$は自然数の集合と１対１に対応することがわかる．

2. 2.

   自然数から自然数への関数全体の集合は数え上げることができない（非可算である）． （もし数え上げ系列$\{f{}_0,f{}_1,\mathrm{\dots },f{}_n,\mathrm{\dots }\}$が存在するとすると， この系列の何処にも出てこない関数 $f(n)=f{}_n(n)+1$が定義できてしまい，矛盾してしまう．（対角線論法）） 一方，プログラムは$\mathrm{\Sigma }{}^{*}$の要素であるから，項目１の通し番号の若い順に 通し番号をつけることができる． したがって，自然数から自然数への関数全体の集合には，プログラムでは表現できない 関数が存在する． 非可算集合から可算集合を取り除いた要素が有限であれば，非可算集合は数え上げることが できてしまうので，プログラムでは表現できない関数は無限に存在する．

3. 3.

   有理数係数の代数方程式は，有限の記号（数字，変数名，プラス・マイ ナス記号，等号等）で書かれたものであるから，これらの方程式を書き下すために必要な 記号を$\mathrm{\Sigma }$と取れば，個々の方程式は$\mathrm{\Sigma }{}^{*}$の要素である． 項目１から，すべての有理数係数の代数方程式の集合は可算無限である． 一つの方程式の解は高々有限個であるため，有理数係数の代数方程式の解の集合 は，有限の要素をもつ可算無限個の集合の和集合である． この和集合の要素は，それが属する集合の順に数え上げることができる ため，可算無限である． 従って，有理数係数の代数方程式で表しうる実数の集合は，この可算無 限集合の部分集合であり，可算である． 一方，実数の集合は非可算である（項目2と同様に，対角線論法で示すことができる）． 以上から，実数の集合には，有理数係数の代数方程式で表し得ない数が無限に存在する．

   （注釈）教科書の初版では，「代数方程式」を「連立方程式」としているが，正誤表の通り， 代数的数の定義は「有理数係数の（一変数の）代数方程式の解と表される数」である． ただし，本問の主旨は，代数的数の集合が可算であることは，代数的数の性質等によらず，

   「記号で表現できる式は$\mathrm{\Sigma }{}^{*}$の要素であり，従ってそのような式全体の集 合は可算である」

   という性質のみをつかって導かれる性質であることを理解する ことである． 従ってこの議論は，記号で表記できる有限個の解をもつ「方程式」で表現可能な数と 一般化しても，問題なく成立する．