可算集合~整除 - 小西研究室@電脳工房ＭＳＣ

(6).可算集合の話

前回までの話をまとめよう。

【定義】

濃度・・・無限集合の要素の数に相当する概念。
無限集合の相等は、「1対1の対応」が存在する場合とする。

整数 $Z$ の濃度＝自然数 $N$ の濃度

　　　 $0\leftrightarrow1,\ 1\leftrightarrow2,\ -1\leftrightarrow3,\ 2\leftrightarrow4,-2\leftrightarrow5,\dots$ 、と対応付けることで、「1対1の対応」付けができる。

平面上の格子点 $(m,n)$ の集合 $M$ の濃度＝自然数 $N$ の濃度

　　　前回までの議論のように、 $(0,0)\leftrightarrow1,\ (1,0)\leftrightarrow2,\ (1,1)\leftrightarrow3,\dots$ と渦巻き状に対応付けることで、
　　座標から順番が求まり、順番から座標が求めることができる。これは、「1対1の対応」付けができることを示している。

有理数の集合

　　 $Q=\{\frac{m}{n}|m,n$ は整数、 $n>0\}$ 　とする。
　　分母が１の有理数は整数であるので、 $Z$ は $Q$ に含まれることが分かる。（これを、 $Z\subset Q$ と書く。）

　　また、分数 $\frac{m}{n}$ を格子点 $(m,n)$ に対応づけることで、 $Q\subset M$ がわかる。

　以上により、 $N\subset Z\subset Q\subset M$ がわかる。
　ゆえに、有理数の濃度＝整数の濃度＝自然数の濃度、が結論付けられる。
　有理数は、整数や自然数よりも多く感じるけど、実は「同じ」個数であることが分かったのである。

(7).カントールの対角線論法

有理数の数号は可算であることが分かったが、実数は可算ではない。
これを証明するのが、「カントール(Cantor)の対角線論法」である。
少し難しいが、証明の素晴らしさを味わってほしい。

「実数の集合は可算ではない」ことを証明する。
まず、結論を否定して矛盾を見出す「背理法」で証明する。

実数の集合が可算である、と仮定する。特に、０より大きく１より小さい実数の集合 $I$ で考える。
　　　 $I=\{\ x\ |\ 0<x<1,x$ は実数 $\}$
仮定より、すべての実数に番号を付けて、下記のように、一列に並べることができる。
　　1番目　・・・　 $0.a_{11}a_{12}a_{13}\dots$
　　2番目　・・・　 $0.a_{21}a_{22}a_{23}\dots$
　　3番目　・・・　 $0.a_{31}a_{32}a_{33}\dots$
　　　　 $\vdots$
　　n番目　・・・　 $0.a_{n1}a_{n2}a_{n3}\dots$
　　　　 $\vdots$
　　　　　　　（ $a_{ij}$ は、 $i$ 番目の数の $j$ 桁目、である）
このとき、
　　 $a_{ii}=1$ のとき $x_{i}=0$ 、　 $a_{ii}\ne 1$ のとき $x_{i}=1$
として、数 $0.x_{1}x_{2}x_{3}\dots$ を定める。
　すると、この数 $0.x_{1}x_{2}x_{3}\dots$ は、上で並べたどの数とも一致しない。
これは、すべての実数に番号を付けて並べたことに矛盾する。
ゆえに、すべての実数に番号を付けることは出来ない　　　　（証明終わり）

上の議論で、有理数と実数は濃度が異なることが分かった。
無限集合に、濃度の違う集合がある。「濃い無限」と「薄い無限」がある。
この他にも濃さの違う無限があるのか、これは20世紀の数学者が追及している問題であり、今後も追及され続ける問題なのである。

第2章.ユークリッドの互除法

(1).整除について

【定義】　整数 $a,b$ に対して、
　　　　 $a\div b=q\dots r$
となるとき、 $a$ を $b$ で割った結果 $q$ を「商」といい、余り $r$ を「剰余」という。このとき、
　　　　 $a=bq+r$
の関係が成り立つ。

【定理】剰余 $r$ については、 $0\le r<q$ を満たすように取ることができる。

（問題）次のそれぞれの場合に定理の式を成り立たせる $q,r$ を求めよ。
　　 $(1).\ a=720,\ b=39$ 　　　　 $(2).\ a=-50,\ b=12$
　　 $(3).\ a=5,\ b=13$ 　　　　　 $(4).\ a=-5,\ b=13$

（解答）
$(1).\ 720\div 39=18\dots 18$ より、 $q=18,r=18$
$(2).\ (-50)\div 12=(-4)\dots (-2)$
　　　　　　　　 $=(-5)\dots 10$ より、 $q=-5,r=10$
$(3).\ 5\div 13=0\dots 5$ より、 $q=0,r=5$
$(4).\ (-5)\div 13=0\dots (-5)$
　　　　　　　　 $=(-1)\dots 8$ より、 $q=-1,r=8$

「可算集合~整除」をウィキ内検索

最終更新：2011年11月16日 13:39