集合論
数学>集合論
集合とはなにか？

集合(set)とは、物の集まりであって、何か物を持ってきたときにそこに属すのか属さないのかどちらかに必ず定まるもののことである。例えば、「標高8500m以上の山」「都道府県であって、人口500万人未満のもの」「すべての二等辺三角形」「正の奇数すべて」などは集合である。ただし、「頭がいい人」のような、何が属して何が属さないのかが曖昧なものは集合とは呼ばないことにする。
集合とはなにか？

集合に属している物のことを元 (element)と呼ぶ。先ほどの例から、「標高8500m以上の山」という集合では、「エベレスト、K2、カンチェンジュンガ、ローツェの4つの元がある」などと言う。「正の奇数すべて」の集合は、「1,3,5,...という無限個の元から成っている」と言える。元が集合に属していることを「 ∈ {\displaystyle \in } 」という記号で表す。例えば、自然数の全体という集合を N {\displaystyle \mathbb {N} } とすると、 1 ∈ N {\displaystyle 1\in \mathbb {N} } と書ける。
集合とはなにか？

なお、元が1つもない集合も集合とみなすことにする。そのような集合を空集合 (empty set、null set)と呼び、 ∅ {\displaystyle \varnothing } で表す。
記法と演算

集合をあらわすには、その集合に属している元をすべて書き表すのが最も簡単だ。例えば「1桁の素数」という集合なら
記法と演算

{ 2 , 3 , 5 , 7 } {\displaystyle \{2,3,5,7\}}
記法と演算

と書ける。このような書き方を外延的記法という。
記法と演算

しかし、集合の元の数が多くなってくると外延的記法は難しくなってくる。例えば、人口500万人未満の都道府県は38個もあるので全部列挙していたら大変だ。それどころか、正の奇数すべての集合の元は無限個あるので、全部書き表すことは不可能で、{1,3,5,7,...}と書くしかない。しかし、このような書き方は、どのような集合なのか誤解を招きやすい。ある人は、「奇数の素数と1」という集合{1,3,5,7,11,13,17,...}の意味でこのように書くかもしれない。
記法と演算

そこで、ある集合の元が満たすべき性質を書くことで集合をあらわすことを考える。そのような記法を内包的記法という。内包的記法では、集合の元を代表する文字と満たすべき条件を縦棒を挟んで並べて書く。例えば、正の奇数の集合は
記法と演算

{ x ∣ x = 2 n − 1 , n ∈ N } {\displaystyle \{x\mid x=2n-1,n\in \mathbb {N} \}}
記法と演算

と書ける。
記法と演算

集合Sのすべての元が集合Tに属しているとき、SはTの部分集合 (subset)であるといい、 S ⊂ T {\displaystyle S\subset T} と表す。空集合は任意の集合の部分集合である。また、S自身もSの部分集合である。S自身以外の部分集合をSの真部分集合といい、TがSの真部分集合であることを T ⊊ S {\displaystyle T\subsetneq S} とあらわす。
記法と演算

元が集合に属しているという関係と、元がひとつだけの集合が別の集合の部分集合であるという関係とは似て非なるものである。すなわち、 x ∈ X {\displaystyle x\in X} と { x } ⊂ X {\displaystyle \{x\}\subset X} とは、同値ではあるが表していることは異なる。この違いにはよく注意すべきである。
記法と演算

X ⊂ Y {\displaystyle X\subset Y} かつ Y ⊂ X {\displaystyle Y\subset X} を満たすとき X = Y {\displaystyle X=Y} と書き、この2つの集合は等しいという。何をくだらないことを定義するのか、と思ってはいけない。数学ではしばしばまったく別の方法で定義した2つの集合X,Yが実は同じ集合であることを証明すべきときがある。そのようなときには、 X ⊂ Y {\displaystyle X\subset Y} かつ Y ⊂ X {\displaystyle Y\subset X} を示せばよいのである。
記法と演算

集合があるとき、その集合の部分集合の集合というものを考えることができる。これをその集合の冪(べき)集合という。きちんと集合の記法で書けば、
記法と演算

のことを、Xの冪集合という。
記法と演算

P ( { 1 , 2 , 3 } ) = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } {\displaystyle {\mathcal {P}}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}}
記法と演算

