プリミティブ再帰集合関数

数学において、 原始再帰集合関数または 原始再帰順序関数は、自然数ではなく集合または順序数に対して定義された原始再帰関数の類似物です。これらは、Jensen と Karp (1971) によって導入されました。

原始再帰集合関数は、次の置換と再帰の規則を繰り返し適用することで、次の基本関数から取得できる集合から集合への 関数です。

基本的な機能は次のとおりです。

• 射影: P _{n , m} ( x ₁ , ...,  x _n ) = x _m ( 0 ≤  m  ≤  n )
• ゼロ: F ( x ) = 0
• 要素を集合に追加する: F ( x ,  y ) = x  ∪ { y }
• メンバーシップのテスト: u  ∈  vの場合はC ( x ,  y ,  u ,  v ) = x、それ以外の場合はC ( x ,  y ,  u ,  v ) = yです。

置換によって新しい関数を生成するための規則は

• F ( x ,  y ) = G ( x , H ( x ), y )
• F ( x ,  y ) = G ( H ( x ), y )

ここで、xとy は変数の有限シーケンスです。

再帰によって新しい関数を生成するための規則は

• F ( z ,  x ) = G (∪ _{u  ∈ z}  F ( u ,  x ), z , x )

原始再帰順序関数は、初期関数F ( x ,  y ) = x  ∪ { y } がF ( x ) = x  ∪ { x } ( xの後継) に置き換えられることを除いて、同じ方法で定義されます。原始再帰順序関数は、順序数を順序数にマッピングする原始再帰集合関数と同じです。

プリミティブ再帰集合関数の例:

• TC、集合に推移閉包を割り当てる関数。^{[1] : 26}
• 遺伝的に有限な定数 関数が与えられると、定数関数は次のように表される。^{[1] : 28}${\displaystyle c}$${\displaystyle f(x)=c}$

より多くの初期関数を追加して、より大きな関数のクラスを取得することもできます。たとえば、順序関数は原始再帰的ではありません。これは、値 ω (またはその他の無限セット) を持つ定数関数が原始再帰的ではないためです。そのため、この定数関数を初期関数に追加したい場合があります。 ${\displaystyle \alpha \mapsto \omega ^{\alpha }}$

ω における原始再帰的集合関数の概念は、原始再帰の定義と同じですが、ω はパラメータとして固定され、原始再帰スキーマによって変更されないという点が異なります。

ωにおける原始再帰関数の例: ^{[1] pp.28--29}

• ${\displaystyle \mathbb {P} _{\omega }(x)=\bigcup _{n<\omega }x^{n}}$。
• ゲーデルの構成可能階層の番目のレベルに割り当てる関数。${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle L_{\alpha}}$

を関数 とし、すべての、およびに対して が成り立つものとする。L _{α は}ゲーデルの構成可能宇宙の α 番目の段階を表すものとする。L _{α が}原始再帰集合関数に対して閉じている場合と、すべての に対してα が各 に対して閉じている場合とで同じである。^{[1] : 31}${\displaystyle f_{0}:{\textrm {Ord}}^{2}\to {\textrm {Ord}}}$${\displaystyle f(\alpha,\beta)=\alpha+\beta}$${\displaystyle i<\omega }$${\displaystyle {\tilde {f}}_{i}(\alpha )=f_{i}(\alpha ,\alpha )}$${\displaystyle f_{i+1}(\alpha ,\beta )=({\tilde {f}}_{i})^{\beta }(\alpha )}$${\displaystyle f_{i}}$${\displaystyle i<\omega }$

• ジェンセン、ロナルド B.; カープ、キャロル (1971)、「原始再帰集合関数」、公理的集合論、純粋数学シンポジウム、第 13 巻、第 1 部、プロビデンス、ロードアイランド州: アメリカ数学協会、pp. 143–176、ISBN 9780821802458、MR  0281602