カーディナリティ

数学において、濃度は集合間の相対的な大きさを比較する関係を表します。^[1]たとえば、集合と はそれぞれ 3 つの要素を含むため、同じ大きさです。 19 世紀後半から、この概念は無限集合に一般化され、異なる種類の無限を区別し、それらに対して算術演算を実行できるようになりました。 濃度について言及するときによく使用される概念は 2 つあります。1 つは単射と単射を使用して集合を直接比較するもので、もう 1 つは基数を使用するものです。^[2] 集合の濃度は、他のサイズの概念と混同する可能性がない場合は、そのサイズと呼ばれることもあります。^[a]${\displaystyle A=\{1,2,3\}}$${\displaystyle B=\{2,4,6\}}$

2つの集合⁠ ⁠${\displaystyle A}$と⁠ ⁠${\displaystyle B}$が同じ濃度を持つ場合、通常は と表記されます。ただし、個々の集合 の濃度を指す場合は、両側に縦棒を付けて と表記するだけです。 ^[3]これは絶対値と同じ表記法であり、意味は文脈によって異なります。集合の濃度は、、 、、 と表記されることもあります。 ${\displaystyle |A|=|B|}$${\displaystyle A}$${\displaystyle |A|}$${\displaystyle A}$${\displaystyle n(A)}$${\displaystyle A}$${\displaystyle \operatorname {card} (A)}$${\displaystyle \#A}$

粗雑な基数感覚、つまり、ある物や出来事のグループが、他のグループと比較して、より多くの、より少ない、または同じ数のインスタンスを含むという認識は、今日のさまざまな動物種に見られ、数百万年前に起源があることを示唆しています。^[4]人間の基数表現は、4万年前には、グループの大きさを記録された刻み目のグループ、または棒や貝殻などの他のものの代表的なコレクションと同一視していました。^[5]基数を数値として抽象化することは、紀元前3000年までにシュメールの数学と、特定のグループや出来事を参照せずに数値を操作することに明らかです。^[6]

紀元前6世紀から、ギリシャの哲学者の著作には、無限集合の濃度についてのヒントが見られる。彼らは、無限の概念を、ある数に繰り返し1を加えるなどの終わりのない一連の動作とみなしていたが、無限の数の集合の大きさは物とは考えていなかった。^[7]古代ギリシャの無限の概念は、物を部分に分割し、それを際限なく繰り返すことも考えていた。ユークリッドの『原論』では、通約可能性は、どんなに小さくても、 aとb の両方に整数回端から端まで敷くことができる3番目の線分がある限り、2つの線分aとbの長さを比として比較できる能力であると説明されている。しかし、無理数の発見により、すべての有理数の無限集合でさえ、あらゆる可能な線分の長さを説明するのに十分ではないことがわかった。^[8]それでも、濃度を持つものとしての無限集合という概念はなかった。

無限集合をよりよく理解するために、集合論の創始者であるゲオルク・カントールは 1880年頃に濃度の概念を定式化した。彼は2つの集合を一対一に対応させる過程を、一意の関係に基づく2つの集合の要素間の一対一対応である単射で調べた。1891年、カントールは対角線論証を発表し、自然数の集合と一対一に対応させることができない数の集合、つまり自然数の無限集合よりも多くの要素を含む無数集合が存在することを証明した。^[9]

有限集合の濃度は単純にその要素の数に匹敵しますが、その概念を無限集合に拡張するには、通常、任意の集合（その一部は無限である可能性があります）の比較の概念を定義することから始まります。

2つの集合が同じ濃度を持つとは、⁠ ⁠ ⁠から⁠ ⁠への全単射（つまり、一対一対応）が存在する場合、^[10]つまり、⁠ ⁠ ⁠から⁠ ⁠への関数が単射かつ全射であることを意味します。このような集合は、等ポテンシャル、等数、または等数集合であると言われています。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

たとえば、関数は⁠ ⁠から⁠ ⁠への一対一関数であるため、非負の偶数の集合は自然数の集合と同じ濃度を持ちます(図を参照)。 ${\displaystyle E=\{0,2,4,6,{\text{...}}\}}$${\displaystyle \mathbb {N} =\{0,1,2,3,{\text{...}}\}}$${\displaystyle f(n)=2n}$${\displaystyle \mathbb {N} }$${\displaystyle E}$

有限集合⁠ ⁠${\displaystyle A}$および⁠ ⁠${\displaystyle B}$に対して、⁠ ⁠から⁠ ⁠への全単射が存在する場合、⁠ ⁠から⁠ ⁠への各単射または全射関数は全単射です。これは、無限⁠ ⁠ ⁠ ⁠および⁠ ⁠では当てはまりません。たとえば、で定義される⁠ ⁠ ⁠から⁠ ⁠への関数⁠ ⁠は単射ですが、たとえば 2 は にマッピングされないため、全射ではありません。また、 で定義される⁠ ⁠ ⁠から⁠ ⁠への関数(モジュロ演算を参照) は全射ですが、たとえば 0 と 1 はどちらも 0 にマッピングされるため、単射ではありません。⁠ ⁠も⁠ ⁠ も⁠ ⁠に異議を唱えることはできません。これは、 ⁠ ⁠の存在によって確立されています。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle g}$${\displaystyle \mathbb {N} }$${\displaystyle E}$${\displaystyle g(n)=4n}$${\displaystyle h}$${\displaystyle \mathbb {N} }$${\displaystyle E}$${\displaystyle h(n)=n-(n{\text{ mod }}2)}$${\displaystyle g}$${\displaystyle h}$${\displaystyle |E|=|\mathbb {N} |}$${\displaystyle f}$

