Función de conjunto recursiva primitiva

En matemáticas , las funciones recursivas primitivas de conjuntos o funciones recursivas primitivas ordinales son análogas de las funciones recursivas primitivas , definidas para conjuntos u ordinales en lugar de números naturales . Fueron introducidas por Jensen y Karp (1971).

Una función de conjunto recursiva primitiva es una función de conjuntos a conjuntos que se puede obtener a partir 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 ₁ , ...,  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 e y son secuencias finitas de variables.

La regla para generar nuevas funciones por recursión 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 conjunto recursivas primitivas que asignan ordinales a ordinales.

Ejemplos de funciones de conjunto recursivas primitivas:

• TC , la función que asigna a un conjunto su clausura transitiva. ^{[1] : 26}
• Dado hereditariamente finito , la función constante . ^{[1] : 28}${\estilo de visualización c}$${\displaystyle f(x)=c}$

También se pueden añadir 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 se podría querer añadir esta función constante a las funciones iniciales. ${\displaystyle \alpha \mapsto \omega ^{\alpha }}$

La noción de una función de conjunto que es recursiva primitiva en ω tiene la misma definición que la de recursión primitiva, excepto que ω es un parámetro que se mantiene fijo y no se altera por los esquemas de recursión primitiva.

Ejemplos de funciones recursivas primitivas en ω: ^{[1] pp.28--29}

• ${\displaystyle \mathbb {P} _{\omega }(x)=\bigcup _{n<\omega }x^{n}}$.
• La función que se asigna al nivel ésimo de la jerarquía construible de Gödel .${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\displaystyle L_{\alpha}}$

Sea la función , y para todos , y . Sea L _α la etapa α del universo construible de Gödel . L _α está cerrada bajo funciones de conjunto recursivas primitivas si y solo si α está cerrada bajo cada una para todos . ^{[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 )}$$estilo de visualización f_{i}}$${\displaystyle i<\omega}$

• Jensen, Ronald B.; Karp, Carol (1971), "Funciones de conjunto recursivas primitivas", Teoría de conjuntos axiomática , Proc. Sympos. Pure Math., vol. XIII, Parte I, Providence, RI: Amer. Math. Soc., págs. 143–176, ISBN 9780821802458, Sr.  0281602