可算集合 – 定義

導入

数学では、その要素が整数によってインデックス付けされたシーケンス内で省略や繰り返しなくリストできる場合、セットは可算 (可算) または可算無限 (可算無限) と言われます。逆に、特定の無限集合には、無限の整数で完全にカバーするには「多すぎる」要素が含まれているため、「非可算集合」と呼ばれます。
可算集合の中には、有限集合が含まれる場合があります。有限集合の要素には、指定された値より小さい正の整数で番号を付けることができます。ただし、形容詞「可算」を無限集合に対してのみ予約することが非常に一般的になってきました。

ゲオルク カントールは、1874 年に発表された論文でこの概念を初めて使用し、集合論の誕生を告げました。しかし、可算数の重要性は、解析、測定理論、トポロジーなど、数学の多くの分野で明らかです。

定義

より正式には、集合E が自然整数の集合Nと等価であるとき、つまりE上にNの全単射が存在するとき、その集合Eは可算であると言われます。この定義は、特定の著者によって有限集合に拡張されることがあります。その著者は、可算集合を、自然数の部分集合を含む全単射の集合として定義します。ただし、この記事では、この拡張を「最も可算な集合」または「有限または可算集合」という表現で指定します。曖昧さの危険がある場合は、 Nに等価な集合は常に「無限可算集合」と指定できます。 ”。

逆に、非可算 (無限) 集合は、 Nと等価ではない無限集合です。カントールの対角論法により、実数の集合とNの部分の集合が可算ではないことだけでなく、他の「多くの」不可算無限の存在も示すことができます。

可算無限集合を含む集合は必然的に無限になります。つまり、自然整数の任意の有界集合と等価ではありません。集合論における十分な公理、特に選択公理を与えるとすぐに、すべての無限集合には可算無限集合が含まれるという意味で、可算無限が最小の無限であることが示されます。逆の場合は何の困難もありません。その後、無限集合を可算集合を含む集合として特徴付けることができます。

Nの基数、つまり可算集合の基数は、ℵ ₀ (アレフ ゼロ) と表されます。これは、選択公理が存在する場合のすべての無限基数を表すアレフの順序列の最初のものです。

可算集合の例

N の部分集合

自然数の集合Nはもちろん定義上可算ですが、後で説明するように、その無限の部分集合もそれぞれ可算です。いくつかの特殊なケースについて説明します。 N が厳密な部分にマッピングされる可能性があるという観察は、古代以来何度か行われてきました。たとえば、ガリレオは自然数と「同じ数の」完全平方が存在するという発言でよく引用されます。同様に、明示的な列挙によって以下を取得します。

• 非ゼロの自然整数の集合N ^{∗ は}可算であり、以下にリストされています ( n +1)。
• 偶数の自然数の集合は、その後にリストされるため (2 n ) 可算です。

素数の場合、漸化式による定義を使用できます。

• 素数のセットは可算です。次のようにして、素数を列挙するシーケンス ( p _n ) を帰納法によって定義します。

ｐ０ _＝ ２；

p _{n +1 は、}厳密にp _nより大きい最小の素数です。

素数の集合が無限であることを示すEuclidの実証は、 p _{n +1}が明確に定義されていることも保証します。なぜなら、厳密にp _nよりも大きい素数の集合は必ず空ではないからです (出現には、 p ₀ 、 p ₁ … p _n +1 の素約数)。

後者の場合に使用される方法は、自然数の無限の部分集合に適応するのに十分一般的です。

N の「スーパーセット」

NまたはNの明らかなコピーを厳密な部分として持つ特定の集合が可算であることを示します。

相対整数。

相対整数の集合Zは可算です。実際、シーケンス ((-1) ⁿ ⌈ n /2⌉) (⌈ n /2⌉ はn /2 以上の最小の整数を示します) は、自然整数から相対整数への全単射を確立します。偶数のインデックスは自然整数を表し、奇数のインデックスはゼロ以外の負の整数を表します。

