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

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.

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.

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全単射ぜんたんしゃ.

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.

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全射ぜんしゃ.

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.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濃度のうど.

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

8Exercise links