可算集合

自然数全体と同じ濃度を持つ集合
可算から転送)

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

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

定義編集

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

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

慣例では、可算集合の濃度を  アレフゼロ、aleph-null)で表す。例えば、N の濃度が可算であることを   などと表す。

例と性質編集

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

 

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

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

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

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

 

によって、  と等しいことが示される。

脚注編集

[脚注の使い方]
  1. ^ a b c d e 「コンピュータサイエンス入門」講義資料”. 京都大学数理解析研究所. 2022年7月27日閲覧。
  2. ^ a b 第7章 可算集合”. Computer Science, RIMS, Kyoto University. 2022年7月27日閲覧。
  3. ^ a b c d 数学の楽しみ 2D 集合の濃度”. 大阪大学大学院理学研究科数学専攻・理学部数学科 松本佳彦. 2022年7月27日閲覧。
  4. ^ a b c d 可算集合と非可算集合”. 東京電機大学理工学部理学系数学コース 越智 禎宏. 2022年7月27日閲覧。

関連項目編集