Fonction d'ensemble récursive primitive - Primitive recursive set function

En mathématiques , les fonctions d'ensemble récursives primitives ou les fonctions ordinales récursives primitives sont des analogues des fonctions récursives primitives , définies pour des ensembles ou des ordinaux plutôt que des nombres naturels . Ils ont été introduits par Jensen & Karp (1971) .

Définition

Une fonction d'ensemble récursive primitive est une fonction d'ensembles à ensembles qui peut être obtenue à partir des fonctions de base suivantes en appliquant à plusieurs reprises les règles de substitution et de récursivité suivantes:

Les fonctions de base sont:

  • Projection: P n , m  ( x 1 , ...,  x n ) = x m pour 0 ≤  m  ≤  n
  • Zéro: F ( x ) = 0
  • Joindre un élément à un ensemble : F ( x ,  y ) = x  ∪ { y }
  • Test de l' appartenance : C ( x ,  y ,  u ,  v ) = x si u  ∈  v , et C ( x ,  y ,  u ,  v ) = y sinon.

Les règles de génération de nouvelles fonctions par substitution sont

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

où x et y sont des séquences finies de variables.

La règle pour générer de nouvelles fonctions par récursivité est

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

Une fonction ordinale récursive primitive est définie de la même manière, sauf que la fonction initiale F ( x ,  y ) = x  ∪ { y } est remplacée par F ( x ) = x  ∪ { x } (le successeur de x ). Les fonctions ordinales récursives primitives sont les mêmes que les fonctions d'ensemble récursives primitives qui mappent les ordinaux aux ordinaux.

On peut également ajouter plus de fonctions initiales pour obtenir une plus grande classe de fonctions. Par exemple, la fonction ordinale ω α n'est pas récursive primitive, car la fonction constante de valeur ω (ou tout autre ensemble infini ) n'est pas récursive primitive, on pourrait donc vouloir ajouter cette fonction constante aux fonctions initiales.

Les références

  • Jensen, Ronald B .; Karp, Carol (1971), "Fonctions d'ensemble récursives primitives", Théorie des ensembles axiomatiques , Proc. Sympos. Mathématiques pures., XIII, Partie I, Providence, RI: Amer. Math. Soc., Pp. 143-176, ISBN 9780821802458, MR  0281602