非可算集合

数学において、非可算集合（ひかさんしゅうごう）、あるいは非可算無限集合とは可算集合でない無限集合のことである。集合の非可算性は基数、濃度という概念と密接に関係している。集合は、その濃度が自然数全体の集合の濃度より大きいときに、非可算である。

特徴づけ

集合の非可算性には多くの同値な言い換えが存在する。集合 X が非可算であることは以下の各条件とそれぞれ同値である：
 X から自然数全体への集合への単射が存在しない。
 X が空でなく、X の要素からなる ω-列をどのようにとっても、その列に入りそこねる X の元が出てくる。すなわち、X が空でなく、自然数集合から X への全射が存在しない。
 X の濃度が有限でも自然数全体の集合の濃度  でもない。
 X の濃度が  より真に大きい。

最初の3つの条件はZFのもとで同値である。しかし、3番目と4番目の条件の同値性はなんらかの選択原理をZFに付け加えない限り証明できない。

性質
 非可算集合 X が Y の部分集合なら Y も非可算集合である。

例 

非可算集合の例として最も知られているものは実数全体の集合 R であろう。その非可算性はカントールの対角線論法により証明される。対角線論法はその他の集合（例えば、自然数からなる無限列全体の集合、自然数からなる集合全体からなる集合族）の非可算性を証明するのにも応用される。R の濃度をしばしば連続体濃度と呼び c や  または  (beth-one) で表す。

カントール集合 は R の非可算部分集合である。カントール集合はフラクタル構造を持ち、ハウスドルフ次元が0より大で1未満である（R は1次元である）。この集合は次の事実の例となっている： R の部分集合でハウスドルフ次元が0より真に大きいものは必ず非可算集合である。

R から R への関数全体の集合も非可算であるが、これは連続体濃度よりもさらに「非可算」である。この集合の濃度は  (beth-two) で、 よりも大きいのである。

非可算集合のさらに抽象的な例としては、可算順序数全体からなる集合 ω1 あるいは Ω がある。ω1 の濃度を  (aleph-one) で表す。選択公理を用いることによって、 が最小の非可算基数であることが証明できる。このことから、実数全体の集合の濃度  は、 に等しいか真に大きい。ゲオルク・カントールは「等しいのか大きいのか、本当はどちらなのか」を問うた最初の研究者である。1900年、ダフィット・ヒルベルトによりこの問題はヒルベルトの23の問題の第1問題とされた。 という主張は今では連続体仮説と呼ばれ、集合論のZFCからは独立であることが証明されている。

選択公理を用いない場合

選択公理を仮定しない場合、 と比較できない濃度が存在しうる、具体的にはデデキント有限な無限集合の濃度がそうである。これらの濃度をもつ集合は上記の非可算性の最初の3つの特徴づけを満たすが、4番目は満たさない。これらの集合は濃度の意味で自然数の集合より大きいわけではないので、それを非可算とは呼ぶことを避ける人もいる。

選択公理を仮定する場合、基数  に関する以下の条件は全て同値である：

、ただし  であり  は  よりも大きい最小のである

しかしながら、選択公理を仮定しない場合これらはすべて異なる条件となりうる。そのため、このときどれが最も適切な "非可算性" の一般化であるかは明らかでない。この場合は非可算という言葉を使うことを避け、これらのうちのどれを意味しているのかを明確にすることが最善であろう。

脚注

参考文献 
Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition).

関連項目
単射
自然数
アレフ数
 ベート数

外部リンク
Proof that R is uncountable

数学に関する記事
集合論
無限
基数