证明整系数多项式全体是可列的.

Proof.  整系数多项式形如

\[
P_n(x)=a_0 x^n+a_1 x^{n-1}+a_2 x^{n-2}+\cdots+a_{n-1} x+a_n,
\]

其中 $a_i\in\mathbb{Z}$, $i=0,1,2,\ldots,n$, 且 $a_0\neq 0$.  将所有这种多项式构成的集合记为 $\mathcal{P}$.

我们可以将整个集合按照多项式的阶分组, 比如 $\mathcal{P}_n$ 表示所有 $n$ 阶整系数多项式全体. 则

\[\mathcal{P}=\mathcal{P}_0\cup\mathcal{P}_1\cup\mathcal{P}_1\cup\mathcal{P}_2\cup\cdots\cup\mathcal{P}_n\cup\cdots\]

于是只要证明每个 $\mathcal{P}_k$ 是可列的. 而 $\mathcal{P}_k\cong\mathbb{N}\times\mathbb{N}\times\cdots\times\mathbb{N}=\mathbb{N}^{k+1}$ 显然是可数集.

References