⁠ ${\displaystyle A}$⁠から⁠ ⁠への単射関数が存在する場合、 ⁠ ⁠の基数は⁠ ⁠${\displaystyle B}$の基数以下になります。 ${\displaystyle A}$${\displaystyle B}$

かつ ならば、となる（シュレーダー・ベルンシュタインの定理として知られる事実）。選択公理は、任意の⁠ ⁠および⁠ ⁠に対してまたはとなることと同等である 。^{[11] [12]}${\displaystyle |A|\leq |B|}$${\displaystyle |B|\leq |A|}$${\displaystyle |A|=|B|}$${\displaystyle |A|\leq |B|}$${\displaystyle |B|\leq |A|}$${\displaystyle A}$${\displaystyle B}$

${\displaystyle A}$⁠ ⁠から⁠ ⁠への単射関数はあるが、全単射関数はない場合、⁠ ⁠ ⁠の基数は⁠ ⁠${\displaystyle B}$の基数よりも厳密に小さくなります。 ${\displaystyle A}$${\displaystyle B}$

たとえば、すべての自然数の集合⁠ ⁠${\displaystyle \mathbb {N} }$の濃度はその冪集合⁠ ⁠よりも厳密に小さくなります。これは、 ⁠ ⁠から⁠ ⁠への単射関数であり、 ⁠ ⁠から⁠ ⁠への関数はいずれも全単射ではないことが示されるためです(図を参照)。同様の議論により、⁠ ⁠ の濃度はすべての実数の集合⁠ ⁠の濃度よりも厳密に小さくなります。証明については、カントールの対角線論証またはカントールの最初の不可算性証明を参照してください。 ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$${\displaystyle g(n)=\{n\}}$${\displaystyle \mathbb {N} }$${\displaystyle {\mathcal {P}}(\mathbb {N} )}$${\displaystyle \mathbb {N} }$${\displaystyle {\mathcal {P}}(\mathbb {N} )}$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {R} }$

上の節では、集合の「濃度」は関数的に定義されていました。つまり、特定のオブジェクトそのものとしては定義されていませんでした。しかし、そのようなオブジェクトは次のように定義できます。

同じ濃度を持つ関係は同数性と呼ばれ、これはすべての集合のクラスにおける同値関係です。したがって、この関係における集合Aの同値クラスは、 Aと同じ濃度を持つすべての集合で構成されます。「集合の濃度」を定義する方法は 2 つあります。

1. 集合Aの濃度は、同数性に基づく同値類として定義されます。
2. 各同値類には代表集合が指定されます。最も一般的な選択はそのクラスの最初の順序数です。これは通常、公理的集合論における基数の定義として採用されます。

