遺伝的有限集合

数学および集合論において遺伝的有限集合（いでんてきゆうげんしゅうごう、英: hereditarily finite set）は有限個の遺伝的有限集合からなる有限集合と定義される。この定義は帰納的である。遺伝的という名称は遺伝的有限という性質がその元に遺伝することによる。

形式的な定義

整礎的な遺伝的有限集合の帰納的定義は次のようにされる：

基底段階: 空集合は遺伝的有限である。

再帰段階: もし ${\displaystyle a_{1},\ldots ,a_{k}}$ が遺伝的有限ならば ${\displaystyle \{a_{1},\ldots ,a_{k}\}}$ もそうである。

以上によって遺伝的有限集合とわかるものだけが遺伝的有限集合である。

全ての整礎的な遺伝的有限集合からなる集合を ${\displaystyle V_{\omega }}$ と書く。いま ${\displaystyle {\mathcal {P}}(S)}$ で ${\displaystyle S}$ の冪集合を表すことにすれば、 ${\displaystyle V_{\omega }}$ は空集合から始めて次のように再帰的に定義できる：

${\displaystyle V_{0}=\varnothing }$

${\displaystyle V_{n+1}={\mathcal {P}}(V_{n})}$

${\displaystyle V_{\omega }=\bigcup _{n<\omega }V_{n}}$

議論

遺伝的有限集合のクラスはフォン・ノイマン宇宙の部分クラスである。これはツェルメロ=フレンケル集合論において無限公理をその否定に置き換えた理論のモデルを成す。したがって無限公理はその他の公理からは証明できない。

${\displaystyle V_{n}}$ の濃度は ${\displaystyle ^{n-1}2}$（テトレーションを見よ）であるから遺伝的有限集合はちょうど可算無限個ある。

同じことであるが、集合が遺伝的有限であることと、その推移閉包が有限であることは同値である。 ${\displaystyle V_{\omega }}$ は ${\displaystyle H_{\aleph _{0}}}$ とも書かれる。その意味するところは遺伝的に濃度が ${\displaystyle \aleph _{0}}$ 未満ということである。

アッカーマンの全単射

Ackermann (1937)は次のような自然な全単射 ${\displaystyle f:\mathbb {N} \to V_{\omega }}$ を与えている。これはアッカーマン符号化として知られる。これは遺伝的集合の階数に関する帰納法によって

${\displaystyle f(2^{a}+2^{b}+\cdots )=\{f(a),f(b),\ldots \}}$

と定義される。ただし ${\displaystyle a,b,\ldots }$ は相異なるものとする。このとき ${\displaystyle f(m)\in f(n)}$ であることと、 ${\displaystyle n}$ の2進展開の第 ${\displaystyle m}$ 位が ${\displaystyle 1}$ であることとは同値である。

ラドーグラフ

遺伝的有限集合を頂点とするグラフであって、一方が他方を含むときに限り、それらの頂点を辺で結んで得られるグラフをラドーグラフあるいはランダムグラフという。

関連項目

• 遺伝的可算集合

参考文献

• Ackermann, Wilhelm (1937), “Die Widerspruchsfreiheit der allgemeinen Mengenlehre”, Mathematische Annalen 114 (1): 305-315, doi:10.1007/BF01594179