可算集合

数学的な集合は、有限であるか、自然数の集合と一対一に対応させることができる場合、可算である。[ ^{a ]同様}に、集合から自然数への単射関数が存在する場合、集合は可算である。これは、集合の各要素が一意の自然数に対応付けられるか、要素が無限にあるため数え終わることはないかもしれないが、集合の要素を一度に 1 つずつ数えることができることを意味する。

より専門的な言い方をすれば、可算選択公理を仮定すると、集合の濃度（集合の要素数）が自然数の濃度を超えない場合、その集合は可算である。有限でない可算集合は可算無限であると言われ、例えばすべての自然数の集合がこれに該当する。${\displaystyle \mathbb {N} }$またはすべての有理数${\displaystyle \mathbb {Q} }$。

この概念はゲオルク・カントールに帰せられ、彼は非可算集合、つまり可算でない集合の存在を証明しました。例えば、実数の集合がそうです。${\displaystyle \mathbb {R} }$。

ここで定義されている「可算」と「可算無限」という用語は非常に一般的ですが、用語は普遍的ではありません。^{[ 1 ]}別のスタイルでは、ここで可算無限と呼ばれるものを「可算」と呼び、ここで可算と呼ばれるものを「せいぜい可算」と呼びます。^{[ 2 ] [ 3 ]}

列挙可能^{[ 4 ]}および列挙可能^{[ 5 ] [ 6 ]}という用語も使用でき、それぞれ可算および可算無限を指します。^{[ 7 ]}定義は様々であり、再帰的に列挙可能との違いに注意が必要です。^{[ 8 ]}

セット${\displaystyle S}$可算名詞となるのは、以下の場合です。

• その濃度${\displaystyle |S|}$以下$\displaystyle \aleph _{0}}$（アレフヌル）、自然数の集合の濃度${\displaystyle \mathbb {N} }$[ ^{9 ]​}
• から単射関数が存在する${\displaystyle S}$に${\displaystyle \mathbb {N} }$[ ^{10 ] [ 11 ]​}
• ${\displaystyle S}$空であるか、または全射関数が存在する${\displaystyle \mathbb {N} }$に${\displaystyle S}$[ ^{11 ]​}
• 間に全単射写像が存在する${\displaystyle S}$そして、${\displaystyle \mathbb {N} }$[ ^{12 ]​}
• ${\displaystyle S}$有限である（${\displaystyle |S|<\aleph _{0}}$）または可算無限。^{[ 5 ]}

これらの定義はすべて同義である。

セット${\displaystyle S}$可算無限であるとは、次の場合に限ります。

• その濃度${\displaystyle |S|}$まさに$\displaystyle \aleph _{0}}$[ ^{9 ]​}
• と の間には単射かつ全射（したがって全単射）な写像が存在する。${\displaystyle S}$そして${\displaystyle \mathbb {N} }$。
• ${\displaystyle S}$1対1の対応関係にある${\displaystyle \mathbb {N} }$[ ^{13 ]​}
• 要素${\displaystyle S}$無限の順序で並べることができる${\displaystyle a_{0},a_{1},a_{2},\ldots }$、 どこ${\displaystyle a_{i}}$は${\displaystyle a_{j}}$のために${\displaystyle i\neq j}$そしてすべての要素${\displaystyle S}$リストされています。^{[ 14 ] [ 15 ]}

集合が可算でない場合、つまりその濃度が厳密に次の値より大きい場合、その集合は非可算である。$\displaystyle \aleph _{0}}$^{[ 9 ]}つまり、${\displaystyle \mathbb {N} }$に${\displaystyle S}$しかし、${\displaystyle S}$に${\displaystyle \mathbb {N} }$選択公理が成り立たないモデルでは、比較不可能な集合も存在する可能性がある。${\displaystyle \mathbb {N} }$いわゆるデデキント有限無限集合。

1874年、カントールは最初の集合論の論文で、実数の集合は非可算集合であることを証明し、すべての無限集合が可算集合ではないことを示した。^{[ 16 ]} 1878年、彼は1対1対応を用いて濃度を定義し、比較した。^{[ 17 ]} 1883年、彼は自然数を無限順序数で拡張し、順序数の集合を用いて異なる無限濃度を持つ無限の集合を生成した。^{[ 18 ]}

