等数性

数学では、2つの集合またはクラス AとBが同数であるとは、それらの間に1対1の対応（または全単射）が存在する場合、つまり、 AからBへの関数が存在し、 Bのすべての要素yに対して、 f ( x ) = y を満たすAの要素xがちょうど1つ存在する場合です。^[1]同数の集合は、同じ濃度（要素の数）を持つと言われています。^[2]濃度の研究は、しばしば同数性（数の同値性）と呼ばれます。代わりに、等強度（強さの同値性）や等ポテンス（べき乗の同値性）という用語が使用されることもあります。

等数性は同値関係の特徴的な性質を持つ。^{[1] 2つの集合}AとBが等数である という表現は通常、

${\displaystyle A\approx B\,}$または、または${\displaystyle A\sim B}$${\displaystyle |A|=|B|.}$

一対一表現を用いた同数性の定義は、有限集合と無限集合の両方に適用でき、2つの集合が無限であっても同じサイズであるかどうかを述べることができる。集合論の発明者であるゲオルク・カントールは、 1874年に無限には複数の種類があること、特にすべての自然数の集合とすべての実数の集合は、どちらも無限であるが同数ではないことを示した（カントールの最初の不可算性の証明を参照）。物議を醸した1878年の論文で、カントールは集合の「べき」の概念を明示的に定義し、それを使用してすべての自然数の集合とすべての有理数の集合が同数であること（無限集合の真部分集合が元の集合と同数である例）、および実数の可算無限個のコピーの直積でさえも、実数の単一のコピーと同数であることを証明した。 ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Q} }$

1891年のカントールの定理は、いかなる集合もそれ自身の冪集合（その部分集合全体の集合）と同数ではないことを意味している。 ^[1]これにより、単一の無限集合から始めて、より大きな無限集合を定義できるようになる。

選択公理が成り立つ場合、集合の基数はその基数の最小の順序数とみなすことができます（初期順序数を参照）。そうでない場合は、（スコットのトリックにより）その基数を持つ最小ランクの集合の集合とみなすことができます。 ^[1]

任意の2つの集合が同数であるか、または一方の集合の濃度が他方の集合の濃度より小さいという主張は選択公理と同等である。^[3]

同数集合は一対一に対応しており、^[4]同じ濃度を持つと言われます。集合Xの濃度は、本質的には集合の要素の数の尺度です。^{[1]同数性は}同値関係（反射性、対称性、推移性）の特徴的な性質を持っています。 ^[1]

反射性

集合Aが与えられたとき、A上の恒等関数はAからそれ自身への全単射であり、すべての集合Aがそれ自身と同数であることを示します: A ~ A。

対称

2 つの集合AとB の間のすべての一対一関数には、 BとAの間の一対一関数である逆関数が存在し、集合Aが集合Bと同数である場合、BもAと同数であることを意味します。つまり、 A ~ Bであれば、B ~ Aとなります。

推移性

3 つの集合A、B、Cと 2 つの全単射f  : A → Bおよびg  : B → Cが与えられている場合、これらの全単射の合成 g ∘ fはAからCへの全単射です。したがって、AとB が同数であり、BとCが同数である場合、AとC は同数です。つまり、 A ~ BおよびB ~ Cを合わせるとA ~ Cになります。

集合の濃度をそれと同数であるすべての集合の同値類として定義しようとする試みは、公理的集合論の標準形であるツェルメロ-フランケル集合論では問題である。なぜなら、空でない集合の同値類は集合としては大きすぎるため、適切な類になってしまうからである。ツェルメロ-フランケル集合論の枠組みでは、関係は定義により集合に制限され（集合A上の二項関係は直積A × Aのサブセットである）、ツェルメロ-フランケル集合論にはすべての集合の集合は存在しない。ツェルメロ-フランケル集合論では、集合の濃度をそれと同数であるすべての集合の同値類として定義する代わりに、各同値類に代表的な集合を割り当てようとする（基数割り当て）。公理的集合論の他のいくつかのシステム、例えばフォン・ノイマン・バーネイス・ゲーデル集合論やモース・ケリー集合論では、関係はクラスに拡張されます。

集合Aの基数は集合Bの基数以下であるとは、 AからBへの1 対 1 関数( 単射 )が存在する場合をいいます。これは、 | A | ≤ | B |と表記されます。 AとBが同数でない場合、 Aの基数はBの基数より厳密に小さいといいます。これは、 | A | < | B |と表記されます。選択公理が成り立つ場合、基数に対して三分法の法則が成り立ち、したがって任意の 2 つの集合は同数であるか、一方の基数が他方より厳密に小さいかのいずれかになります。^{[1]基数の三分法の法則は、}選択公理も意味します。^[3]

