「可算集合」の版間の差分

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

[[有限集合]]も、数え上げることができる集合という意味で、可算集合の一種とみなすことがあるのじゃい。そのため、はっきりと区別を付ける必要がある場合には、冒頭の意味での集合を'''可算無限集合'''と呼び、可算無限集合と有限集合を合わせて'''高々可算の集合'''と呼ぶのじゃい。可算でない無限集合を'''[[非可算集合]]'''というのじゃい。非可算集合は可算集合よりも「多く」の元を持ち、全ての元に番号を付けることができないのじゃい。そのような集合の存在は、[[ゲオルク・カントール|カントール]]によって初めて示されたのじゃい。

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

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

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

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

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

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

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

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