Función de conjunto recursiva primitiva

En matemáticas , las funciones recursivas primitivas de conjunto 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).

Definición

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} ${\displaystyle c}$ ${\displaystyle f(x)=c}$

Extensiones

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 asigna al nivel th de la jerarquía construible de Gödel . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$

Cierre recursivo primitivo

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 )}$ ${\displaystyle f_{i}}$ ${\displaystyle i<\omega }$

Referencias

• 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

En línea

1. RB Jensen, Manuscrito sobre la estructura fina, la teoría del modelo interno y el modelo central por debajo de un cardinal de Woodin (pp. 22--31). Consultado el 7 de diciembre de 2022