この例を見てもわかるように、有限個の元から成る集合(厳密な定義は後の節を参照)Xの冪集合 P ( X ) {\displaystyle {\mathcal {P}}(X)} の元の個数は、Xの元の個数の2の冪である(この例でいえば、2=8個)ので、 P ( X ) {\displaystyle {\mathcal {P}}(X)} のことを 2 X {\displaystyle 2^{X}} と書くこともある。また P ( X ) {\displaystyle {\mathfrak {P}}(X)} とも書かれる。
記法と演算

集合 S {\displaystyle S} と集合 T {\displaystyle T} の元をあわせた集合 { x | x ∈ S ∨ x ∈ T } {\displaystyle \{x|x\in S\lor x\in T\}} を和集合(sum)ないしは合併(union)といい、 S ∪ T {\displaystyle S\cup T} と表す。例えば、 { 1 , 2 , 3 } ∪ { 3 , 4 , 5 } = { 1 , 2 , 3 , 4 , 5 } {\displaystyle \{1,2,3\}\cup \{3,4,5\}=\{1,2,3,4,5\}} である。
記法と演算

集合 S {\displaystyle S} から集合 T {\displaystyle T} の元を除いた集合 { x | x ∈ S ∧ x ∉ T } {\displaystyle \{x|x\in S\land x\notin T\}} を差集合(difference set)といい、 S − T {\displaystyle S-T} または S ∖ T {\displaystyle S\setminus T} と表す。例えば、 { 1 , 2 , 3 } ∖ { 3 , 4 , 5 } = { 1 , 2 } {\displaystyle \{1,2,3\}\setminus \{3,4,5\}=\{1,2\}} である。
記法と演算

集合 S {\displaystyle S} と集合 T {\displaystyle T} の共通する元の集合 { x | x ∈ S ∧ x ∈ T } {\displaystyle \{x|x\in S\land x\in T\}} を積集合(intersection)ないしは共通部分(meet)といい、 S ∩ T {\displaystyle S\cap T} と表す。例えば、 { 1 , 2 , 3 } ∩ { 3 , 4 , 5 } = { 3 } {\displaystyle \{1,2,3\}\cap \{3,4,5\}=\{3\}} である。
記法と演算

これらに関しては、次の性質(ド・モルガンの法則)が成り立つ。SとTをXの部分集合とすると、
記法と演算

また、次の性質(吸収法則)もよく知られている。
記法と演算

集合 S {\displaystyle S} と集合 T {\displaystyle T} の元の組の集合 { ( x , y ) | x ∈ S ∧ y ∈ T } {\displaystyle \{(x,y)|x\in S\land y\in T\}} を直積(direct product)といい、 S × T {\displaystyle S\times T} と表す。例えば、 { 1 , 2 } × { 3 , 4 } = { ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) } {\displaystyle \{1,2\}\times \{3,4\}=\{(1,3),(1,4),(2,3),(2,4)\}} である。
写像

我々は、関数という概念を既に知っている。fが関数(function)であるとは、xという数に対して別の数f(x)がただひとつ定まることであった。ここでは、関数の概念を一般化した写像という概念を考える。すなわち、集合XとYについて、任意の x ∈ X {\displaystyle x\in X} に対して f ( x ) ∈ Y {\displaystyle f(x)\in Y} がただひとつ定まるとき、この対応fはXからYへの写像 (mapping)であるといい、
写像

と書くことにする。2つの写像 f 1 , f 2 : X → Y {\displaystyle f_{1},f_{2}:X\to Y} について、
写像

と定める。
写像

2つの写像 f : X → Y {\displaystyle f:X\to Y} と g : Y → Z {\displaystyle g:Y\to Z} があるとき、写像 h : X → Z , x ↦ g ( f ( x ) ) {\displaystyle h:X\to Z,x\mapsto g(f(x))} が定まる。これをfとgの合成 (composite)といい、 g ∘ f {\displaystyle g\circ f} と書く。
写像

写像 f : X → Y {\displaystyle f:X\to Y} とXの部分集合Sがあるとき、Yの部分集合 { f ( x ) | x ∈ S } {\displaystyle \{f(x)|x\in S\}} をfによるSの像 (image)といい、 f ( S ) {\displaystyle f(S)} と書く。
写像

写像 f : X → Y {\displaystyle f:X\to Y} とYの部分集合Tがあるとき、Xの部分集合 { x | f ( x ) ∈ T } {\displaystyle \{x|f(x)\in T\}} をfによるTの逆像 (inverse image)といい、 f − 1 ( T ) {\displaystyle f^{-1}(T)} と書く。
写像

