等濃
数学において二つの集合 A, B の濃度が等しいとは、それらの間の一対一対応(全単射)が存在すること、すなわち A から B への写像 f: A → B が存在して B の各元 y に対してちょうど一つづつの x ∈ A が f(x) = yを満たすときに言う。濃度が等しいことは、それら集合に属する元の数が同じであることと解釈することができる。このように集合の濃度が等しいとき、それら集合は同数 (equi­numerous), 対等もしくは同等 (equi­pollent)初等幾何学における有向線分の 同方向等長性(同方向同長)と混同してはならない。有向線分の equipollence を同値関係とする同値類は幾何学的ベクトルである。 あるいは等濃 (equi­potent, equicardinality) であるなどと言う字義としては、接頭辞 "equi-" は「同じ」「等しい」ことを意味する。"-noumerous", "-numerosity" は「数(の)」、"-pollent", "-pollency" は「勢力(の)」「強さ(の)」の意、また "potency" は「冪」("power") の意で "cardinality" (「濃度」) の別名である。。
「濃度が等しい」という関係は同値関係の三つの公理(反射律・対称律・推移律)を満足する。記号では二つの集合 A, B が等濃であることを A \approx B,\quad A \sim B,\quad |A|=|B| などで表す。
全単射を用いたこの等濃性の定義は、有限集合にも無限集合にも適用できるから、これにより無限集合の場合であっても「同じ数」かどうかを議論することができることになる。集合論の祖ゲオルク・カントールは1874年に、無限が一種類ではないこと、特に自然数全体の集合と実数全体の集合は(ともに無限でありながらも)濃度が異なることを示した(カントールの最小非可算性の証明も参照)。物議を醸した1878年の論文で、カントールは集合の「濃度」("power") の概念を明示的に定義して、それを用いて自然数全体の成す集合と有理数全体の成す集合が等濃であること(これは無限集合の真部分集合がもとの集合と等濃になるという状況の一つの例を与えている)や、実数全体の成す集合のいくつか(可算無限個でもよい)のコピーの直積集合が実数全体の成す集合ひとつと等濃であることなどを示した。
1891年以降現れたカントールの定理によれば、任意の集合は自身の冪集合(部分集合全体の成す集合)に等濃となることはない。ゆえに一つ無限集合が与えられれば、それを手掛かりにより大きな無限濃度を持つ集合を次々に作り出すことができる。
選択公理が成り立つならば、各集合の基数 (cardinal number) はその集合と同じ濃度を持つ最小の順序数として定義することができる(始数の項を参照)。選択公理がない場合でも、スコットのトリックにより同じ濃度を持つ最小ランク (minimal ordinal rank) の集合全体の成す集合と見なせる。
任意の二つの集合の濃度が比較可能(互いに等濃であるかさもなくば一方が他方よりも濃度が小さい)であるという条件は、選択公理と同値である。
互いに等濃な集合は同じ濃度を持つ。集合 X の濃度とは「その集合の元の数」を測るものである。互いに等濃であるという関係(等濃性)は同値関係の定義性質(反射律・対称律・推移律)を満たす:
反射性: 任意の集合 A に対し、A 上の恒等写像を考えれば、これは A から A への全単射ゆえ A ~ A が成り立つ。
対称性: 二つの集合 A, B の間に全単射が存在するとき、その逆写像は B, A の間の全単射であるから、A ~ B ならば B ~ A が成り立つ。
推移性: 三つの集合 A, B, C に対し二つの全単射 f: A → B および g: B → C が存在すれば、写像の合成 g ∘ f は A から C への全単射であるから、A ~ B かつ B ~ C ならば A ~ C が成り立つ。
ここでこの同値関係に関する同値類(濃度を互いに等濃な集合全体)として集合の濃度を定義しようとするならば、それは公理的集合論で標準的に用いられるツェルメロ–フレンケル集合論 (ZF) では問題になる—これは任意の空でない同値類は、集合となるには大きすぎ、真クラスとなってしまうからである。ZF集合論の枠組みでは二項関係は集合上に限って定義される(集合 A 上の二項関係とは直積集合 A × A の任意の部分集合のことであり、ZF において普遍集合は存在しえないのであった)。したがってZFのもとでは「すべての集合の等濃性に関する同値類」として集合の濃度を定義するのではなく、そのような「同値類の代表元となるべき」集合を割り当てる方法(濃度割り当て)を考えなければならない。真クラスを持つようなほかの公理的集合論(例えば、フォンノイマン–ベルナイス–ゲーデル集合論やMK集合論など)ではクラスの間の二項関係も考えることができる。
集合 A の濃度が集合 B の濃度よりも小さい(あるいは以下である)とは A から B への単射(一対一の写像)が存在するときに言い、これを A ≤ B と表す。このとき A と B が等濃でないならば、A の濃度は B の濃度よりも真に小さい(あるいは未満である)と言い、A < B と書く。選択公理が真ならば、基数に対する三分律—任意のふたつの集合は互いに等濃であるか、さもなくば一方が他方よりも真に小さい濃度を持つ—を満足する。この基数に対する三者択一の法則は選択公理を導く。
シュレーダー–ベルンシュタインの定理は、二つの集合 A, B は、二つの単射 f: A → B および g: B → A があるとき、互いに等濃であることを述べる:
定理 (Schröder–Bernstein): A ≤ B かつ B ≤ A ならば A = B が成り立つ。
この定理は選択公理に依らない。
カントールの定理からは、任意の集合がその冪集合(部分集合全体の成す集合)と等濃でないことがわかる。このことは、無限集合に対しても成り立っている。特に、可算無限集合の冪集合は非可算無限集合になる。
自然数全体の成す無限集合 ℕ の存在と、任意の集合の冪集合の存在を認めれば、次々に冪集合をとることで得られる無限集合の無限の系列 ℕ, 𝔓(ℕ), 𝔓(𝔓(ℕ)), 𝔓(𝔓(𝔓(ℕ))), … を作ることができる。カントールの定理により、この系列の各集合の濃度は直前の項の濃度よりも真に大きいから、どんどん濃度は大きくなっていく。
カントールの仕事は同時代の一部の数学者からは痛烈な批判を受けることになった(例えば、数学の哲学として有限の立場に強く立脚したレオポルト・クロネッカーは、そのような無限の数の概念(実無限)を真っ向から否定した)が、ほかの数学者(例えばリヒャルト・デーデキント)によって擁護され、最終的には大いに受け入れられ、ダフィット・ヒルベルトによる強固な支持を受けた(カントール理論をめぐる論争の項を参照)。
ツェルメロ–フレンケル集合論の枠組み内では、冪集合公理が任意の集合の冪集合の存在を保証し、また無限公理が少なくとも一つの無限集合(これは自然数全体の成す集合を含む)の存在を保証する。冪集合公理や無限公理を意図的に除外した代替集合論(例えば、一般集合論, クリプキ–プラーテク集合論、ポケット集合論 など)もあり、その枠組みのなかでは上記のカントール提示した無限集合からなる無限階層は定義することができない。
無限系列 ℕ, 𝔓(ℕ), 𝔓(𝔓(ℕ)), 𝔓(𝔓(𝔓(ℕ))), … の各集合に対応する濃度はベート数 ב‎0, ב‎1, ב‎2, ב‎3, … で表される。最小のベート数 ב‎0 は可算無限濃度 ℵ0 に等しく、その次のベート数 ב‎1 は連続体濃度 𝔠 に等しい。
集合がその真部分集合と等濃になる場合がある(例えば自然数全体の成す集合はその真部分集合である偶数全体の成す集合と等濃である)。そのような集合はデデキント無限であると言う。
デデキント無限でない集合が実際に有限集合となることを示すには(選択公理 (AC) よりも弱い)可算選択公理 (ACω) が必要になる。選択公理を持たないツェルメロ–フレンケル集合論 ZF は任意の無限集合がデデキント無限となることを示すには十分な強さではないが、ZF に可算選択公理を加えた ZF+ACω はそれに十分である。集合の有限性と無限性の別な定義では、選択公理を要しない。
等濃性は基数の算術のもとで集合の基本演算と両立する。具体的に例えば非交和との両立性は:
命題: 集合 A, B, C, D は A と C および B と D がそれぞれ互いに素かつ濃度は A ~ B かつ C ~ D であるものとすると A ∪ C ~ B ∪ D が成り立つ。
これは基数の加法を正当化するものである。
A ~ B かつ C ~ D ならば A × C ~ B × D が成り立つ。
A × B ~ B × A が成り立つ。
(A × B) × C ~ A × (B × C) が成り立つ。
というような形で述べられる。これらの性質により基数の乗法が正当化できる。
冪についても、Y から X への写像全体の成す集合を XY と書けば
A ~ B かつ C ~ D ならば AC ~ BD が成り立つ。
AB∪C ~ AB × AC (ただし B ∩ C = ∅) が成り立つ。
(A × B)C ~ AC × BC が成り立つ。
(AB)C ~ AB×C が成り立つ。
これらの性質により基数の冪が正当化される。
他にも、与えられた集合 A に対してその冪集合(A の部分集合全体の成す集合)は A から二値集合への写像全体の成す集合 2A に等濃である。
すべての集合を対象としその間のすべての写像を射とする圏 Setにおいて、二つの対象の間の同型射とは二つの集合の間の全単射のことにほかならず、したがって二つの集合が等濃であることはこの圏において同型であるということにほかならない。