列挙

列挙とは、コレクション内のすべての項目の完全な順序付きリストです。この用語は、数学やコンピュータ サイエンスで、集合のすべての要素のリストを指すためによく使用されます。列挙の正確な要件 (たとえば、集合が有限である必要があるかどうか、リストに繰り返しを含めることができるかどうかなど) は、研究分野や特定の問題のコンテキストによって異なります。

いくつかの集合は自然な順序付け（正の整数の集合では 1、2、3、4、... など）によって列挙できますが、他の場合には（おそらくは任意の）順序付けを強制する必要があるかもしれません。列挙的組合せ論などの一部の文脈では、列挙という用語は、要素の明示的なリストの作成ではなく、集合に含まれる要素の数を決定することに重点を置いた、数えるという意味で使用されます。

組合せ論では、列挙とは数えること、つまり有限集合の要素の正確な数を決定することを意味します。有限集合は、通常、ある有限集合のすべての順列からなる集合の族など、無限族にグループ化されます。数学の多くの分野では、この意味での特別な種類のオブジェクトの列挙に関わるサブ領域が盛んに行われています。たとえば、パーティション列挙やグラフ列挙では、特定の条件を満たすパーティションまたはグラフを数えることが目的です。

集合論では、列挙の概念はより広い意味を持ち、列挙される集合が有限である必要はありません。

列挙が順序付きリストのコンテキストで使用される場合、インデックス セットに何らかの順序付け構造要件を課します。一般性を高めるために順序付けの要件をかなり緩くすることもできますが、最も自然で一般的な前提条件は、インデックス セットが整然とした順序になっていることです。この特徴付けによると、順序付き列挙は、整然としたドメインを持つ全射 (全射関係) として定義されます。この定義は、インデックス セット上の整然とした順序付けによって、部分列挙が与えられた場合に次の要素をリストする一意の方法が得られるという意味で自然です。

特に指定がない限り、列挙は自然数によって行われます。つまり、集合Sの列挙は、自然数または自然数の初期セグメント{1, ..., n }からSへの全単射関数です。 ${\displaystyle \mathbb {N} }$

集合は、列挙できる場合、つまり列挙が存在する場合、可算です。そうでない場合は、不可算です。たとえば、実数の集合は不可算です。

集合は、自然数の適切な初期セグメント{1, ..., n }によって列挙できる場合、有限であり、その場合、その濃度はnです。空集合は、自然数の空の初期セグメントによって列挙できるため、有限です。

用語可算集合は計算可能可算集合にもよく使用されますとは、アルゴリズムを使用して列挙関数を計算できる可算集合のことです。

有限集合と可算無限集合を区別することを避けるために、同等の別の定義を使用すると便利なことがよくあります。集合Sが可算であるためには、そこから自然数への入射関数が存在する必要があります。

