集合しゅうごうsetの濃度のうどcardinalityと可算性かさんせいcountability

1導入どうにゅう

集合しゅうごうsetの大おおきさsizeを比くらべるとき、有限集合ゆうげんしゅうごうなら元げんelementの個数こすうを数かぞえればよい。しかし無限集合むげんしゅうごうでは、数かぞえ終おえることができない。そこで重要じゅうようになる発想はっそうは、「一対一対応いちたいいちたいおうを作つくれるなら同おなじ大おおきさと見みなす」である。

この見方みかたでは、濃度のうどcardinalityは全単射ぜんたんしゃbijectionによって比較ひかくされる。全単射ぜんたんしゃbijectionは余あまりも重かさなりもない対応たいおうcorrespondenceなので、元げんelementを 1 つずつ対応たいおうさせる数かぞえ方かたの抽象化ちゅうしょうかである。

濃度のうどcardinalityを比くらべるときは、見みた目めの大おおきさではなく全単射ぜんたんしゃbijectionを使つかう。無限集合むげんしゅうごうでは、数かぞえ上あげられるかどうかと、対角線論法たいかくせんろんぽうで列挙れっきょを破やぶれるかどうかが境界きょうかいになる。

順序上じゅんじょじょうの注意ちゅういとして、写像しゃぞうmap、単射たんしゃinjection、全射ぜんしゃsurjection、全単射ぜんたんしゃbijectionの正式せいしきな講義こうぎは後あとにある。このページでは、写像しゃぞうを「各かく入力にゅうりょくに出力しゅつりょくを 1 つ割わり当あてる規則きそく」、単射たんしゃを「重かさなりがない」、全射ぜんしゃを「余あまりがない」、全単射ぜんたんしゃを「重かさなりも余あまりもない」として最小限さいしょうげんに使つかう。

2用語ようごと定義ていぎ

集合しゅうごうset $$A,B$$A,B の間あいだに全単射ぜんたんしゃbijection $$A\to B$$A\to B が存在そんざいするとき、$$A$$A と $$B$$B は同おなじ濃度のうどcardinalityを持もつという。

$$n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$$n\ge0 に対たいし、$$\left[n\right]=\{1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},n\}$$[n]=\{1,2,\dots,n\} と書かく。ただし $$\left[0\right]=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[0]=\varnothing と定さだめる。集合しゅうごうset $$A$$A が有限集合ゆうげんしゅうごうfinite setであるとは、ある 0 以上いじょうの整数せいすう $$n$$n について $$A$$A と $$\left[n\right]$$[n] の間あいだに全単射ぜんたんしゃbijectionが存在そんざいすることである。

この講義こうぎでは $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\} とする。集合しゅうごうset $$A$$A が可算集合かさんしゅうごうcountable setであるとは、$$A$$A が有限集合ゆうげんしゅうごうfinite setであるか、自然数しぜんすうnatural number全体ぜんたい $$\mathbb{N}$$\mathbb N と同おなじ濃度のうどcardinalityを持もつことである。

3方針ほうしん

濃度のうどcardinalityを比較ひかくするときは、実際じっさいに数かぞえるのではなく、写像しゃぞうmapを構成こうせいする。$$\left|A\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|A|\le |B| は、$$A$$A から $$B$$B への単射たんしゃinjectionが存在そんざいするという意味いみである。したがって $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B| を示しめすには、$$B$$B から $$A$$A への単射たんしゃinjectionを探さがす。$$\left|A\right|=\left|B\right|$$|A|=|B| を示しめすには、全単射ぜんたんしゃbijectionを構成こうせいする。

4直感的ちょっかんてきな説明せつめい

偶数ぐうすう全体ぜんたい $$2\mathbb{N}$$2\mathbb N は、自然数しぜんすう全体ぜんたい $$\mathbb{N}$$\mathbb N の一部いちぶである。しかし $$n\mapsto 2n$$n\mapsto 2n は $$\mathbb{N}$$\mathbb N から $$2\mathbb{N}$$2\mathbb N への全単射ぜんたんしゃbijectionである。したがって、濃度のうどcardinalityの意味いみでは $$\mathbb{N}$$\mathbb N と $$2\mathbb{N}$$2\mathbb N は同おなじ大おおきさである。

これは無限集合むげんしゅうごうの直感ちょっかんが有限集合ゆうげんしゅうごうと異ことなる点てんである。有限集合ゆうげんしゅうごうでは、真しんの部分集合ぶぶんしゅうごうproper subsetは元げんの個数こすうが少すくない。しかし無限集合むげんしゅうごうでは、真しんの部分集合ぶぶんしゅうごうproper subsetと全体ぜんたいが全単射ぜんたんしゃbijectionで対応たいおうすることがある。

可算かさんcountableとは、有限個ゆうげんこの番号ばんごう、または $$\mathbb{N}$$\mathbb N で重複ちょうふくなく漏もれなく番号ばんごうを付つけられるということである。一方いっぽう、対角線論法たいかくせんろんぽうdiagonal argumentは、どんな一覧いちらんを仮定かていしても、そこに載のらない対象たいしょうを作つくる。