集合とは要素の集まりであり、さまざまな方法で記述できます。1つの方法は、すべての要素を単純に列挙することです。たとえば、整数 3、4、5 からなる集合は次のように表すことができます。${\displaystyle \{3,4,5\}}$これは、列挙形式と呼ばれます。^{[ 19 ]}ただし、これは小さな集合にのみ有効です。大きな集合では、時間がかかり、エラーが発生しやすくなります。すべての要素を列挙する代わりに、書き手が読者が「...」が何を表しているかを簡単に推測できると考える場合、集合の開始要素と終了要素の間にある多くの要素を表すために省略記号（「...」）が使用されることがあります。たとえば、${\displaystyle \{1,2,3,\dots ,100\}}$はおそらく1 から 100 までの整数の集合を表します。しかし、この場合でも、集合の要素の数は有限であるため、すべての要素を列挙することは可能です。集合の要素に 1、2、…と番号を付けると、${\displaystyle n}$これにより、「サイズの集合」の通常の定義が得られます。${\displaystyle n}$「。

一部の集合は無限です。これらの集合は${\displaystyle n}$要素${\displaystyle n}$は指定可能な任意の整数です。（指定された整数の大きさは問いません。）${\displaystyle n}$例えば${\displaystyle n=10^{1000}}$無限集合は、${\displaystyle n}$要素。）例えば、自然数の集合は、で表すことができる。${\displaystyle \{0,1,2,3,4,5,\dots \}}$[ ^{a ]は}無限に多くの要素を持ち、その大きさを表すのに自然数を使うことはできません。集合を異なるクラスに分けるのは自然なことのように思えるかもしれません。要素が 1 つだけの集合をまとめ、要素が 2 つだけの集合をまとめ、…、最後にすべての無限集合をまとめて、それらを同じ大きさとみなします。この考え方は可算無限集合にはうまく機能し、ゲオルク・カントールの研究以前は一般的な仮定でした。例えば、奇数は無限に多く、偶数も無限に多く、整数全体も無限に多く存在します。すべての整数に対して異なる偶数が存在するように配置できるため、これらの集合はすべて同じ「大きさ」を持つと考えることができます。 $${\displaystyle \ldots \,-\!2\!\rightarrow \!-\!4,\,-\!1\!\rightarrow \!-\!2,\,0\!\rightarrow \!0,\,1\!\rightarrow \!2,\,2\!\rightarrow \!4\,\cdots }$$ あるいは、より一般的には、${\displaystyle n\rightarrow 2n}$（図を参照）。ここで行ったことは、整数と偶数を一対一対応（または全単射）で配置することです。これは、2つの集合間の写像であり、各集合の各要素が他方の集合の1つの要素に対応します。この数学的な「大きさ」、濃度の概念は、2つの集合が同じ大きさであるのは、それらの間に全単射が存在する場合のみであるということです。整数と一対一対応しているすべての集合を可算無限集合と呼び、濃度を持つと言います。$\displaystyle \aleph _{0}}$。

ゲオルク・カントールは、すべての無限集合が可算無限集合であるとは限らないことを示した。例えば、実数は自然数（非負整数）と1対1に対応させることはできない。

実数の集合は自然数の集合よりも濃度が大きく、非可算集合であると言われています。カントールの対角線論法は、背理法を用いて形式的な証明を提供します。この論法は、区間 (0,1) 内の実数の集合が可算集合であるという仮定から始まります。これが真であれば、その範囲のすべての実数を ( s ₁ ,s ₂ ,s ₃ , ... )という順序リストに並べることができ、各数は無限小数展開で表されます。この構造化されたリストは、論理的にその数列に存在しないことが保証されている特定の実数を構成する基礎となり、それによって可算性の最初の前提が無効になります。