選択公理を仮定すると、無限集合の濃度は次のように表される。

${\displaystyle \aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots .}$

各順序数 に対して、より大きい最小の基数 です。 ${\displaystyle \alpha }$${\displaystyle \aleph _{\alpha +1}}$${\displaystyle \aleph _{\alpha }}$

自然数の濃度はアレフゼロ( )で表され、実数の濃度は「 」(小文字のフラクトゥール文字「c」)で表され、連続体の濃度とも呼ばれます。カントールは、対角線上の議論を使用して、 であることを示しました。 であることが示され、これは自然数のすべての部分集合の集合の濃度でもあります。 ${\displaystyle \aleph _{0}}$${\displaystyle {\mathfrak {c}}}$${\displaystyle {\mathfrak {c}}>\aleph _{0}}$${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}}$

連続体仮説によれば、 はより大きい最小の基数であり、つまり、基数が整数の基数と実数の基数の中間に厳密に収まる集合は存在しない。連続体仮説は、集合論の標準的な公理化であるZFCとは独立している。つまり、ZFC が矛盾しない限り、連続体仮説またはその否定を ZFC から証明することは不可能である。詳細については、以下の § 連続体の基数 を参照。^{[13] [14] [15]}${\displaystyle \aleph _{1}=2^{\aleph _{0}}}$${\displaystyle 2^{\aleph _{0}}}$${\displaystyle \aleph _{0}}$

選択公理が成り立つ場合、基数に対して三分法の法則が成り立ちます。したがって、次の定義を行うことができます。

• 任意の集合X の濃度が自然数の濃度より小さい場合、つまり |  X  | < |  N | の場合、その集合は有限集合 であるといわれます。
• 自然数の集合と同じ濃度を持つ任意の 集合X 、つまり| X  | = |  N  | =は可算無限集合と呼ばれる。^[10]${\displaystyle \aleph _{0}}$
• 自然数の濃度よりも大きい濃度を持つ 集合X 、または | X  | > |  N  |、たとえば |  R  | = > |  N | は、無数 であると言われます。${\displaystyle {\mathfrak {c}}}$

有限集合から得られる我々の直観は、無限集合を扱う際には通用しない。19世紀後半、ゲオルク・カントール、ゴットロープ・フレーゲ、リヒャルト・デデキントらは、全体の大きさが部分の大きさと同じではあり得ないという見解を否定した。^{[16] [要出典]}その一例が、ヒルベルトのグランド・ホテルのパラドックスである。実際、デデキントは、無限集合を、厳密な部分集合と一対一に対応させることができる集合（つまり、カントールの意味で同じ大きさを持つ集合）と定義した。この無限の概念は、デデキント無限と呼ばれている。カントールは基数を導入し、彼の一対一に基づくサイズの定義によれば、いくつかの無限集合は他のものよりも大きいことを示した。最小の無限基数は、自然数（）の基数である。 ${\displaystyle \aleph _{0}}$

カントールの最も重要な結果の 1 つは、連続体の濃度( ) は自然数の濃度 ( ) よりも大きい、つまり実数Rのほうが自然数Nより多いということである。つまり、カントールは (ベス 1を参照) が次を満たすことを示しました。 ${\displaystyle {\mathfrak {c}}}$${\displaystyle \aleph _{0}}$${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}}$

${\displaystyle 2^{\aleph _{0}}>\aleph _{0}}$

(カントールの対角線議論またはカントールの最初の不可算性証明を参照)。

連続体仮説は、実数の基数と自然数の基数の間に基数は存在しない、つまり、

${\displaystyle 2^{\aleph _{0}}=\aleph _{1}}$

しかし、ZFC が矛盾しない場合、この仮説は広く受け入れられているZFC 公理集合論の範囲内で証明することも反証することもできません。

基数演算を使用すると、実数直線上の点の数がその直線の任意の線分の点の数に等しいだけでなく、平面上の点の数、さらには任意の有限次元空間内の点の数にも等しいことを示すことができます。これらの結果は、 S にはその部分集合に属さない要素が含まれ、 S の超集合にはそれに含まれない要素が含まれるにもかかわらず、 S と同じサイズの無限集合 S の真部分集合と真超集合が存在することを意味するため、非常に直感に反しています。