5厳密げんみつな説明せつめい：対角線論法たいかくせんろんぽうdiagonal argumentの入口いりぐち

可算集合かさんしゅうごうcountable setは、有限個ゆうげんこの番号ばんごうまたは $$\mathbb{N}$$\mathbb N で重複ちょうふくなく漏もれなく番号ばんごうを付つけられる集合しゅうごうsetである。一方いっぽう、$$0<x<1$$0<x<1 を満みたす実数じっすうreal number $$x$$x の集合しゅうごうは可算集合かさんしゅうごうcountable setではない。

この集合しゅうごうが可算集合かさんしゅうごうcountable setだと仮定かていすると、その全要素ぜんようそを含ふくむ列れつ $$r_1,r_2,r_3,\text{[PARSE ERROR: Undefined("Command("dots")")]}$$r_1,r_2,r_3,\dots を作つくれる。可算無限かさんむげんなら $$\mathbb{N}$$\mathbb N との全単射ぜんたんしゃbijectionの順じゅんに並ならべればよい。有限ゆうげんなら全要素ぜんようそを一度いちど並ならべた後あと、この集合しゅうごうの元げん $$1/2$$1/2 を繰くり返かえせばよい。

ここで対角線論法たいかくせんろんぽうdiagonal argumentを用もちいる。各かく $$r_i$$r_i について、末尾まつびが 9 だけで続つづく表示ひょうじを使つかわない小数表示しょうすうひょうじ $$r_i=0.d_{i1}{d}_{i2}{d}_{i3}\text{[PARSE ERROR: Undefined("Command("dots")")]}$$r_i=0.d_{i1}d_{i2}d_{i3}\dots を選えらぶ。$$s=0.s_1{s}_2{s}_3\text{[PARSE ERROR: Undefined("Command("dots")")]}$$s=0.s_1s_2s_3\dots の $$i$$i 桁目けためを、$$d_{ii}\ne 1$$d_{ii}\ne1 なら $$s_i=1$$s_i=1、$$d_{ii}=1$$d_{ii}=1 なら $$s_i=2$$s_i=2 と定さだめる。すると $$s$$s は 0 と 1 の間あいだにあり、$$r_i$$r_i とは $$i$$i 桁目けためで異ことなる。また $$s$$s の各桁かくけたは 1 または 2 なので、別べつの「9 が続つづく表示ひょうじ」と同おなじ実数じっすうになる問題もんだいも起おこらない。したがって $$s$$s は列れつに含ふくまれず、この列れつが全要素ぜんようそを含ふくむという仮定かていに矛盾むじゅんする。

対角線論法たいかくせんろんぽうdiagonal argumentでは、任意にんいの列挙れっきょを仮定かていし、$$n$$n 番目ばんめの対象たいしょうと $$n$$n 番目ばんめの位置いちで必かならず違ちがう新あたらしい対象たいしょうを作つくる。この構成こうせいにより、その列挙れっきょが全射ぜんしゃでないことを示しめす。

6例題れいだい：偶数ぐうすう全体ぜんたいは可算集合かさんしゅうごうcountable setである

6.1問題もんだい

正せいの偶数ぐうすう全体ぜんたい $$E=\{2,4,6,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$E=\{2,4,6,\dots\} が $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\} と同おなじ濃度のうどcardinalityを持もつことを示しめせ。

6.2解説かいせつ

$$f:\mathbb{N}\to E$$f:\mathbb N\to E を $$f\left(n\right)=2n$$f(n)=2n で定義ていぎする。任意にんいの $$n_1,n_2\in \mathbb{N}$$n_1,n_2\in\mathbb N について $$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2) なら $$2n_1=2n_2$$2n_1=2n_2 である。両辺りょうへんを非零定数ひれいていすう $$2$$2 で割わって $$n_1=n_2$$n_1=n_2 を得える。したがって $$f$$f は単射たんしゃinjectionである。

任意にんいの $$e\in E$$e\in E を取とる。$$E$$E の定義ていぎより、ある $$n\in \mathbb{N}$$n\in\mathbb N が存在そんざいして $$e=2n$$e=2n である。したがって $$f\left(n\right)=e$$f(n)=e であり、$$f$$f は全射ぜんしゃsurjectionである。よって $$f$$f は全単射ぜんたんしゃbijectionであり、$$E$$E と $$\mathbb{N}$$\mathbb N は同おなじ濃度のうどcardinalityを持もつ。

7見分みわけ方かたと関連かんれんリンク

• 大おおきさを比較ひかくするなら、全単射ぜんたんしゃbijectionを探さがす。
• 数かぞえ上あげられることを示しめすなら、自然数しぜんすうnatural numberからの列挙れっきょを作つくる。
• 数かぞえ上あげられないことを示しめすなら、任意にんいの列挙れっきょから漏もれる元げんelementを構成こうせいする。
• 有限集合ゆうげんしゅうごうで成立せいりつする直感ちょっかんが、無限集合むげんしゅうごうでも成立せいりつするとは限かぎらない。

8演習えんしゅうリンク