この新しい実数を定義する際に矛盾が生じる。${\displaystyle x}$それぞれ${\displaystyle n}$第 10 桁目は、${\displaystyle n}$の 番目の桁${\displaystyle n}$リスト内の 番目の番号。各桁を確実にすることで${\displaystyle x_{n}}$等しくない$d_n$（循環小数との曖昧さを避けるため、0または9は使用しない）結果として得られる数値${\displaystyle x}$は、数列のすべての要素と少なくとも1桁の小数点以下で異なっています。${\displaystyle x}$が、想定される完全なリストに現れない 0 から 1 の間の実数である場合、自然数と実数の間には全単射は存在しないことになる。^{[ 20 ]}

定義により、集合${\displaystyle S}$は、の間に全単射が存在する場合に可算である。${\displaystyle S}$そして自然数の部分集合${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$例えば、対応関係を定義する $${\displaystyle a\leftrightarrow 1,\ b\leftrightarrow 2,\ c\leftrightarrow 3}$$ すべての要素が${\displaystyle S=\{a,b,c\}}$正確に1つの要素とペアになっている${\displaystyle \{1,2,3\}}$、またその逆も同様で、これは全単射を定義し、次のことを示しています。${\displaystyle S}$は可算集合である。同様に、すべての有限集合が可算集合であることを示すことができる。

無限集合の場合、集合は${\displaystyle S}$は、間に全単射が存在する場合に可算無限である。${\displaystyle S}$そしてすべての${\displaystyle \mathbb {N} }$例として、集合を考えてみましょう。${\displaystyle A=\{1,2,3,\dots \}}$、正の整数の集合、および${\displaystyle B=\{0,2,4,6,\dots \}}$偶数の集合。これらの集合が可算無限であることを示すには、自然数との全単射を示すことができます。これは、割り当てを使用して実現できます。${\displaystyle n\leftrightarrow n+1}$そして${\displaystyle n\leftrightarrow 2n}$、 となることによって $${\displaystyle {\begin{matrix}0\leftrightarrow 1,&1\leftrightarrow 2,&2\leftrightarrow 3,&3\leftrightarrow 4,&4\leftrightarrow 5,&\ldots \\[6pt]0\leftrightarrow 0,&1\leftrightarrow 2,&2\leftrightarrow 4,&3\leftrightarrow 6,&4\leftrightarrow 8,&\ldots \end{matrix}}}$$ 可算無限集合はすべて可算集合であり、可算無限集合はすべて可算無限集合である。さらに、自然数の任意の部分集合は可算集合であり、より一般的には、次のことが成り立つ。

自然数の順序 対の集合（ 2 つの自然数の集合のデカルト積、${\displaystyle \mathbb {N} \times \mathbb {N} }$図のような経路をたどればわかるように、 は可算無限である。

その結果得られるマッピングは、以下の手順で行われます。

$${\displaystyle 0\leftrightarrow (0,0),1\leftrightarrow (1,0),2\leftrightarrow (0,1),3\leftrightarrow (2,0),4\leftrightarrow (1,1),5\leftrightarrow (0,2),6\leftrightarrow (3,0),\ldots }$$ このマッピングは、そのようなすべての順序対を網羅しています。

この形式の三角形マッピングは再帰的に一般化され、${\displaystyle n}$-自然数のタプル、つまり、${\displaystyle (a_{1},a_{2},a_{3},\dots ,a_{n})}$どこ${\displaystyle a_{i}}$そして${\displaystyle n}$自然数であり、${\displaystyle n}$-タプルを自然数に変換します。たとえば、${\displaystyle (0,2,3)}$次のように書くことができます${\displaystyle ((0,2),3)}$。 それから${\displaystyle (0,2)}$5にマッピングされるので${\displaystyle ((0,2),3)}$地図${\displaystyle (5,3)}$、 それから${\displaystyle (5,3)}$39 にマッピングされます。別の 2 タプル、つまり次のようなペアなので、${\displaystyle (a,b)}$、異なる自然数にマッピングされるため、2 つの n タプル間の 1 つの要素の差は、n タプルが異なる自然数にマッピングされることを保証するのに十分です。したがって、集合からの挿入は、${\displaystyle n}$自然数の集合へのタプル${\displaystyle \mathbb {N} }$証明されている。${\displaystyle n}$-有限個の異なる集合の直積によって作られるタプルでは、​​各タプルの各要素は自然数に対応しているため、すべてのタプルは自然数で表すことができ、同じ論理を適用して定理を証明します。

すべての整数の集合${\displaystyle \mathbb {Z} }$そしてすべての有理数の集合${\displaystyle \mathbb {Q} }$直感的には、${\displaystyle \mathbb {N} }$しかし、見た目に騙されてはいけません。ペアが一般分数（形式の分数）の分子と分母として扱われる場合、${\displaystyle a/b}$どこ${\displaystyle a}$そして${\displaystyle b\neq 0}$が整数である場合、すべての正の分数に対して、それに対応する異なる自然数を考えることができます。この表現には自然数も含まれます。なぜなら、すべての自然数は${\displaystyle n}$も分数です${\displaystyle n/1}$したがって、正の有理数の数と正の整数の数はちょうど同じであると結論づけることができます。これは、以下に示すように、すべての有理数にも当てはまります。

同様に、代数的数の集合は可算である。^{[ 24 ] [ d ]}

複数のマッピングが役立つ場合もあります。${\displaystyle A}$可算として表示されるには、別の集合に1対1でマッピング（挿入）する必要があります。${\displaystyle B}$、 それから${\displaystyle A}$が可算であると証明されるのは、${\displaystyle B}$自然数の集合に1対1で対応付けられます。たとえば、正の有理数の集合は、自然数のペア（2タプル）の集合に簡単に1対1で対応付けられます。${\displaystyle p/q}$地図${\displaystyle (p,q)}$上記のように、自然数のペアの集合は自然数の集合に1対1で対応付けられる（実際には1対1対応または全単射である）ため、正の有理数の集合は可算であることが証明されます。

集合が数えきれないほど存在するという先見性を踏まえると、この最後の結果をさらに拡張できるかどうか疑問に思うかもしれない。答えは「イエス」でもあり「ノー」でもある。拡張することは可能だが、そのためには新たな公理を仮定する必要がある。

例えば、可算集合が与えられた場合${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$まず、各セットの各要素にタプルを割り当て、次に、上記で見た三角形列挙の変形を使用して各タプルにインデックスを割り当てます。 $${\displaystyle {\begin{array}{c|c|c }{\text{Index}}&{\text{Tuple}}&{\text{Element}}\\\hline 0&(0,0)&{\textbf {a}}_{0}\\1&(0,1)&{\textbf {a}}_{1}\\2&(1,0)&{\textbf {b}}_{0}\\3&(0,2)&{\textbf {a}}_{2}\\4&(1,1)&{\textbf {b}}_{1}\\5&(2,0)&{\textbf {c}}_{0}\\6&(0,3)&{\textbf {a}}_{3}\\7&(1,2)&{\textbf {b}}_{2}\\8&(2,1)&{\textbf {c}}_{1}\\9&(3,0)&{\textbf {d}}_{0}\\10&(0,4)&{\textbf {a}}_{4}\\\vdots &&\end{array}}}$$

すべての集合をインデックス付けするには、可算選択公理が必要です。${\displaystyle {\textbf {a}},{\textbf {b}},{\textbf {c}},\dots }$同時に。

この集合は、長さ1のシーケンス、長さ2のシーケンス、長さ3のシーケンスなど、それぞれが可算集合（有限デカルト積）であるシーケンスの和集合です。したがって、この集合は可算集合の可算和集合であり、前の定理により可算集合となります。

任意の有限部分集合の要素は、有限列に順序付けることができる。有限列は可算個しか存在しないため、有限部分集合も可算個しか存在しない。

これらは、可算集合を単射／全射関数として定義することから導かれる。^{[ g ]}

カントールの定理は、もし${\displaystyle A}$セットであり、${\displaystyle {\mathcal {P}}(A)}$は、その冪集合、すなわち、のすべての部分集合の集合です。${\displaystyle A}$ならば、からの全射関数は存在しない。${\displaystyle A}$に${\displaystyle {\mathcal {P}}(A)}$証明は「カントールの定理」という記事で示されています。これと上記の基本定理から、次のことが直接的に導かれます。

この結果の詳細については、カントールの対角線論法を参照してください。

実数の集合は非可算集合であり、^{[ h ]}であり、自然数の無限列の集合も同様です。

ZFC集合論の標準モデル（内部モデルを参照）となる集合が存在するならば、最小標準モデル（構成可能宇宙を参照）が存在する。レーヴェンハイム・スコレムの定理を用いると、この最小モデルが可算であることを示すことができる。このモデルにおいても「非可算性」の概念が意味を持ち、特にこのモデルMには次のような要素が含まれているという事実は、次のことを示している。

• Mの部分集合、したがって可算、
• しかし、 Mの観点からは不可算である。

集合論の初期には逆説的だと考えられていた。詳しくはスコレムのパラドックスを参照のこと。

最小標準モデルには、すべての代数的数とすべての実効的に計算可能な超越数、およびその他の多くの種類の数が含まれる。

可算集合は、例えば以下のような様々な方法で全順序付けすることができる。

• 整列順序（序数も参照）：
  • 自然数の通常の順序（0、1、2、3、4、5、…）
  • 整数は (0, 1, 2, 3, ...; −1, −2, −3, ...) の順です。
• その他（あまり良くない）：
  • 整数の通常の順序（…、−3、−2、−1、0、1、2、3、…）
  • 有理数の通常の順序（順序付きリストとして明示的に記述することはできません！）

ここで挙げた2つの整列順序の例では、どの部分集合にも最小元が存在します。一方、2つの非整列順序の例では、一部の部分集合には最小元が存在しません。これが、全順序が整列順序でもあるかどうかを判断する重要な定義です。

• アレフ番号
• 数える
• ヒルベルトのグランドホテルのパラドックス
• 数えられない集合

• アポストル、トム・M.（1969年6月）、『多変数微積分と線形代数とその応用』第2巻 （第2 版）、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-00007-5
• アベルスガード、キャロル（1990）、『高等数学の基礎』、スコット・フォーズマン・アンド・カンパニー、ISBN 0-673-38152-8
• Cantor、Georg (1878)、「Ein Beitrag zur Mannigfaltigkeitslehre」、Journal für die Reine und Angewandte Mathematik、1878 (84): 242–248、doi : 10.1515/crelle-1878-18788413、S2CID 123695365 
• フェレイロス、ホセ（2007）、『思考の迷宮：集合論の歴史と数学的思考におけるその役割』（第2版改訂 版）、ビルクハウザー、ISBN 978-3-7643-8349-7
• フレッチャー、ピーター、パティ、C.ウェイン（1988）、『高等数学の基礎』、ボストン：PWS-KENT Publishing Company、ISBN 0-87150-164-3
• Halmos、Paul R. (1960)、Naive Set Theory、D. Van Nostorm Company, Inc1974年、シュプリンガー・フェルラーク社（ニューヨーク）より復刻。ISBN 0-387-90092-6（シュプリンガー・フェルラーク版）。マルティーノ・ファイン・ブックスより2011年に復刻。ISBN 978-1-61427-131-4（ペーパーバック版）
• カムケ、エーリッヒ（1950）、『集合論』、ドーバー数学物理学シリーズ、ニューヨーク：ドーバー、ISBN 978-0486601410{{citation}}ISBN /日付の不一致（ヘルプ）
• ラング、セルジュ（1993）、『実解析と関数解析』、ベルリン、ニューヨーク：シュプリンガー・フェルラーク、ISBN 0-387-94001-4
• ルディン、ウォルター（1976）、『数学解析の原理』、ニューヨーク：マグロウヒル、ISBN 0-07-054235-X
• Tao, Terence (2016). 「無限集合」 .解析学 I.数学テキストと読本 第 37巻（第3 版）. シンガポール：Springer. pp. 181–210 . doi : 10.1007/978-981-10-1789-6_8 . ISBN  978-981-10-1789-6。