Función de conjunto recursiva primitiva

En matemáticas , las funciones recursivas primitivas de conjuntos o las funciones recursivas primitivas de ordinales son análogas a 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 } (el sucesor de x ). Las funciones ordinales recursivas primitivas son iguales a las funciones de conjunto recursivas primitivas que asignan ordinales a otros ordinales.

Ejemplos de funciones de conjuntos recursivas primitivas:

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

También se pueden agregar más funciones iniciales para obtener una clase de funciones más amplia. Por ejemplo, la función ordinal.${\displaystyle \alpha \mapsto \omega ^{\alpha }}$no es recursivo primitivo, porque la función constante con valor ω (o cualquier otro conjunto infinito ) no es recursivo primitivo, por lo que uno podría querer agregar esta función constante a las funciones iniciales.

La noción de que una función de conjunto sea recursiva primitiva en ω tiene la misma definición que la de recursión primitiva, excepto que ω es un parámetro que se mantiene fijo, sin ser alterado 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 asigna a${\displaystyle \alpha }$el${\displaystyle \alpha }$nivel th${\displaystyle L_{\alpha }}$de la jerarquía constructible de Gödel .

Dejar${\displaystyle f_{0}:{\textrm {Ord}}^{2}\to {\textrm {Ord}}}$ser la función${\displaystyle f(\alpha ,\beta )=\alpha +\beta }$y para todos${\displaystyle i<\omega }$,${\displaystyle {\tilde {f}}_{i}(\alpha )=f_{i}(\alpha ,\alpha )}$y${\displaystyle f_{i+1}(\alpha ,\beta )=({\tilde {f}}_{i})^{\beta }(\alpha )}$. Sea L _α la α-ésima etapa del universo construible de Gödel . L _α es cerrado bajo funciones de conjuntos recursivos primitivos si y solo si α es cerrado bajo cada${\displaystyle f_{i}}$a pesar de${\displaystyle i<\omega }$. ^{[ 1 ] : 31}

• Jensen, Ronald B .; Karp, Carol (1971), "Funciones de conjuntos recursivas primitivas", Axiomatic Set Theory , Proc. Sympos. Pure Math., vol.  XIII, Part I, Providence, RI: Amer. Math. Soc., pp. 143–176 , ISBN  9780821802458, MR 0281602