遺伝的有限集合

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

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

再帰段階: もし ${\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 2\uparrow \uparrow n-1}$）であるから遺伝的有限集合はちょうど可算無限個ある。

同じことであるが、集合が遺伝的有限であることと、その推移閉包が有限であることは同値である。 ${\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}$ であることとは同値である。