2018-02-04

非加算無限集合

大学数学

前回、加算非加算無限 - ほぼ数学科の大学生の備忘録。この記事の最後で実数全体の集合 $\mathbb{R}$ は非加算無限集合であるという話をしました。
今回は、対角線論法を用いたその証明をしたいと思います。

まず、区間 $I=(0,1)$ から $\mathbb{R}$ には全単射が存在します。例えば、
$g(x)=tan\left(\cfrac{2x-1}{2} \pi \right)$
とすれば、gは全単射です。

従って、自然数全体の集合 $\mathbb{N}$ から区間 $I=(0,1)$ に全単射がないことを示せばよいことになります( $\mathbb{N}$ から $I$ に全単射があれば上の全単射と合成することで $\mathbb{N}$ から $\mathbb{R}$ への全単射が作れますし、 $\mathbb{N}$ から $I$ に全単射がなければ $\mathbb{N}$ から $\mathbb{R}$ に全単射があると上の全単射の逆写像と合成することで $\mathbb{N}$ から $I$ に全単射が作れてしまい矛盾するからです)。

ここで、 $\mathbb{N}$ から $I$ に全単射fが存在するとします。このとき、
$\displaystyle I=\{a_i\ |\ i \in \mathbb{N},a_i=f(i)\}=\{a_1,a_2,a_3,\cdots \}$
と書けます。この各 $a_i$ に対して、2進数展開をします。つまり、
$\displaystyle a_i=\sum_{j=1}^{\infty} a_{ij}2^{-j}$
となるような $a_{ij}$ を考えます。ここで、各 $a_{ij}\in {0,1}$ です。

この $a_{ij}$ に対し、 $b_i=\lnot a_{ii}$ とします。但し $\lnot$ はビット反転を表す記号で、0だったものを1に、1だったものを0にします。つまり、
$\displaystyle b_i= \begin{cases} 1\ (a_{ii}=0のとき) \\ 0\ (a_{ii}=1のとき) \end{cases}$
となります。ここで、
$\displaystyle b=\sum_{i=1}^{\infty} b_i 2^{-i}$
とすれば、たしかに $b \in I$ ですが、どの $a_i$ とも $2^{-i}$ の桁の係数が違うので矛盾します。

以上より $\mathbb{N}$ から $I$ には全単射fが存在しなことが分かり、 $I$ や $\mathbb{R}$ は非加算無限集合であることが示せました。

このような論法（すべての要素から一つずつ取ってきたものを用いる方法）を対角線論法といいます。

2018-02-03

加算非加算無限

大学数学

無限には二種類あるということを知っていますか？

聞いたことがある人も多いと思いますが、無限は自然数の無限である加算無限と、実数の無限である非加算無限があります。

無限集合のうち、自然数全体の集合 $\mathbb{N}$ から全単射が存在する集合を加算無限集合といいます。逆に、 $\mathbb{N}$ からの全単射が存在しない集合を非加算無限集合といいます。
全単射が存在するということは、その集合の要素に一対一対応が存在するということなので、イメージとしては集合の要素の「数」が同じ、ということです。

感覚として分かる人も多いかと思いますが、例えば自然数のうち偶数だけを取ってきた集合(ここでは $\mathbb{N}_{even}$ と書きます)や、整数全体の集合 $\mathbb{Z}$ は加算無限集合です。
$\mathbb{N}$ から $\mathbb{N}_{even}$ への全単射fは、例えば
$\displaystyle f(n)=2n$
とすることで得られ、 $\mathbb{N}$ から $\mathbb{Z}$ への全単射gは、例えば
$\displaystyle g(n)=\begin{cases} \cfrac{n-1}{2}\ (nが奇数) \\ \cfrac{n}{2}\ (nが偶数) \end{cases}$
とすることで得られます。

また、非加算無限集合の代表例は、実数全体の集合 $\mathbb{R}$ です。
$\mathbb{N}$ と $\mathbb{R}$ の間に全単射が存在しないことを示すには、対角線論法という論法を使うのですが、これの説明は次回に回したいと思います。

2017-10-01

Legendre多項式関連の式

大学数学

Legendre多項式についての次の式の証明がネットで調べても見つからなかったので紹介しておきます。 $P_n(cos \theta )=\cfrac{1}{n} \sum_{r=1}^n cos(r \theta )P_{n-r}(cos \theta ) \tag{1}$ まず、n=1,2については、 \[ P_0(x)=1,\ P_1(x)=x,\ P_2(x)=\cfrac{3x^2-1}{2}\]などから直接示すことができます(cosの加法定理を用います)。次に、n=k,k-1での成立を仮定します。ここで重要になるのは、cosについての次の式です。 \[ \tag{2} \cos(r+1)\theta+\cos(r-1)\theta=2\cos\theta\cos r\theta \] また、ボネの漸化式と呼ばれる以下の漸化式も、今回の証明に利用しますが、そうでなくてもLegendre多項式の重要な式の一つです。 \[\begin{align} \tag{3} (n+1)P_{n+1}(x)=(2n+1)P_n(x)-nP_n(x)\end{align} \] 以下、 \[ Q_n(\theta)=\sum_{r=1}^k\cos(r\theta)P_{k-r}(\cos\theta)\] とします。このとき、（１）式は \[ P_n(\cos\theta)=\cfrac{1}{n}Q_n(\cos\theta) \] と書けます。また、（２）式より、 $\begin{align} 2\cos\theta Q_n(\cos\theta)&=\sum_{r=1}^k\cos(r+1)\theta \ P_{k-r}(\cos\theta)+\sum_{r=1}^k\cos(r-1)\theta \ P_{k-r}(\cos\theta)\\ &=\left(Q_{k+1}(\cos\theta)-\cos\theta\ P_k(\cos\theta)\right)+\left(Q_{k-1}(\cos\theta)+P_{k-1}(\cos\theta)\right)\end{align}$
となります（１行目→２行目は余分な項を引いて帳尻を合わせています）。さらに変形を進めて、
$\begin{align} Q_{k+1}(\cos\theta)&=(2k+1)\cos\theta\ P_k(\cos\theta)-k\ P_{k-1}(\cos\theta)\\ &=(k+1)P_{k+1}(\cos\theta) \end{align}$
これは、（１）式がn=k+1でも成立することを表しています。以上より、任意の自然数nに対して、 \[ P_n(\cos\theta)=\cfrac{1}{n}\sum_{r=1}^n\cos(r\theta)P_{n-r}(cos\theta) \] が成立することが示されました。