可算集合

数学では、集合が可算であるとは、それが有限であるか、自然数の集合と一対一に対応付けられるかのいずれかである。^[a]同様に、集合が可算であるとは、その集合から自然数への入射関数が存在する場合である。つまり、集合内の各要素が一意の自然数に関連付けられるか、集合の要素が一度に 1 つずつ数えられるが、要素の数が無限であるため数え上げが終わらない場合があることを意味する。

より技術的な言葉で言えば、可算選択公理を前提とすると、集合の濃度（集合の要素の数）が自然数の濃度より大きくない場合、その集合は可算です。有限でない可算集合は可算無限であると言われます。

この概念は、無数集合、つまり数えられない集合（例えば実数の集合）の存在を証明したゲオルク・カントールに帰せられます。

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

可算^[4]および可算^{[5] [6]}という用語も使用されることがあります。たとえば、それぞれ可算および可算無限を指しますが^{[7] 、定義はさまざまであり、}再帰的に可算との違いに注意する必要があります。^[8]

集合が可算であるのは、次の場合です。 ${\displaystyle S}$

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

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

集合が可算無限であるとは、次の場合です。 ${\displaystyle S}$

• その濃度はちょうど である。^[9]${\displaystyle |S|}$${\displaystyle \aleph_{0}}$
• と の間には、単射かつ全射の（したがって全単射の）マッピングが存在します。${\displaystyle S}$${\displaystyle \mathbb {N} }$
• ${\displaystyle S}$はと一対一に対応している。^[13]${\displaystyle \mathbb {N} }$
• の要素は無限列 に並べることができる。ここで はに対してとは区別され、 のすべての要素がリストされる。^{[14] [15]}${\displaystyle S}$${\displaystyle a_{0},a_{1},a_{2},\ldots }$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle i\neq j}$${\displaystyle S}$

集合が可算でない、つまりその濃度がより大きい場合、その集合は不可算である。^[9]${\displaystyle \aleph_{0}}$

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

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

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

ゲオルク・カントールは、すべての無限集合が可算無限であるとは限らないことを示しました。たとえば、実数は自然数 (負でない整数) と 1 対 1 で対応させることはできません。実数の集合は自然数の集合よりも濃度が高く、可算ではないと言われています。

定義により、集合が可算であるとは、 と自然数の部分集合の間に一対一の関係が存在する場合です。たとえば、 の対応を定義します。 のすべての要素はの1 つの要素と正確に対になっており、その逆も同様であるため、これは一対一の関係を定義し、 が可算であることを示します。同様に、すべての有限集合が可算であることを示すことができます。 ${\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\}}$${\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 }$$ このマッピングは、そのような順序付けられたペアをすべてカバーします。

この形式の三角マッピングは、自然数の-組、つまり、とが自然数である場合に、 - 組の最初の 2 つの要素を自然数に繰り返しマッピングすることによって再帰的に一般化されます。たとえば、は と書くことができます。次に5 にマッピングされるため にマッピングされ、次に39 にマッピングされます。 などの異なる 2 組は異なる自然数にマッピングされるため、2 つの n 組の要素が 1 つ異なるだけで、n 組が異なる自然数にマッピングされることが保証されます。したがって、 - 組の集合から自然数の集合への単射が証明されます。有限個の異なる集合の直積によって作成される - 組の集合では、各組の各要素が自然数に対応しているため、すべての組を自然数で記述でき、同じロジックを適用して定理を証明できます。 ${\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)}$${\displaystyle ((0,2),3)}$${\displaystyle (5,3)}$${\displaystyle (5,3)}$${\displaystyle (a,b)}$${\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}$

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

複数のマッピングが役に立つ場合もあります。可算として示される集合 が別の集合 に 1 対 1 でマッピング (単射) されている場合、 が自然数の集合 に 1 対 1 でマッピングされると、 は可算であることが証明されます。たとえば、は にマッピングされるため、正の有理数の集合は自然数のペア (2 組) の集合 に簡単に 1 対 1 でマッピングできます。上記のように、自然数のペアの集合は自然数の集合 に 1 対 1 でマッピング (実際には 1 対 1 対応または単射) されるため、正の有理数の集合は可算であることが証明されます。 ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle p/q}$${\displaystyle (p,q)}$

数え切れないほど多くの集合が存在するという先見の明があれば、この最後の結果をさらに推し進めることができるかどうか疑問に思うことができます。答えは「はい」と「いいえ」です。これを拡張することはできますが、そのためには新しい公理を想定する必要があります。

たとえば、可算集合が与えられた場合、まず各集合の各要素にタプルを割り当て、次に上で見た三角列挙の変形を使用して各タプルにインデックスを割り当てます。 ${\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、...)
  • 有理数の通常の順序 (順序付きリストとして明示的に記述することはできません!)

ここでの整列順序の両方の例では、どの部分集合にも最小元があります。また、非整列順序の両方の例では、一部の部分集合には最小元がありません。これが、全順序も整列順序であるかどうかを決定する重要な定義です。

• アレフ数
• カウント
• グランドホテルのヒルベルトのパラドックス
• 不可算集合

• アポストル、トム・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 出版、ISBN 0-87150-164-3
• Halmos、Paul R. (1960)、Naive Set Theory、D. Van Nostorm Company, IncSpringer-Verlag、ニューヨーク、1974年に再版。ISBN 0-387-90092-6（Springer-Verlag版）。Martino Fine Books、2011年に再版。ISBN 978-1-61427-131-4 （ペーパーバック版）。  
• カムケ、エーリッヒ（1950）、集合論、数学と物理学のドーバーシリーズ、ニューヨーク：ドーバー、ISBN 978-0486601410
• ラング、セルジュ（1993）、実数と関数解析、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 0-387-94001-4
• ルディン、ウォルター（1976）、数学解析の原理、ニューヨーク：マグロウヒル、ISBN 0-07-054235-X
• タオ、テレンス (2016)。 「無限集合」。解析学 I。数学テキストと読書。第 37 巻 (第 3 版)。シンガポール: シュプリンガー。pp.  181– 210。doi :10.1007 / 978-981-10-1789-6_8。ISBN 978-981-10-1789-6。

無料辞書のウィクショナリーで「countable」を調べてください。