En matemáticas , las funciones de conjuntos recursivas primitivas o las funciones ordinales recursivas primitivas son análogas a las funciones recursivas primitivas , definidas para conjuntos u ordinales en lugar de números naturales . Fueron introducidos por Jensen y Karp (1971) .
Definición
Una función de conjunto recursiva primitiva es una función de conjuntos a conjuntos que se puede obtener de las siguientes funciones básicas aplicando repetidamente las siguientes reglas de sustitución y recursión:
Las funciones básicas son:
- Proyección: P n , m ( x 1 , ..., x n ) = x m para 0 ≤ m ≤ n
- Cero: F ( x ) = 0
- Adjuntar un elemento a un conjunto : F ( x , y ) = x ∪ { y }
- Prueba de pertenencia : C ( x , y , u , v ) = x si u ∈ v , y C ( x , y , u , v ) = y en caso contrario.
Las reglas para generar nuevas funciones por sustitución son
- F ( x , y ) = G ( x , H ( x ), y )
- F ( x , y ) = G ( H ( x ), y )
donde x y y son secuencias finitas de variables.
La regla para generar nuevas funciones por recursividad es
- F ( z , x ) = G (∪ u ∈ z F ( u , x ), z , x )
Una función ordinal recursiva primitiva se define de la misma manera, excepto que la función inicial F ( x , y ) = x ∪ { y } se reemplaza por F ( x ) = x ∪ { x } (la sucesora de x ). Las funciones ordinales recursivas primitivas son las mismas que las funciones de conjuntos recursivas primitivas que asignan ordinales a ordinales.
También se pueden agregar más funciones iniciales para obtener una clase más grande de funciones. Por ejemplo, la función ordinal ω α no es recursiva primitiva, porque la función constante con valor ω (o cualquier otro conjunto infinito ) no es recursiva primitiva, por lo que uno podría querer agregar esta función constante a las funciones iniciales.