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

Cardinality濃度のうど and countability可算性かさんせい of sets集合しゅうごう

1導入どうにゅう

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

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

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

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

1Introduction

For a finite set集合しゅうごう, we compare size大きさ by counting elements元げん. For an infinite set無限集合むげんしゅうごう, counting to the end is impossible. The key idea is: if a one-to-one correspondence can be built, the sets have the same size.

In this viewpoint, cardinality濃度のうど is compared using a bijection全単射ぜんたんしゃ. A bijection is a correspondence対応たいおう with no leftovers and no overlaps, so it abstracts the act of matching elements one by one.

When comparing cardinality濃度のうど, use bijections rather than visual size. For infinite sets, the boundary is whether the set can be listed and whether a diagonal argument対角線論法たいかくせんろんぽう can defeat any proposed listing.

Order note: the formal lectures on maps写像しゃぞう, injections単射たんしゃ, surjections全射ぜんしゃ, and bijections全単射ぜんたんしゃ appear later. On this page, use the minimum needed meanings: a map assigns one output to each input, an injection has no overlaps, a surjection has no leftovers, and a bijection has neither overlaps nor leftovers.

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を持もつことである。

2Terms and definitions

Two sets集合しゅうごう $$A,B$$A,B have the same cardinality濃度のうど when there exists a bijection全単射ぜんたんしゃ $$A\to B$$A\to B.

For $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}0$$n\ge0, write $$\left[n\right]=\{1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},n\}$$[n]=\{1,2,\dots,n\}, with the convention $$\left[0\right]=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[0]=\varnothing. A set $$A$$A is a finite set有限集合ゆうげんしゅうごう if, for some nonnegative integer $$n$$n, there is a bijection between $$A$$A and $$\left[n\right]$$[n].

In this lecture, $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\}. A set $$A$$A is a countable set可算集合かさんしゅうごう if it is finite or has the same cardinality濃度のうど as $$\mathbb{N}$$\mathbb N.

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を構成こうせいする。

3Method

To compare cardinalities濃度のうど, construct a map写像しゃぞう rather than trying to count directly. The statement $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|A|\le |B| means that an injection単射たんしゃ from $$A$$A to $$B$$B exists. Thus, to show $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B|, look for an injection from $$B$$B to $$A$$A. To show $$\left|A\right|=\left|B\right|$$|A|=|B|, construct a 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は、どんな一覧いちらんを仮定かていしても、そこに載のらない対象たいしょうを作つくる。

4Intuitive explanation

The set of even natural numbers $$2\mathbb{N}$$2\mathbb N is a part of $$\mathbb{N}$$\mathbb N. However, $$n\mapsto 2n$$n\mapsto 2n is a bijection全単射ぜんたんしゃ from $$\mathbb{N}$$\mathbb N to $$2\mathbb{N}$$2\mathbb N. Therefore, in the sense of cardinality濃度のうど, $$\mathbb{N}$$\mathbb N and $$2\mathbb{N}$$2\mathbb N have the same size.

This is where intuition for infinite sets無限集合むげんしゅうごう differs from intuition for finite sets. For finite sets, a proper subset真部分集合しんぶぶんしゅうごう has fewer elements. For infinite sets, a proper subset can correspond bijectively to the whole set.

To say that a set is countable可算かさん means that its elements can be labeled without duplication or omission by a finite initial segment of the natural numbers, or by all of $$\mathbb{N}$$\mathbb N. A diagonal argument対角線論法たいかくせんろんぽう instead starts from any proposed infinite list and constructs an object missing from it.

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 番目ばんめの位置いちで必かならず違ちがう新あたらしい対象たいしょうを作つくる。この構成こうせいにより、その列挙れっきょが全射ぜんしゃでないことを示しめす。

5Precise idea: entrance to the diagonal argument対角線論法たいかくせんろんぽう

A countable set可算集合かさんしゅうごう is a set集合しゅうごう whose elements can be labeled without duplication or omission by finitely many indices or by $$\mathbb{N}$$\mathbb N. In contrast, the set of real numbers実数じっすう $$x$$x satisfying $$0<x<1$$0<x<1 is not countable.

Suppose this set were countable可算かさん. We could then form a sequence $$r_1,r_2,r_3,\text{[PARSE ERROR: Undefined("Command("dots")")]}$$r_1,r_2,r_3,\dots containing every one of its elements. In the countably infinite case, list them in the order given by a bijection全単射ぜんたんしゃ with $$\mathbb{N}$$\mathbb N. In the finite case, list every element once and then repeat the element $$1/2$$1/2.

Now apply Cantor's diagonal argument対角線論法たいかくせんろんぽう. For each $$r_i$$r_i, choose the decimal expansion $$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 that does not end in an infinite string of 9s. Define $$s=0.s_1{s}_2{s}_3\text{[PARSE ERROR: Undefined("Command("dots")")]}$$s=0.s_1s_2s_3\dots by taking $$s_i=1$$s_i=1 when $$d_{ii}\ne 1$$d_{ii}\ne1 and $$s_i=2$$s_i=2 when $$d_{ii}=1$$d_{ii}=1. Then $$0<s<1$$0<s<1, and $$s$$s differs from $$r_i$$r_i in the $$i$$i-th digit. Because every digit of $$s$$s is either 1 or 2, no alternative expansion ending in 9s can identify it with an entry in the list. Thus $$s$$s is missing from the sequence, contradicting the assumption that the sequence contains every element.

In a diagonal argument対角線論法たいかくせんろんぽう, assume an arbitrary listing and construct a new object that differs from the $$n$$n-th listed object at the $$n$$n-th position. This construction shows that the listing is not a surjection全射ぜんしゃ.

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を持もつことを示しめせ。

6Worked example: the positive even numbers are countable可算かさん

6.1Problem

Show that the set of positive even numbers $$E=\{2,4,6,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$E=\{2,4,6,\dots\} has the same cardinality濃度のうど as $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\}.

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を持もつ。

6.2Explanation

Define $$f:\mathbb{N}\to E$$f:\mathbb N\to E by $$f\left(n\right)=2n$$f(n)=2n. If $$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2), then $$2n_1=2n_2$$2n_1=2n_2. Dividing by the nonzero constant $$2$$2 gives $$n_1=n_2$$n_1=n_2, so $$f$$f is an injection単射たんしゃ.

Take arbitrary $$e\in E$$e\in E. By the definition of $$E$$E, there exists $$n\in \mathbb{N}$$n\in\mathbb N such that $$e=2n$$e=2n. Therefore $$f\left(n\right)=e$$f(n)=e, so $$f$$f is a surjection全射ぜんしゃ. Hence $$f$$f is a bijection全単射ぜんたんしゃ, and $$E$$E and $$\mathbb{N}$$\mathbb N have the same cardinality濃度のうど.

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

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

7How to identify it and related links

• To compare sizes, look for a bijection全単射ぜんたんしゃ.
• To prove countability, construct a listing from the natural numbers自然数しぜんすう.
• To prove uncountability, construct an element元げん missing from an arbitrary list.
• Intuition valid for finite sets may fail for infinite sets無限集合むげんしゅうごう.

8演習えんしゅうリンク

8Exercise links