遺伝的に有限な集合

数学と集合論において、遺伝的有限集合は、その要素がすべて遺伝的有限集合である有限集合として定義されます。言い換えると、集合自体は有限であり、そのすべての要素は有限集合であり、空集合に至るまで再帰的に有限集合になります。

整基礎遺伝的有限集合の再帰的定義は次のとおりです。

基本ケース: 空集合は遺伝的に有限な集合です。

再帰規則:が遺伝的に有限である場合、 も有限です。${\displaystyle a_{1},\dots a_{k}}$${\displaystyle \{a_{1},\dots a_{k}\}}$

これら 2 つの規則を有限回数適用して構築できる集合のみが、遺伝的に有限です。

このクラスのセットは、セットを表すために必要な括弧のペアの数によって自然にランク付けされます。

• ${\displaystyle \{\}}$（つまり、ノイマン順序数「0」）${\displaystyle \emptyset}$
• ${\displaystyle \{\{\}\}}$（つまり、または、ノイマン順序数「1」）${\displaystyle \{\emptyset \}}$${\displaystyle \{0\}}$
• ${\displaystyle \{\{\{\}\}\}}$
• ${\displaystyle \{\{\{\{\}\}\}\}}$そしてまた（つまり、ノイマン序数「2」）、${\displaystyle \{\{\},\{\{\}\}\}}$${\displaystyle \{0,1\}}$
• ${\displaystyle \{\{\{\{\{\}\}\}\}\}}$、同様に、${\displaystyle \{\{\{\},\{\{\}\}\}\}}$${\displaystyle \{\{\},\{\{\{\}\}\}\}}$
• ...括弧で囲まれた集合。例えば。このような集合は6つある。${\displaystyle 6}$${\displaystyle \{\{\{\{\{\{\}\}\}\}\}\}}$
• ...括弧で囲まれた集合。例えば。このような集合は12個ある。${\displaystyle 7}$${\displaystyle \{\{\{\{\{\{\{\}\}\}\}\}\}\}}$
• ...括弧のペアで表される集合、例：または（つまり、ノイマン順序数「3」）${\displaystyle 8}$${\displaystyle \{\{\{\{\{\{\{\{\}\}\}\}\}\}\}\}}$${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}}$${\displaystyle \{0,1,2\}}$
• ...などなど

このように、括弧のペアを持つセットの数は^[1]です。${\displaystyle n}$

集合 はそのような遺伝的に有限な集合の例であり、前述のように空集合 もそうです。一方、集合または は遺伝的に有限ではない有限集合の例です。たとえば、 のとき、最初の は少なくとも 1 つの無限集合を要素として含んでいるため、遺伝的に有限ではありません。 ${\displaystyle \{\{\},\{\{\{\}\}\}\}}$${\displaystyle \{\}}$${\displaystyle \{7,{\mathbb {N} },\pi \}}$${\displaystyle \{3,\{{\mathbb {N} }\}\}}$${\displaystyle {\mathbb {N} }=\{0,1,2,\dots \}}$

すべての遺伝的有限集合のクラスは で表され、各メンバーの濃度が より小さいことを意味します。(同様に、遺伝的可算集合のクラスはで表されます。) は と全単射に対応しています。また、 で表すこともできます。これは、フォン・ノイマン宇宙の 番目のステージを表します。^{[2]したがって、ここでは}可算集合 です。 ${\displaystyle H_{\aleph _{0}}}$${\displaystyle \aleph_{0}}$${\displaystyle H_{\aleph _{1}}}$${\displaystyle H_{\aleph _{0}}}$${\displaystyle \aleph_{0}}$${\displaystyle V_{\omega}}$${\displaystyle \omega}$

1937年、ヴィルヘルム・アッカーマンは遺伝的有限集合を自然数として符号化する手法を導入した。^{[3] [4] [5]} これは、遺伝的有限集合を自然数にマッピングする関数によって定義され、次の再帰定義によって与えられる。 ${\displaystyle f\colon H_{\aleph _{0}}\to \omega }$

${\displaystyle \displaystyle f(a)=\sum _{b\in a}2^{f(b)}}$

たとえば、空集合にはメンバーが含まれないため、空の合計、つまり数値0にマッピングされます。一方、異なるメンバーを持つ集合はにマッピングされます。 ${\displaystyle \{\}}$${\displaystyle a,b,c,\dots }$${\displaystyle 2^{f(a)}+2^{f(b)}+2^{f(c)}+\ldots }$

逆は次のように表される。

${\displaystyle \displaystyle f^{-1}\colon \omega \to H_{\aleph _{0}}}$