特に T = { y } {\displaystyle T=\{y\}} のときには f − 1 ( { y } ) {\displaystyle f^{-1}(\{y\})} を単に f − 1 ( y ) {\displaystyle f^{-1}(y)} と書くこともしばしばある。しかし、この記号は少し紛らわしいので注意すべきである。 f ( S ) {\displaystyle f(S)} と f − 1 ( T ) {\displaystyle f^{-1}(T)} はどちらも集合であるのに対して、 f ( x ) {\displaystyle f(x)} は集合の元だが f − 1 ( y ) {\displaystyle f^{-1}(y)} は集合である。
写像

写像 f : X → Y {\displaystyle f:X\to Y} が f ( x ) = f ( x ′ ) ⇒ x = x ′ {\displaystyle f(x)=f(x')\Rightarrow x=x'} (対偶を取れば、 x ≠ x ′ ⇒ f ( x ) ≠ f ( x ′ ) {\displaystyle x\neq x'\Rightarrow f(x)\neq f(x')} )を満たすとき、fは単射 (injection)であるという。また、 f ( X ) = Y {\displaystyle f(X)=Y} を満たすとき、fは全射 (surjection)であるという。全射かつ単射であることを全単射 (bijection)であるという。
写像

例 集合Xと部分集合Sが与えられているとする。このとき、 i : S → X {\displaystyle i:S\to X} をi(x)=xで定めると、これは単射である。このiを包含写像という。特にS=Xのとき、iは全単射である。このとき恒等写像 (identity mapping)と呼び、特に i d X {\displaystyle id_{X}} と書く。
写像

特に空集合は任意の集合の部分集合なので、空集合からは任意の集合へ包含写像を考えることができる(実質的には何も定めていない写像だが、集合論的に考えることはできる、ということである)。これを特に空写像という。
写像

写像 f : X → Y {\displaystyle f:X\to Y} と g : Y → X {\displaystyle g:Y\to X} があって、 g ∘ f = i d X {\displaystyle g\circ f=id_{X}} かつ f ∘ g = i d Y {\displaystyle f\circ g=id_{Y}} を満たすとき、gはfの逆写像 (inverse mapping)であるといい、 f − 1 {\displaystyle f^{-1}} と書く。
写像

命題 写像 f : X → Y {\displaystyle f:X\to Y} に逆写像が存在することと、写像fが全単射であることは同値である。
写像

この命題があるため、写像が全単射であることを証明するために、全射かつ単射であることを示すより、具体的に逆写像を構成してしまったほうが簡単な場合がしばしばある。
写像

より細かくみると、次が成り立つ。
写像

命題 Xが空集合でないとき、写像 f : X → Y {\displaystyle f:X\to Y} が単射であることは、 r ∘ f = i d X {\displaystyle r\circ f=id_{X}} を満たす写像 r : Y → X {\displaystyle r:Y\to X} (fの左逆写像、またはレトラクトという)が存在することと同値である。また、写像 f : X → Y {\displaystyle f:X\to Y} が全射であることは、 f ∘ s = i d Y {\displaystyle f\circ s=id_{Y}} を満たす写像 s : Y → X {\displaystyle s:Y\to X} (fの右逆写像、またはセクションという)が存在することと同値である。
写像

単射・全射については以下の命題も成り立つ。
写像

命題 写像 g : Y → Z {\displaystyle g:Y\to Z} が単射で、 f 1 , f 2 : X → Y {\displaystyle f_{1},f_{2}:X\to Y} が g ∘ f 1 = g ∘ f 2 {\displaystyle g\circ f_{1}=g\circ f_{2}} を満たすとき、 f 1 = f 2 {\displaystyle f_{1}=f_{2}}
写像

命題 写像 f : X → Y {\displaystyle f:X\to Y} が全射で、 g 1 , g 2 : Y → Z {\displaystyle g_{1},g_{2}:Y\to Z} が g 1 ∘ f = g 2 ∘ f {\displaystyle g_{1}\circ f=g_{2}\circ f} を満たすとき、 g 1 = g 2 {\displaystyle g_{1}=g_{2}}
写像

これらの命題は、単射や全射という概念を、集合の元という概念を用いずに特徴づけているという点で重要な命題である。
写像

写像 f : X → Y {\displaystyle f:X\to Y} と集合 S ⊂ X {\displaystyle S\subset X} があるとき、 x ∈ S {\displaystyle x\in S} に対して x ↦ f ( x ) {\displaystyle x\mapsto f(x)} と定めることで、写像 S → Y {\displaystyle S\to Y} が自然に定まる。このようにして定めた写像をfのSへの制限といい、 f | S {\displaystyle f|_{S}} であらわす。
写像

