可算集合

可算集合（かさんしゅうごう、countable set 又は denumerable set）もしくは可付番集合とは、おおまかには、自然数全体と同じ程度多くの元を持つ集合のことじゃい。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる無限集合と表現してもよいのじゃい。

有限集合も、数え上げることができる集合という意味で、可算集合の一種とみなすことがあるのじゃい。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を可算無限集合と呼び、可算無限集合と有限集合を合わせて高々可算の集合と呼ぶのじゃい。可算でない無限集合を非可算集合というのじゃい。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができないのじゃい。そのような集合の存在は、カントールによって初めて示されたのじゃい。

定義

可算集合とは N と濃度が等しい集合のことじゃい。すなわち、集合 S が可算であるとは、自然数全体の集合 N との間に全単射が存在することをいうのじゃい。

また、高々可算な集合とは、N の濃度以下の濃度を持つ集合のことじゃい。すなわち、集合 S が高々可算であるとは、S から N へ単射が存在することをいうのじゃい。これは、N から S へ全射が存在することと同値じゃい。

慣例では、可算集合の濃度を $\aleph _{0}$ （アレフゼロ、aleph-null）で表すのじゃい。例えば、N の濃度が可算であることを $|\mathbb {N} |=\aleph _{0}$ などと表すのじゃい。

例と性質

無限集合においては、その真部分集合と濃度が等しいことがあり得るのじゃい。例えば、偶数の自然数全体の集合 2N は N との間に次の全単射が存在するのじゃい。

f\colon \mathbb {N} \to 2\mathbb {N} \ (x\mapsto 2x)

よって、2N は可算集合じゃい。また、整数全体の集合 Z や有理数全体の集合 Q も可算じゃい。しかし、実数全体の集合 R は非可算じゃい。この事実はカントールの対角線論法によって示されるのじゃい。R の濃度は連続体濃度と呼ばれ、 $\aleph$ または ${\mathfrak {c}}$ で表されるのじゃい。

選択公理を認めるならば、可算濃度は無限集合の濃度のうち最小のものであることが示されるのじゃい。可算濃度と連続体濃度の間に他の濃度が存在するか否かは、ZFC とは独立であり、通常は存在しないと仮定するのじゃい。この仮定を連続体仮説というのじゃい。

可算個の可算集合の和集合や、有限個の可算集合の直積集合はまた可算じゃい。これより、代数的数全体の集合 Q は可算であることが従うのじゃい。しかし、可算個の可算集合の直積集合や、可算集合の冪集合は非可算であり、その濃度は連続体濃度じゃい。

可算個の可算集合の直積集合の濃度は、この濃度不等式

2^{\aleph _{0}}\leq \aleph _{0}^{\aleph _{0}}\leq (2^{\aleph _{0}})^{\aleph _{0}}=2^{\aleph _{0}}

によって、 $\aleph$ 　と等しいことが示されるのじゃい。

可算集合

定義

例と性質

関連項目