ほぼ数学科の大学生の備忘録。

都内理系大学生が数学/物理等の解説をあげていくブログです。

ベルンシュタインの定理(2)

今回は、ベルンシュタインの定理を証明します。

まず、 |A| \leq |B| かつ |B| \leq |A| であるとします。濃度の大小関係の定義からAからBへの単射 fBからAへの単射 g が存在します。ここで、写像 h:A \to A としてh=g \circ f を考えます。

この元で、Aの部分集合の列 \{A_n\}_{n\in \mathbb{N}} を、以下のように考えます。

A_0=A,A_1=g(B),A_{n+2}=g\circ f(A_n)\ (n=0,1,2\cdots)

こうすると、この列は減少列、つまり A_0 \supset A_1 \supset A_2 \cdots となります。

また、 f,g単射なのでその合成 h=g \circ f単射です。そのため、 g \circ f を各 A_n から A_{n+2} への写像としてみると全単射とみなせます。つまり、

\[ |A_1|=|A_3|=|A_5|=\cdots ,\ |A_0|=|A_2|=|A_4|=\cdots\]

であることがわかります。同様にして gB から A_1 への全単射とみなせるので、 |B|=|A_1| です。

以上より、 |A|=|A_1| を示せば、 |A|=|B| であることが示せます。

これは具体的に全単射を構成することで示します。

まず、\( K=\cup_{i=1}^{\infty}A_i \)とします。このもとで、\( \Phi:A\to A_1\)を

\[ \Phi(x)=\begin{cases}
h(x)\ &(x\in A_{2n+1} \setminus A_{2n})\\
x &(x\ \in \left( A_{2n+2}\setminus A_{2n} \right)\cup K)
\end{cases} \]

とすればこれは全単射となり、ベルンシュタインの定理が証明できたことになります。

最後の写像は、イメージとしては二つずつ内側に押し込めていくイメージです。実際に図を書いてみて確認してみてください。

ベルンシュタインの定理(1)

前回が集合論の加算無限非加算無限の話でしたが、今回は集合の濃度に関する定理、ベルンシュタインの定理の紹介とその説明をします。

集合の濃度とは、直感的には集合の要素の個数、もしくは大きさです。但し濃度は有限集合に限らず無限集合に対しても定義されます。

具体的には、k個の要素から成る有限集合AにたいしてはAの濃度 |A|=k とし、無限集合B,Cに対して、BからCへの全単射がある時に |B|=|C| とします。全単射があるということは、その各要素に対して一対一の対応が取れるということなので、全単射があるときの集合の「大きさ」が等しいという定義は合理的に思えます。

また、集合A,Bに対してAからBへの単射が存在するときに、 |A|\leq|B| と定義します。AからBへの単射があるということは、Aの要素に対して対応する要素がBの中にあるということを表しており、BのAの要素に対応しない要素も存在する可能性があることから、Bの要素の数の方がAの要素の数よりも多くなるというのが直感的な説明です。

この元で、ベルンシュタインの定理とは、
|A|\leq|B|かつ|B|\leq|A| ならば |A|=|B| である

というものです。有限集合について考えれば当然の定理ですが、無限集合に対してもこれが適用できます。

少し長くなってきたので証明はまた次回とします。

非加算無限集合

前回、加算非加算無限 - ほぼ数学科の大学生の備忘録。この記事の最後で実数全体の集合\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}は非加算無限集合であることが示せました。

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

加算非加算無限

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

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


無限集合のうち、自然数全体の集合 \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}の間に全単射が存在しないことを示すには、対角線論法という論法を使うのですが、これの説明は次回に回したいと思います。

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)\] とします。このとき、(1)式は \[ P_n(\cos\theta)=\cfrac{1}{n}Q_n(\cos\theta) \] と書けます。また、(2)式より、 {\displaystyle \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} }
となります(1行目→2行目は余分な項を引いて帳尻を合わせています)。 さらに変形を進めて、
{\displaystyle \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} }
これは、(1)式がn=k+1でも成立することを表しています。 以上より、任意の自然数nに対して、 \[ P_n(\cos\theta)=\cfrac{1}{n}\sum_{r=1}^n\cos(r\theta)P_{n-r}(cos\theta) \] が成立することが示されました。

行列のおはなし。

今回は、正方行列(行と列の大きさが等しい行列)についてのみ考えます。

a,b\in \mathbb{R}に対しては、 ab=0 \Rightarrow a=0\ or\ b =0 が成り立ちます。

しかし、一般の行列A,Bについては、同様の定理は成り立ちません。

代数学の言葉で言えば、このような定理が成り立つものを「整域(integral domain)」といいます。正方行列は整域でない環の例として有名です)

これは、全ての行列に対して逆行列が存在するわけではないことが原因となっています。

まずは、逆行列を定義します。

正方行列Aに対して逆行列A^{-1}とは、
AA^{-1}=A^{-1}A=I
が成り立つような行列のことです。
ただし、Iは単位行列です。

逆行列は全ての行列に存在するわけではなく、逆に逆行列を持つ行列のことを正則行列といいます。

行列が正則になる条件(必要十分条件)はいくつかありますが、特に重要なのは以下の二つです。

Aが正則
\Leftrightarrow det(A) \neq 0
\Leftrightarrow Aの各行ベクトルが線形独立

束の分配不等式の証明

束の分配不等式の証明が少し調べたところ見つかりにくかった(というより日本語では見つけられなかった)ので、書いておこうと思います。

そもそも、束の分配不等式とは何かというと、任意の束の任意の元A,B,Cについて、

A \land (B \lor C) \geq (A \land B ) \lor (A \land C)

A \lor (B \land C) \leq (A \lor B ) \land (A \lor C)

が成り立つ、というものである。これが任意の組み合わせについて等号で成り立つとき、その束を分配束という。

確認だが、

A \leq B \Leftrightarrow A \land B =A または A \lor B=B

である。

また、この定義から

A \land B = \sup\{A,B\} , A \lor B = \inf\{A,B\}

であることが示される。 

では、実際に証明してみる。

第1式のみ証明する。

\leqの定義より、A\geq A\land BA\geq A\land C であるので、

A \geq (A\land B) \lor (A \land C)が成り立つ。

これは、Aが(A\land B)(A\land C)の上界に入っており、右辺は最小の上界であることから示される。

また、(B \lor C) \geq B \geq (A \land B)(B \lor C) \geq B \geq (A \land C)であるので、上と同様にして

(B \lor C) \geq (A\land B)\lor (A \land C)

が成り立つ。

したがって、示したい式の右辺はAとB \land Cの下界であり、左辺はAとB \land Cの最大の下界なので、(左辺)\geq(右辺)が成立する。

 第2式も同様にして示される。