可算集合とは？
かさんしゅうごう
可算集合とは、自然数全体と全単射が対応できる集合のことで、要素を1, 2, 3, …と番号付けして数え上げられる集合を指します。
可算集合（かさんしゅうごう、countable set）とは、集合Sの要素に自然数を使って番号を付けること（列挙すること）ができる集合のことです。より正確には、自然数全体の集合 ℕ からSへの全単射が存在する集合を可算無限集合と呼び、有限集合と可算無限集合を合わせて可算集合といいます。
可算集合の例と非例を示します。
- 自然数全体 ℕ = {0, 1, 2, 3, …}（自明に可算）
- 整数全体 ℤ（負の整数も含むが、0, 1, -1, 2, -2, …と並べれば可算）
- 有理数全体 ℚ（対角線論法的な手法で可算無限と示せる）
- 実数全体 ℝ は非可算（カントールの対角線論法により、自然数と全単射は存在しない）
可算集合は「最も小さな無限集合」であり、その濃度はアレフ・ゼロ（ℵ₀）と表されます。重要な性質として、可算無限集合の有限個の直積も可算であること、可算集合の可算個の和集合も可算であることが挙げられます。
可算性の概念は集合論・数理論理学・計算理論において基礎をなしており、「アルゴリズムで列挙できる問題のクラス」の議論などにも応用されます。
使い方・例文
「有理数は可算集合だが実数は非可算集合である」というように、無限集合の「大きさ」の違いを議論するときに使われます。
この用語をシェア
最終更新: