集合しゅうごう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を持もつという。

集合しゅうごうset $$A$$A が有限集合ゆうげんしゅうごうfinite setであるとは、ある自然数しぜんすうnatural number $$n$$n について $$A$$A と $$\{1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},n\}$$\{1,2,\dots,n\} の間あいだに全単射ぜんたんしゃbijectionが存在そんざいすることである。$$n=0$$n=0 の場合ばあいは、$$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing に対応たいおうする。

集合しゅうごう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.

A set $$A$$A is a finite set有限集合ゆうげんしゅうごう if, for some natural number自然数しぜんすう $$n$$n, there is a bijection between $$A$$A and $$\{1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},n\}$$\{1,2,\dots,n\}. The case $$n=0$$n=0 corresponds to $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing.

A set $$A$$A is a countable set可算集合かさんしゅうごう if it is finite or has the same cardinality濃度のうど as the set of natural numbers自然数しぜんすう $$\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| と言いいたいなら、$$A$$A から $$B$$B への全射ぜんしゃsurjectionを探さがす。$$\left|A\right|=\left|B\right|$$|A|=|B| と言いいたいなら、全単射ぜんたんしゃbijectionを構成こうせいする。

3Method

To compare cardinalities濃度のうど, construct a map写像しゃぞう rather than trying to count directly. To show $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|A|\le |B|, look for an injection単射たんしゃ from $$A$$A to $$B$$B. To show $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B|, look for a surjection全射ぜんしゃ from $$A$$A to $$B$$B. 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とは、自然数しぜんすうで重複ちょうふくなく漏もれなく番号ばんごうを付つけられるということである。一方いっぽう、対角線論法たいかくせんろんぽう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.

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

可算集合かさんしゅうごうcountable setは列挙れっきょできる集合しゅうごうsetである。一方いっぽう、実数じっすうreal numberの区間くかん $$(0,1)$$(0,1) は可算集合かさんしゅうごうcountable setではない。

この事実じじつの基本きほんは対角線論法たいかくせんろんぽうdiagonal argumentである。もし $$(0,1)$$(0,1) の実数じっすうreal numberを $$r_1,r_2,r_3,\text{[PARSE ERROR: Undefined("Command("dots")")]}$$r_1,r_2,r_3,\dots と列挙れっきょできたと仮定かていする。各かく $$r_i$$r_i の小数表示しょうすうひょうじを並ならべ、$$i$$i 番目ばんめの $$r_i$$r_i の $$i$$i 桁目けためと異ことなる数字すうじを選えらんで新あたらしい実数じっすうreal number $$s$$s を作つくる。すると $$s$$s は任意にんいの $$r_i$$r_i と $$i$$i 桁目けためで異ことなるため、列挙れっきょの中なかに存在そんざいしない。

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

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

A countable set可算集合かさんしゅうごう is a set集合しゅうごう that can be listed. In contrast, the interval $$(0,1)$$(0,1) of real numbers実数じっすう is not countable.

The basic idea is Cantor's diagonal argument対角線論法たいかくせんろんぽう. Suppose the real numbers in $$(0,1)$$(0,1) could be listed as $$r_1,r_2,r_3,\text{[PARSE ERROR: Undefined("Command("dots")")]}$$r_1,r_2,r_3,\dots. Write their decimal expansions in a table, and choose a new real number $$s$$s whose $$i$$i-th digit differs from the $$i$$i-th digit of $$r_i$$r_i. Then $$s$$s differs from every $$r_i$$r_i at the $$i$$i-th digit, so it is not in the list.

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無限集合むげんしゅうごう.