可算集合のソースを表示

{{出典の明記|date=2015年10月}}
'''可算集合'''（かさんしゅうごう、{{lang-en|countable set または denumerable set}}）または'''可付番集合'''とは、おおまかには、[[自然数]]全体と同じ程度多くの[[元_(数学)|元]]を持つ[[集合]]のことである。各々の元に 1, 2, 3, … と番号を付けることのできる、すなわち元を全て数え上げることのできる[[無限]]集合と表現してもよい<ref name=":0">{{Cite web|和書|url=https://www.kurims.kyoto-u.ac.jp/~cs/lecture/2008/prelim.pdf |title=「コンピュータサイエンス入門」講義資料 |access-date=2022-07-27 |publisher=京都大学数理解析研究所}}</ref>。

[[有限集合]]も、数え上げることができる集合という意味で、可算集合の一種とみなすことがある<ref name=":0" />。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を'''可算無限集合''' (countably infinite set) と呼び、可算無限集合と有限集合を合わせて'''高々可算''' (at most countable) の集合と呼ぶ<ref name=":1">{{Cite web|和書|url=https://www.math.is.tohoku.ac.jp/~obata/student/subject/file/2018-7_kasan.pdf |title=第7章 可算集合 |access-date=2022-07-27 |publisher=Computer Science, RIMS, Kyoto University}}</ref><ref name=":2">{{Cite web|和書|url=http://www4.math.sci.osaka-u.ac.jp/~matsumoto/courses/2016-fs2/docs/2016-fs2-B-mod-20161027.pdf |title=数学の楽しみ 2D　集合の濃度 |access-date=2022-07-27 |publisher=大阪大学大学院理学研究科数学専攻・理学部数学科　松本佳彦}}</ref>。可算でない無限集合を'''[[非可算集合]]''' (uncountable set) という<ref name=":3">{{Cite web|和書|url=http://www.u.dendai.ac.jp/~ochi/suen2B_1.pdf |title=可算集合と非可算集合 |access-date=2022-07-27 |publisher=東京電機大学理工学部理学系数学コース　越智 禎宏}}</ref>。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができない。そのような集合の存在は、[[ゲオルク・カントール|カントール]]によって初めて示された。

== 定義 ==
可算集合とは '''N''' と[[濃度 (数学)|濃度]]が等しい集合のことである<ref name=":0" />。すなわち、集合 ''S'' が'''可算'''であるとは、自然数全体の集合 '''N''' との間に[[全単射]]が存在することをいう<ref name=":1" /><ref name=":2" />。

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

慣例では、可算集合の濃度を <math>\aleph_0</math>（[[アレフ数|アレフゼロ]]、aleph-null）で表す。例えば、'''N''' の濃度が可算であることを <math>|\mathbb{N}|=\aleph_0</math> などと表す。

== 例と性質 ==
[[無限集合]]においては、その真部分集合と濃度が等しいことがあり得る。<ref name=":2" />例えば、[[偶数]]の自然数全体の集合 2'''N''' は '''N''' との間に次の全単射が存在する。
:<math>f\colon\mathbb{N} \ni n \mapsto 2n \in 2\mathbb{N}.</math>
よって、2'''N''' は可算集合である。また、[[整数]]全体の集合 '''Z''' や[[有理数]]全体の集合 '''Q''' も可算である<ref name=":0" /><ref name=":3" />。しかし、[[実数]]全体の集合 '''R''' は非可算である。この事実は[[カントールの対角線論法]]によって示される<ref name=":0" /><ref name=":3" />。'''R''' の濃度は'''[[連続体濃度]]'''と呼ばれ、<math>\aleph</math> または <math>\mathfrak{c}</math> で表される。

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

可算個の可算集合の[[合併 (集合論)|和集合]]や、有限個の可算集合の[[直積集合]]はまた可算である<ref name=":2" />。これより、[[代数的数]]全体の集合 <span style="text-decoration:overline">'''Q'''</span> は可算であることが従う。しかし、可算個の可算集合の直積集合や、可算集合の[[冪集合]]は非可算であり、その濃度は連続体濃度である<ref name=":3" />。

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

:<math>2^{\aleph_0} \le \aleph_0^{\aleph_0} \le (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}</math>

によって、<math>\aleph</math>　と等しいことが示される。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
*[[濃度 (数学)]]
*[[連続体仮説]]
*[[ヒルベルトの無限ホテルのパラドックス]]

{{集合論}}
{{Settheory-stub}}
{{DEFAULTSORT:かさんしゆうこう}}
[[Category:無限]]
[[Category:数学に関する記事]]