${\displaystyle \displaystyle f^{-1}(i)=\{f^{-1}(j)\mid {\text{BIT}}(i,j)=1\}}$

ここで、BIT はBIT 述語を表します。

アッカーマン符号化は、自然数における有限集合論のモデルを構築するために使用できます。より正確には、(はの逆関係で、2 つの引数を入れ替えたもの) は、無限公理 のないツェルメロ-フランケル集合論ZF をモデル化します。ここで、各自然数は集合をモデル化し、関係は集合間の所属関係をモデル化します。 ${\displaystyle (\mathbb {N} ,{\text{BIT}}^{\top })}$${\displaystyle {\text{BIT}}^{\top}}$${\displaystyle {\text{ビット}}}$${\displaystyle {\text{ビット}}}$

クラスは、非自明な対称性を持たない（つまり、唯一の自己同型は恒等式である）根付き木のクラスと正確に対応していることがわかります。ルート頂点は最上位の括弧に対応し、各辺は、それ自体がルート頂点として機能できる要素（別のそのようなセット）につながります。このグラフの自己同型は存在せず、等しい枝が識別されるという事実に対応しています（たとえば、形状 の 2 つのサブグラフの順列を自明化するなど）。このグラフモデルにより、データ型として無限大を使用せずに ZF を実装できるため、表現型理論における集合論の解釈が可能になります。 ${\displaystyle H_{\aleph _{0}}}$${\displaystyle \{\dots \}}$${\displaystyle \{t,t,s\}=\{t,s\}}$${\displaystyle t}$

ZF にはグラフモデルが存在し、また、非整根拠理論などのツェルメロ集合論とは異なる集合論も存在します。このようなモデルは、より複雑なエッジ構造を持ちます。

グラフ理論では、頂点が遺伝的に有限な集合に対応し、辺が集合のメンバーシップに対応するグラフは、ラド グラフまたはランダム グラフと呼ばれます。

一般的な公理的集合論アプローチでは、空集合は最初のフォン・ノイマン順序数も表し、 と表記されます。すべての有限フォン・ノイマン順序数は遺伝的に有限であるため、自然数を表す集合のクラスも有限です。言い換えると、 には自然数の標準モデルの各要素が含まれるため、 を表現する集合論には必然的にそれらも含まれている必要があります。 ${\displaystyle \{\}}$${\displaystyle 0}$${\displaystyle H_{\aleph _{0}}}$${\displaystyle H_{\aleph _{0}}}$

ここで、ロビンソン算術は、外延性、空集合、および随伴によって公理が与えられるツェルメロ集合論Z ⁻の非常に小さな部分理論であるSTですでに解釈できることに注目してください。 のすべてには、これらの公理と、たとえば集合帰納法や置換を含む構成的な公理化があります。 ${\displaystyle H_{\aleph _{0}}}$

遺伝的有限集合の理論を公理的に特徴付けるために、無限公理の否定を追加することができます。理論は の他の公理を検証するため、無限公理はこれらの他の公理の結果ではないことが証明されます。 ${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {ZF}}}$

遺伝的有限集合は、フォン・ノイマン宇宙のサブクラスです。ここでは、すべての整基礎遺伝的有限集合のクラスは と表記されます。この文脈では、これも集合であることに注意してください。 ${\displaystyle V_{\omega}}$

の冪集合を で表し、空集合を で表すと、各整数 に対してを設定することで が得られます。したがって、 は次のように表すことができます 。${\displaystyle \wp (S)}$${\displaystyle S}$${\displaystyle V_{0}}$${\displaystyle V_{\omega}}$${\displaystyle V_{i+1}=\wp (V_{i})}$${\displaystyle i\geq 0}$${\displaystyle V_{\omega}}$

${\displaystyle \displaystyle V_{\omega }=\bigcup _{k=0}^{\infty }V_{k}}$

そしてそのすべての要素は有限です。

この定式化は、遺伝的に有限な集合は可算個しか存在しないことを再度示しています。 は任意の有限な に対して有限であり、その濃度はクヌースの上矢印表記法（2 の累乗の塔）で表され、可算個の有限集合の和集合は可算です。 ${\displaystyle V_{n}}$${\displaystyle n}$${\displaystyle 2\uparrow \uparrow (n-1)}$${\displaystyle n-1}$

同様に、集合が遺伝的に有限であるためには、その推移閉包が有限である必要があります。

• 構成的集合論
• 有限集合
• 遺伝性セット
• 遺伝的に可算な集合
• 世襲財産
• 根付いた木々