• 自然数は関数f ( x ) = xによって列挙可能です。この場合、は単純に恒等関数です。${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$
• ${\displaystyle \mathbb {Z} }$では、整数の集合は、すべての自然数がちょうど 1 つの整数に対応するため、一対一で列挙可能 です。次の表は、この列挙の最初のいくつかの値を示しています。 $${\displaystyle f(x):={\frac {1-(-1)^{x}\,(2\,x+1)}{4}}}$$ ${\displaystyle f\colon \mathbb {N} _{0}\to \mathbb {Z} }$
• すべての（空でない）有限集合は列挙可能です。S をn > 0 の要素を持つ有限集合とし、 K = {1,2,..., n } とします。 S内の任意の要素s を選択し、f ( n ) = s を割り当てます。次に、S' = S  − { s } と設定します（ここで、 − は集合の差を表します）。任意の要素s'  ∈  S'を選択し、f ( n  − 1) = s'を割り当てます。このプロセスを、集合のすべての要素に自然数が割り当てられるまで続けます。次に、Sの列挙が得られます。${\displaystyle f:K\to S}$
• カントールの対角線論証とカントールの第一非可算性証明によって証明されているように、実数には可算な列挙がありません。

• 集合が可算である場合に限り、集合の列挙が（この意味で）存在します。
• 集合が列挙可能である場合、空集合または (正確な定義によって異なりますが) 1 つの要素を持つ集合などの退化したケースを除いて、異なる列挙の無限数が存在します。ただし、列挙が単射である必要があり、f ( n )が定義されている場合はすべてのm  <  nに対してf ( m ) が定義される必要があるという限定された形式の部分性のみを許可する場合、 N要素の有限集合には正確にN ! 個の列挙があります。
• 定義域を持つ集合Sの列挙e は、 のときのみ、s ≤ tによって定義される集合上に整列順序≤を誘導します。順序は基になる集合とほとんど関係がないかもしれませんが、集合の何らかの順序が必要な場合に役立ちます。${\displaystyle \mathbb {N} }$${\displaystyle \min e^{-1}(s)\leq \min e^{-1}(t)}$

集合論では、列挙関数の定義域が自然数の最初のセグメントであり、列挙関数の定義域が任意の順序数をとることができるという特徴付けよりも一般的な列挙の概念があります。この定義では、集合Sの列挙は、順序数 α からSへの任意の射影です。前述の列挙のより制限されたバージョンは、 α が有限順序数または最初の極限順序数 ω である特別なケースです。このより一般化されたバージョンは、前述の定義を超限列挙を含むように拡張します。

この定義によれば、最初の非可算順序数は の${\displaystyle \omega _{1}}$恒等関数によって列挙できるため、これら 2 つの概念は一致しません。より一般的には、この特徴付けによって任意の整列集合を列挙できるため、一般化されたリスト列挙とラベル付けし直すまで一致するというのが ZF の定理です。選択公理も仮定すると、すべての集合を列挙できるため、最も一般的な形式の列挙とラベル付けし直すまで一致します。 ${\displaystyle \omega _{1}}$

集合論者は任意の大きさの基数の無限集合を扱うため、このグループの数学者の間では、集合の列挙のデフォルトの定義は、そのすべての要素を正確にリストした任意の α シーケンスになる傾向があります。実際、集合論者の一般的な参考文献である Jech の本では、列挙はまさにこのように定義されています。したがって、曖昧さを避けるために、区別された可算列挙の対応するタイプの 1 つを示すために、有限に列挙可能または可算という用語を使用できます。

形式的には、集合Sの列挙の最も包括的な定義は、任意の添字集合IからSへの任意の全射である。この広い文脈では、すべての集合S はSからそれ自身への恒等関数によって自明に列挙できる。選択公理またはその変形のいずれかを仮定しない場合、 S は整列している必要はない。選択公理を仮定する場合でも、S は自然な整列している必要はない。

したがって、この一般的な定義は、「何個あるか」ではなく「何の順序か」に関心がある計数概念に適しています。実際には、列挙のこの広い意味は、異なる集合の相対的なサイズや濃度を比較するためによく使用されます。選択公理を使用せずにツェルメロ-フランケル集合論を扱う場合、列挙は単射（重複なし）でなければならないという追加の制限を課したい場合があります。この理論では、IからSへの全射の存在は、 SからIへの単射の存在を意味する必要はないためです。

計算可能性理論では、可算列挙を、（すべての自然数の集合）から列挙された集合への写像が計算可能でなければならないという追加の要件とともに考えることがよくあります。列挙される集合は、再帰的に列挙可能（または、より現代的な言葉で計算可能列挙可能）と呼ばれ、写像が計算可能であることの意味を形式化する際に再帰理論を使用することを指します。 ${\displaystyle \mathbb {N} }$

この意味で、自然数のサブセットは、それが計算可能関数の値域である場合に計算可能列挙可能となります。この文脈では、enumerable は計算可能列挙可能の意味で使用されます。ただし、ドメイン ω を持つ任意の関数によって列挙できる自然数のサブセットは無数にあり、計算可能関数は可算数しかないため、これらの定義は異なるクラスを特徴付けます。列挙はあっても計算可能列挙ではない集合の具体的な例としては、停止集合の補集合があります。

さらに、この特徴付けは、リストの順序が重要な場所を示しています。停止集合の計算可能な列挙は存在しますが、要素を昇順でリストする列挙は存在しません。もし存在する場合、停止集合は決定可能になりますが、これは明らかに誤りです。一般に、再帰的に列挙可能であることは、決定可能な集合であるよりも弱い条件です。

列挙の概念は、列挙アルゴリズムの文脈におけるさまざまなタスクに対する計算複雑性理論の観点からも研究されてきました。

• 序数
• 列挙的定義
• 順序

• ジェック、トーマス(2002)。集合論、第三千年紀版 (改訂・拡張版)。シュプリンガー。ISBN 3-540-44085-2。

• ウィクショナリーの列挙の辞書定義