これらの結果のうち最初のものは、例えば、区間(−½π, ½π) とRの間に1 対 1 の対応を提供する正接関数を考えると明らかです (グランドホテルのヒルベルトのパラドックスも参照)。

2 番目の結果は、1878 年にカントールによって初めて実証されましたが、1890 年にジュゼッペ ペアノが空間充填曲線を導入したときにさらに明らかになりました。空間充填曲線とは、任意の正方形、立方体、超立方体、または有限次元空間全体を埋め尽くすほどにねじれた曲線のことです。これらの曲線は、直線が有限次元空間と同じ数の点を持つことを直接証明するものではありませんが、そのような証明を得るために使用できます。

カントールはまた、濃度が よりも確実に大きい集合が存在することも示しました (彼の一般化された対角線上の議論と定理を参照)。これには、たとえば次のものが含まれます。 ${\displaystyle {\mathfrak {c}}}$

• Rの部分集合全体の集合、すなわちRの冪集合。P ( R ) または 2 ^Rと表記される。
• RからRまでのすべての関数の集合R ^R

どちらも基数を持っている

${\displaystyle 2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}}$

（ベス2参照）。

基数等式 と基数算術を使用して証明できます。 ${\displaystyle {\mathfrak {c}}^{2}={\mathfrak {c}},}$ ${\displaystyle {\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}},}$${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}}$

${\displaystyle {\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},}$

${\displaystyle {\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}}.}$

• X = { a , b , c }、Y = {リンゴ、オレンジ、桃} （ a、b、cは異なる）の場合、| X  | = |  Y  | となります。これは 、{ ( a、リンゴ)、( b 、オレンジ)、( c、桃)} が集合XとYの間の一対一であるためです。XとYのそれぞれの濃度は3 です。
• |  X  | ≤ |  Y  | の場合、 | X  | = |  Z  |かつZ ⊆ Yとなる Zが存在します。
• |  X  | ≤ |  Y  | かつ |  Y  | ≤ |  X  | の場合、|  X  | = |  Y | です。これは無限基数に対しても成り立ち、カントール・ベルンシュタイン・シュレーダーの定理 として知られています。
• 連続体の濃度を持つ集合には、すべての実数の集合、すべての無理数の集合、および区間が含まれます。${\displaystyle [0,1]}$

AとBが互いに素な集合である場合、

${\displaystyle \left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .}$

このことから、一般に、和集合と 積集合の基数は、次の式で関係していることがわかります。 ^[17]

${\displaystyle \left\vert C\cup D\right\vert +\left\vert C\cap D\right\vert =\left\vert C\right\vert +\left\vert D\right\vert .}$

ここで はすべての集合のクラスを表し、 はすべての順序数のクラスを表します。 ${\displaystyle V}$${\displaystyle {\mbox{Ord}}}$

${\displaystyle |A|:={\mbox{Ord}}\cap \bigcap \{\alpha \in {\mbox{Ord}}|\exists (f:A\to \alpha ):(f{\mbox{ injective}})\}}$

によって定義されるクラスの共通部分を使用するので、この場合 ${\displaystyle (x\in \bigcap Q)\iff (\forall q\in Q:x\in q)}$${\displaystyle \bigcap \emptyset =V}$

${\displaystyle (x\mapsto |x|):V\to {\mbox{Ord}}}$。

この定義により、任意の適切なクラスの濃度も取得できます。特に ${\displaystyle P}$

${\displaystyle |P|={\mbox{Ord}}}$

この定義は、 と任意の適切なクラス 間の一対一関係を意味するサイズ制限の公理に一致するため自然です。${\displaystyle V}$

ウィキメディア・コモンズには、 Cardinalityに関連するメディアがあります。

Wikidata には次のプロパティがあります:

• グループ基数 (P1164) (使用法を参照)
• この集合の濃度 (P2820) (使用法を参照)

• アレフ数
• ベス番号
• カントールのパラドックス
• カントールの定理
• 可算集合
• カウント
• 順序性
• 鳩の巣原理