シュレーダー・ベルンシュタインの定理は、2つの一対一関数f  : A → Bとg  : B → Aが存在する任意の2つの集合AとBは同数であることを述べています。つまり、| A |≤| B |かつ| B |≤| A |ならば、 | A |=| B |です。^{[1] [3]この定理は}選択公理に依存しません。

カントールの定理は、いかなる集合もその冪集合（その部分集合全体の集合）と同数ではないことを意味している。 ^[1]これは無限集合についても成り立つ。具体的には、可算無限集合の冪集合は非可算集合である。

すべての自然数からなる無限集合Nが存在し、任意の集合の冪集合が存在すると仮定すると、各集合がその前の集合の冪集合である無限集合のシーケンスN、P ( N )、P ( P ( N ) )、P ( P ( P ( N ) ) )、…を定義できます。カントールの定理により、このシーケンスの各集合の濃度は、その前の集合の濃度を厳密に超えているため、無限集合はますます大きくなります。

カントールの研究は、同時代の人々、例えば有限主義^[5]の数学哲学を強く支持し、数が実際の完全な全体性（実際の無限）を形成できるという考えを否定したレオポルド・クロネッカーなどから厳しく批判された。しかし、カントールの考えは、リヒャルト・デデキントなど他の人々によって擁護され、最終的にはダヴィド・ヒルベルトの強い支持を得て広く受け入れられた。詳細についてはカントールの理論をめぐる論争を参照。

ツェルメロ-フランケル集合論の枠組みでは、冪集合公理は任意の集合の冪集合の存在を保証する。さらに、無限公理は少なくとも 1 つの無限集合、つまり自然数を含む集合の存在を保証する。冪集合公理と無限公理を意図的に省略し、カントールが提唱した無限の無限階層の定義を許可しない代替集合論、たとえば「一般集合論」(GST)、クリプキ-プラテック集合論、ポケット集合論 (PST) がある 。

集合N、P ( N )、P ( P ( N ))、P ( P ( P ( N )))、…に対応する濃度はベス数 、、、、…であり、最初のベス数は任意の可算無限集合の濃度である(アレフ ノート)に等しく、2 番目のベス数は連続体の濃度である に等しい。 ${\displaystyle \beth_{0}}$${\displaystyle \beth_{1}}$${\displaystyle \beth_{2}}$${\displaystyle \beth_{3}}$${\displaystyle \beth_{0}}$${\displaystyle \aleph_{0}}$${\displaystyle \beth_{1}}$${\displaystyle {\mathfrak {c}}}$

場合によっては、集合Sとその真部分集合が同数になることがあります。たとえば、偶数の自然数の集合は、すべての自然数の集合と同数です。それ自身の真部分集合と同数である集合は、デデキント無限集合と呼ばれます。^{[1] [3]}

可算選択公理 (AC ω ) は選択公理₍ AC )の弱い変形であり、デデキント無限でない集合が実際には有限であることを示すために必要である。選択公理 (ZF) のないツェルメロ-フランケル集合論の公理は、すべての無限集合がデデキント無限であることを証明するのに十分強力ではないが、可算選択公理 ( ZF + AC _ω ) のあるツェルメロ-フランケル集合論の公理は十分に強力である。^[6]デデキントによって与えられたもの以外の集合の有限性と無限性の定義では、これに選択公理を必要としない。有限集合 § 有限性のための必要十分条件を参照。^[1]

等数性は、基数算術の定義を可能にする方法で、基本的な集合演算と互換性があります。^[1]特に、等数性は互いに素な和と互換性があります。4つの集合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 )

これらの特性は基数の乗算を正当化するために使用されます。

2 つの集合XとY が与えられたとき、 YからXへのすべての関数の集合はX ^Yで表されます。このとき、次のステートメントが成り立ちます。

• A ~ BかつC ~ DならばA ^C ~ B ^Dです。
• A ^{B ∪ C} ~ A ^B × A ^C （ BとC は互いに重ならない）
• ( A × B ) ^C ~ A ^C × B ^C
• ( A ^B ) ^C ~ A ^{B × C}

これらの特性は基数累乗を正当化するために使用されます。

さらに、与えられた集合A ( Aのすべての部分集合の集合) の冪集合は、集合Aからちょうど 2 つの要素を含む集合へ のすべての関数の集合である集合 2 ^Aと同数です。

圏論において、集合の圏（Setと表記）は、すべての集合をオブジェクトとして集めたものと、集合間のすべての関数を射として集めたものから成り、関数の合成を射の合成とする圏である。Setでは、 2つの集合間の同型はまさに一対一であり、2つの集合がSet内のオブジェクトとして同型である場合に、それらの集合はまさに同数である。

• 組み合わせクラス
• ヒュームの原理