はじめはfと f | S {\displaystyle f|_{S}} はほとんど同じもののように感じるかもしれないが、区別したほうが便利である。たとえば、 f : R → R , x ↦ x 2 {\displaystyle f:\mathbb {R} \to \mathbb {R} ,x\mapsto x^{2}} と S = { x ∈ R | x ≥ 0 } ⊂ R {\displaystyle S=\{x\in \mathbb {R} |x\geq 0\}\subset \mathbb {R} } を考えると、fは全射でも単射でもないが、 f | S {\displaystyle f|_{S}} は単射である。
写像

写像の制限は、包含写像を使って表すことができる。 i : S → X {\displaystyle i:S\to X} を包含写像とすると、
写像

である。
同値関係と商集合

「~」が集合A上の二項関係であるとは、任意の a , b ∈ A {\displaystyle a,b\in A} について、a~bであるかまたはそうでないかが必ず定まることである。例えば、実数の集合における「=」「≦」などは二項関係である。さらに、二項関係であって次の3つを満たすもののことを同値関係 (equivalent relation)と呼ぶ。
同値関係と商集合

先ほど挙げた「=」は同値関係であるが、「≦」は対称律を満たさないので同値関係ではない。他に同値関係の例として、自然数の集合上の、ある自然数nで割った余りが等しいという関係「≡(mod n)」などを挙げておく。
同値関係と商集合

さて、同値関係が与えられたときに、各 a ∈ A {\displaystyle a\in A} について次の集合を考える。
同値関係と商集合

C ( a ) = { x ∈ A | x ∼ a } {\displaystyle C(a)=\{x\in A|x\sim a\}}
同値関係と商集合

すなわちC(a)とは、同値関係~によってaと同値な元全体の集合である。これを~に関するaの同値類 (equivalent class)と呼ぶ。このように定めると、次の性質が成り立つことが容易にわかる。
同値関係と商集合

この2番目の性質は、同値関係が与えられると、元の集合Aは、互いに交わらない部分集合族によって分割(直和分解)されることを表している。この、Aを分割する部分集合族のことを、Aを同値関係~で割った商集合 (quotient set)といい、A/~と書く。集合の言葉できちんと書くと下のようになる。
同値関係と商集合

A / ∼= { C ( a ) | a ∈ A } {\displaystyle A/\sim =\{C(a)|a\in A\}}
同値関係と商集合

商集合は同値関係にある元を同じものとして同一視した集合であると言える。
同値関係と商集合

A {\displaystyle A} を三次元ユークリッド空間内の有向線分全体の集合とする。この集合 A {\displaystyle A} に同値関係 ∼ {\displaystyle \sim } を v ∼ w ⟺ v , w {\displaystyle v\sim w\iff v,w} の方向が同じでかつ長さが等しい で定める。 このとき、商集合 A / ∼ {\displaystyle A/\sim } は空間ベクトル全体の集合である。
同値関係と商集合

集合Aと部分集合Sを考えると、SからAへは包含写像という自然な単射を考えることができた。商集合でも、次のような自然な写像を考えることができる。
同値関係と商集合

π : A → A / ∼ , x ↦ C ( x ) {\displaystyle \pi :A\to A/\sim ,x\mapsto C(x)}
同値関係と商集合

この写像は明らかに全射である。この写像のことを、標準的全射とか、自然な全射という。
同値関係と商集合

以下の命題が成り立つ。
同値関係と商集合

命題 集合 A {\displaystyle A} 上の同値関係 ∼ {\displaystyle \sim } と写像 f : A → B {\displaystyle f:A\to B} について、次の3条件は同値である。
集合族

∀ λ ∈ Λ {\displaystyle \forall \lambda \in \Lambda } に対して集合 A λ {\displaystyle A_{\lambda }} が対応するとき、集合 A λ {\displaystyle A_{\lambda }} たちすべてを元とする集合を考えることができる。これを { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} と表し、 Λ {\displaystyle \Lambda } を添え字とする集合族という。このとき、 Λ {\displaystyle \Lambda } を添字集合といい、 λ {\displaystyle \lambda } を A λ {\displaystyle A_{\lambda }} の添字という。 ∀ λ ∈ Λ {\displaystyle \forall \lambda \in \Lambda } に対し A λ ⊂ X {\displaystyle A_{\lambda }\subset X} であるとき、集合族 { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} は X {\displaystyle X} の部分集合族であるという。
集合族

