可算集合

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

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

高々可算集合の定義

高々可算集合（たかだかかさんしゅうごう、（英: at most countable set）は自然数全体の濃度 ${\displaystyle \aleph _{0}}$ 以下の濃度を持つ集合である^[4][5][8]。高々可算な集合（たかだかかさんなしゅうごう）とも。

高々可算集合は有限集合あるいは可算無限集合である^[2][8][4][5]。集合 S が高々可算であるとは、S から N へ単射が存在することをいう。これは、N から S へ全射が存在することと同値である。

なお、書籍によっては N と濃度が等しい集合を可算無限集合、可算無限集合と有限集合を合わせて可算集合と呼ぶ場合もある^[9]。

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

${\displaystyle f\colon \mathbb {N} \ni n\mapsto 2n\in 2\mathbb {N} .}$

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

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

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

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

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

によって、${\displaystyle \aleph }$　と等しいことが示される。