自然数のペア

カントール結合関数は、 N × NからNへの全単射を確立します。

自然整数のペアの集合N × Nは可算であり、添付の図に示すように、対角ごとに自然整数のペアを列挙できます。これに従うことで、すべてのペアを全単射的に列挙する一連のペアを再帰的に簡単に定義できます。自然数。この関数の逆数、つまりfは、結合関数と呼ばれるN × NのNへの全単射であり、次数2 の多項式です。

合理的

Neil Calkin と Herbert Wilf によるStern-Brocot 木の変形では、正またはゼロの有理数、より正確には自然整数の既約分数による表現を計算するための単純な全単射が得られます。既約分数a / b a for leftson a / ( a + b ) および右息子の場合は ( a + b )/ b ;これらの分数は既約です。整数の既約分数は、ツリー内に 1 回だけ出現します (元の Euclid減算アルゴリズムを参照)。ルート 0/1 からノードa / bまでのパスは、全単射によるa / bの整数イメージのバイナリ表現を与えます。逆全単射は帰納法によって定義できます。

$$ {{\ \ }^{x_0=0,\ x_{n+1}={1\over \lfloor x_n\rfloor + 1 -\{x_n\}}}} $$

ここで、⌊ x _n ⌋ はx _nの整数部分であり、 x _n =⌊ x _n ⌋ + {x _n }です。

有理数の集合Qは可算です。実際、有理数は分数、つまり相対整数とゼロ以外の自然整数で構成されるペアで表されます。以前に確立された全単射を正しく構成することにより、 NのZ × N ^∗への全単射が得られます。分数による有理数の表現は一意ではありませんが、 Qが無限であることがわかっているので、 QにおけるNの全単射の帰納によって簡単に定義を推測できます (列挙の最初の対の商をnのイメージとして取得します) Z × N ^∗の有理数はまだ列挙されていません)。これはカントール・バーンスタインの定理の結果でもありますが、この特定のケースでは簡単に証明できます。

その他の例

最初の 2 つの例、 Zの可算性、特にN × Nの可算性は、可算性の実証にかなり一般的な引数を使用します。 Zの場合は一定サイズの、連続するブロックで考慮される集合の要素を列挙します (要素は 2 つ)。同じ絶対値の、 N × N の場合にサイズが増加する、つまり対角、つまり同じ和のペア。また、完成した各ブロックを並べて並べる統一した方法もあります。

• たとえば、有限アルファベット上の単語の集合、つまり有限集合の要素の有限シーケンス (任意の長さ) は可算です。最初にストップワード、次にサイズ 1 のワード、次にサイズ 2 のワードというように、固定サイズのワードのブロックとしてリストされます。各ブロックは、開始アルファベットの任意の順序から辞書編集的に並べることができます。
• 同様に、整数の有限シーケンスのセット (これは可算アルファベットから単語を取得することに相当します) は可算です。ブロックとして、 n以下の整数のうちのn以下の長さのシーケンスを使用できます。ここで、シーケンスの長さが厳密にn-1より小さい場合、 n は必ず出現します。各ブロックは辞書順に並べられています。
• 自然な整数係数を持つ多項式のセットは、これらの係数の (有限) シーケンスのセットとして見ることができます。これらはすべて、最後の項が非ゼロである整数の有限シーケンスです。前のケースと厳密に同様に、このセットは可算です。相対整数Zのセットは可算であるため、合成により、相対整数係数を持つ多項式のセットも可算であると推定されます。

• したがって、代数的数 (実数または複素数) のセットも可算です。整数の係数を持つ多項式を列挙でき、これらの多項式のそれぞれが有限数の根を持っているため、次のことだけを考慮して、多項式ごとに代数的数を列挙できます。列挙にまだ現れていない多項式の根。実数の集合も複素数の集合も可算ではないため、超越的な (実数または複素数) 数の存在を推定します。

これらの最後の例には、後で説明する一般定理を使用することもできます。