集合族 { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} を構成するすべての集合 A λ {\displaystyle A_{\lambda }} の合併をとった集合 { x | ∃ λ ∈ Λ , x ∈ A λ } {\displaystyle \{x|\exists \lambda \in \Lambda ,x\in A_{\lambda }\}} を和集合といい、 ⋃ λ ∈ Λ A λ {\displaystyle \bigcup _{\lambda \in \Lambda }A_{\lambda }} と表す。特に i , j ∈ Λ , i ≠ j ⇒ A i ∩ A j = ∅ {\displaystyle i,j\in \Lambda ,i\neq j\Rightarrow A_{i}\cap A_{j}=\varnothing } のとき、集合族 { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} の和集合を ∐ λ ∈ Λ A λ {\displaystyle \coprod _{\lambda \in \Lambda }A_{\lambda }} と表し、直和という。
集合族

集合族 { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} を構成するすべての集合に含まれている元の集合 { x | ∀ λ ∈ Λ , x ∈ A λ } {\displaystyle \{x|\forall \lambda \in \Lambda ,x\in A_{\lambda }\}} を共通部分といい、 ⋂ λ ∈ Λ A λ {\displaystyle \bigcap _{\lambda \in \Lambda }A_{\lambda }} と表す。
集合族

集合族 { A λ } λ ∈ Λ {\displaystyle \{A_{\lambda }\}_{\lambda \in \Lambda }} を構成するすべての集合の直積をとった集合 { { a λ } λ ∈ Λ | ∀ λ ∈ Λ , a λ ∈ A λ } {\displaystyle \{\{a_{\lambda }\}_{\lambda \in \Lambda }|\forall \lambda \in \Lambda ,a_{\lambda }\in A_{\lambda }\}} を直積といい、 ∏ λ ∈ Λ A λ {\displaystyle \prod _{\lambda \in \Lambda }A_{\lambda }} と表す。直積 ∏ λ ∈ Λ A λ {\displaystyle \prod _{\lambda \in \Lambda }A_{\lambda }} を定義域とする写像 π μ : ∏ λ ∈ Λ A λ → A μ ; { a λ } λ ∈ Λ ↦ a μ {\displaystyle \pi _{\mu }:\prod _{\lambda \in \Lambda }A_{\lambda }\to A_{\mu };\{a_{\lambda }\}_{\lambda \in \Lambda }\mapsto a_{\mu }} を第 μ {\displaystyle \mu } -成分への射影という。
濃度

この節では、集合の元の個数について考える。いま、素朴に「個数」と書いたが、この概念は自明な概念ではない。確かに、 { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} という集合の元の個数は3個である、といったことは、素朴に考えてもすぐに言うことができる。しかし、では元が「無限個」ある場合はどうしたらよいのだろうか?これは案外難しい。
濃度

そこで、個数という概念を直接定義するのではなく、2つの集合の元の個数がひとしいとはどういうことなのか、ということをまず定義することにしたい。これはそれほど難しくない。以下のようにすればよい。
濃度

定義 2つの集合AとBの間に全単射があるとき、AとBは対等であるという。
濃度

元が有限個の場合に、これまでの素朴な「個数がひとしい」という概念と一致していることは容易にわかる。
濃度

さて、この集合と集合が対等であるという関係は、同値関係である。そこで、この同値関係によるAの同値類を Card ( A ) {\displaystyle \operatorname {Card} (A)} と書き、これをAの濃度 (cardinality)という。2つの集合が対等であるということを、2つの集合の濃度がひとしいという言葉で言い換えただけである。これによって、任意の集合に適用できる「個数」にあたる概念を手に入れることができた。もちろん(くどいかもしれないが)この濃度の概念は有限集合の場合は素朴な「個数」の概念と一致する。
濃度

2つの集合があったとき、その2つの集合の濃度がひとしいか否かというのはしばしば気になることである。しかし、2つの集合の濃度がひとしいということを示すには、今のところは全単射を具体的に構成するしかなく、これはしばしば大変なこともある。例えば、閉区間[0,1]と R {\displaystyle \mathbb {R} } とは濃度がひとしいのだが、全単射を具体的に作るのは容易ではない。
濃度

そこで役に立つのが、次に挙げる定理である。
濃度

定理(Bernstein)集合AとBがあり、AからBへの単射と、BからAへの単射があるとき、
濃度

card A=card B
濃度

AからBへの単射があることと、BからAへの全射があることは同値であるから、定理のステートメントの「単射」をすべて「全射」と書き換えても構わない。
濃度

この定理を用いて、自然数の集合 N {\displaystyle \mathbb {N} } と、有理数の集合 Q {\displaystyle \mathbb {Q} } が対等であることを示してみよう。 N {\displaystyle \mathbb {N} } から Q {\displaystyle \mathbb {Q} } へは自明な単射が存在するから、逆向きの単射を作ればよい。 Q {\displaystyle \mathbb {Q} } から N × N {\displaystyle \mathbb {N} \times \mathbb {N} } への単射は容易に作れるので、結局 N × N {\displaystyle \mathbb {N} \times \mathbb {N} } から N {\displaystyle \mathbb {N} } への単射を作ればよい。 ( a , b ) ∈ N × N {\displaystyle (a,b)\in \mathbb {N} \times \mathbb {N} } に対して f ( ( a , b ) ) = 2 a − 1 ( 2 b − 1 ) {\displaystyle f((a,b))=2^{a-1}(2b-1)} と定めると、これは N {\displaystyle \mathbb {N} } への単射である。したがって、これらを合成すると Q {\displaystyle \mathbb {Q} } から N {\displaystyle \mathbb {N} } への単射が構成でき、Bernsteinの定理より N {\displaystyle \mathbb {N} } と Q {\displaystyle \mathbb {Q} } は対等である。
濃度

問 Bernsteinの定理を用いて、閉区間[0,1]と R {\displaystyle \mathbb {R} } は濃度が等しいことを証明せよ。
濃度

これまで「有限」という言葉をナイーブに未定義のままで使ってきたが、ここできちんと定義しておく。
濃度

定義 [ n ] = { 1 , 2 , . . . , n } {\displaystyle [n]=\{1,2,...,n\}} とする。特に [ 0 ] = ∅ {\displaystyle [0]=\varnothing } とする。集合Aが有限集合(finite set)であるとは、ある自然数nに対してAと [ n ] {\displaystyle [n]} が対等であることである。
濃度

これまでナイーブに想像していた概念と一致することを確認してほしい。有限集合でない集合のことを無限集合(infinite set)という。
濃度

有限集合であるための同値な条件はこのほかにもあるが、ここではひとつ挙げておく。
濃度

命題 集合Aが有限集合であることは、Aと対等なAの真部分集合が存在しないことと同値。
濃度

たとえば、偶数の集合は整数の集合の真部分集合だが、これらは対等である。有限集合ではこのようなことは起きない。
濃度

無限集合の中でも、特に N {\displaystyle \mathbb {N} } と対等な集合は特別視して、可算集合(countable set)という(可算無限集合ということもあるが、重言である)。先ほどの議論から、 Q {\displaystyle \mathbb {Q} } は可算集合である。有限集合と可算集合を合わせて高々可算な集合といい、高々可算でない集合のことを非可算集合という。
濃度

なぜ無限集合の中で可算集合を特別視するかというと、可算集合は「最も小さい」無限集合だからである。すなわち、
濃度

命題 任意の無限集合Aは、可算な部分集合を持つ。
濃度

つまり、非可算集合とは、自然数の集合よりも大きい集合のことである。
濃度

次の命題とその証明は非常によく知られている。
濃度

命題 R {\displaystyle \mathbb {R} } は非可算集合である。
濃度

(証明) 全射 p : N → R {\displaystyle p:\mathbb {N} \to \mathbb {R} } が存在したとすると、 n ↦ {\displaystyle n\mapsto } ( p ( n ) {\displaystyle p(n)} の小数部分)と定めることで、全射 f : N → ( 0 , 1 ) {\displaystyle f:\mathbb {N} \to (0,1)} を作ることができる。したがって、任意の写像 f : N → ( 0 , 1 ) {\displaystyle f:\mathbb {N} \to (0,1)} が全射でないことを示せば十分である。
濃度

f ( n ) {\displaystyle f(n)} の小数第n桁目を a n {\displaystyle a_{n}} と定める。(ただし、小数による実数の表示は一意ではないので、ここでは同じ実数について無限に9が続く表示と無限に0が続く表示がある場合は後者を採用することにする。)このとき、数列 b n {\displaystyle b_{n}} を
濃度

と定め、cを、整数部分が0で、小数第n桁目が b n {\displaystyle b_{n}} であるような実数とする。すると、明らかにcはfの値域に入っていない。よって、fは全射ではない。//
濃度

この有名な議論を、Cantorの対角線論法という。