Teorías de definiciones inductivas iteradas

En la teoría de conjuntos y la lógica , la jerarquía ID de Buchholz es una jerarquía de subsistemas de aritmética de primer orden . Los sistemas/teorías se conocen como "las teorías formales de definiciones inductivas iteradas ν veces". La ID _ν extiende PA mediante ν puntos fijos mínimos iterados de operadores monótonos. ${\displaystyle ID_{\nu }}$

Definición

Definición original

La teoría formal ID _ω (y ID _ν en general) es una extensión de la Aritmética de Peano , formulada en el lenguaje L _ID , por los siguientes axiomas: ^[1]

• ${\displaystyle \forall y\forall x({\mathfrak {M}}_{y}(P_{y}^{\mathfrak {M}},x)\rightarrow x\in P_{y}^{\mathfrak {M}})}$
• ${\displaystyle \forall y(\forall x({\mathfrak {M}}_{y}(F,x)\rightarrow F(x))\rightarrow \forall x(x\in P_{y}^{\mathfrak {M}}\rightarrow F(x)))}$para cada L _ID -fórmula F(x)
• ${\displaystyle \forall y\forall x_{0}\forall x_{1}(P_{<y}^{\mathfrak {M}}x_{0}x_{1}\leftrightarrow x_{0}<y\land x_{1}\in P_{x_{0}}^{\mathfrak {M}})}$

La teoría ID _ν con ν ≠ ω se define como:

• ${\displaystyle \forall y\forall x(Z_{y}(P_{y}^{\mathfrak {M}},x)\rightarrow x\in P_{y}^{\mathfrak {M}})}$
• ${\displaystyle \forall x({\mathfrak {M}}_{u}(F,x)\rightarrow F(x))\rightarrow \forall x(P_{u}^{\mathfrak {M}}x\rightarrow F(x))}$para cada L _ID -fórmula F(x) y cada u < ν
• ${\displaystyle \forall y\forall x_{0}\forall x_{1}(P_{<y}^{\mathfrak {M}}x_{0}x_{1}\leftrightarrow x_{0}<y\land x_{1}\in P_{x_{0}}^{\mathfrak {M}})}$

Explicación / definición alternativa

IDENTIFICACIÓN₁

Un conjunto se define inductivamente si, para algún operador monótono , , donde denota el punto fijo mínimo de . El lenguaje de ID ₁ , , se obtiene del de la teoría de números de primer orden, , mediante la adición de una constante de conjunto (o predicado) I _A para cada fórmula X-positiva A(X, x) en L _N [X] que solo contiene X (una nueva variable de conjunto) y x (una variable numérica) como variables libres. El término X-positiva significa que X solo ocurre positivamente en A (X nunca está a la izquierda de una implicación). Nos permitimos un poco de notación de teoría de conjuntos: ${\displaystyle I\subseteq \mathbb {N} }$ ${\displaystyle \Gamma :P(N)\rightarrow P(N)}$ ${\displaystyle LFP(\Gamma )=I}$ ${\displaystyle LFP(f)}$ ${\displaystyle f}$ ${\displaystyle L_{ID_{1}}}$ ${\displaystyle L_{\mathbb {N} }}$

• ${\displaystyle F(x)=\{x\in N\mid F(x)\}}$
• ${\displaystyle s\in F}$medio ${\displaystyle F(s)}$
• Para dos fórmulas y , significa . ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F\subseteq G}$ ${\displaystyle \forall xF(x)\rightarrow G(x)}$

Entonces, ID ₁ contiene los axiomas de la teoría de números de primer orden (PA) con el esquema de inducción extendido al nuevo lenguaje, así como estos axiomas:

• ${\displaystyle (ID_{1})^{1}:A(I_{A})\subseteq I_{A}}$
• ${\displaystyle (ID_{1})^{2}:A(F)\subseteq F\rightarrow I_{A}\subseteq F}$

Donde varía en todas las fórmulas. ${\displaystyle F(x)}$ ${\displaystyle L_{ID_{1}}}$

Nótese que expresa que  está cerrado bajo el operador de conjunto definible aritméticamente , mientras que  expresa que  es el menos cerrado (al menos entre los conjuntos definibles en ). ${\displaystyle (ID_{1})^{1}}$ ${\displaystyle I_{A}}$ ${\displaystyle \Gamma _{A}(S)=\{x\in \mathbb {N} \mid \mathbb {N} \models A(S,x)\}}$ ${\displaystyle (ID_{1})^{2}}$ ${\displaystyle I_{A}}$ ${\displaystyle L_{ID_{1}}}$

Por lo tanto,  se pretende que sea el punto menos prefijado y, por lo tanto, el punto menos fijo del operador . ${\displaystyle I_{A}}$ ${\displaystyle \Gamma _{A}}$

IDENTIFICACIÓN_no

Para definir el sistema de definiciones inductivas iteradas ν veces, donde ν es un ordinal, sea  un ordenamiento recursivo primitivo de tipo ν. Usamos letras griegas para denotar elementos del cuerpo de . El lenguaje de ID _ν , se obtiene de mediante la adición de una constante de predicado binario J _A para cada fórmula X-positiva que contenga como máximo las variables libres mostradas, donde X es nuevamente una variable unaria (conjunto), e Y es una nueva variable de predicado binario. Escribimos en lugar de , pensando en x como una variable distinguida en la última fórmula. ${\displaystyle \prec }$ ${\displaystyle \prec }$ ${\displaystyle L_{ID_{\nu }}}$ ${\displaystyle L_{\mathbb {N} }}$ ${\displaystyle L_{\mathbb {N} }[X,Y]}$ ${\displaystyle A(X,Y,\mu ,x)}$ ${\displaystyle x\in J_{A}^{\mu }}$ ${\displaystyle J_{A}(\mu ,x)}$

El ID del sistema _ν  ahora se obtiene del sistema de teoría de números de primer orden (PA) expandiendo el esquema de inducción al nuevo lenguaje y agregando el esquema que expresa la inducción transfinita junto con una  fórmula arbitraria  así como los axiomas: ${\displaystyle (TI_{\nu }):TI(\prec ,F)}$ ${\displaystyle \prec }$ ${\displaystyle L_{ID_{\nu }}}$ ${\displaystyle F}$

• ${\displaystyle (ID_{\nu })^{1}:\forall \mu \prec \nu ;A^{\mu }(J_{A}^{\mu })\subseteq J_{A}^{\mu }}$
• ${\displaystyle (ID_{\nu })^{2}:\forall \mu \prec \nu ;A^{\mu }(F)\subseteq F\rightarrow J_{A}^{\mu }\subseteq F}$

donde es una  fórmula  arbitraria . En  y  usamos la abreviatura  de la fórmula , donde  es la variable distinguida. Vemos que estos expresan que cada , para , es el punto menos fijo (entre los conjuntos definibles) para el operador . Observe cómo todos los conjuntos anteriores , para , se usan como parámetros. ${\displaystyle F(x)}$ ${\displaystyle L_{ID_{\nu }}}$ ${\displaystyle (ID_{\nu })^{1}}$ ${\displaystyle (ID_{\nu })^{2}}$ ${\displaystyle A^{\mu }(F)}$ ${\displaystyle A(F,(\lambda \gamma y;\gamma \prec \mu \land y\in J_{A}^{\gamma }),\mu ,x)}$ ${\displaystyle x}$ ${\displaystyle J_{A}^{\mu }}$ ${\displaystyle \mu \prec \nu }$ ${\displaystyle \Gamma _{A}^{\mu }(S)=\{n\in \mathbb {N} |(\mathbb {N} ,(J_{A}^{\gamma })_{\gamma \prec \mu }\}}$ ${\displaystyle J_{A}^{\gamma }}$ ${\displaystyle \gamma \prec \mu }$

Luego definimos . ${\textstyle ID_{\prec \nu }=\bigcup _{\xi \prec \nu }ID_{\xi }}$

Variantes

${\displaystyle {\widehat {\mathsf {ID}}}_{\nu }}$- es una versión debilitada de . En el sistema de , un conjunto se llama definido inductivamente si para algún operador monótono , es un punto fijo de , en lugar del punto menos fijo. Esta sutil diferencia hace que el sistema sea significativamente más débil: , mientras que . ${\displaystyle {\widehat {\mathsf {ID}}}_{\nu }}$ ${\displaystyle {\mathsf {ID}}_{\nu }}$ ${\displaystyle {\widehat {\mathsf {ID}}}_{\nu }}$ ${\displaystyle I\subseteq \mathbb {N} }$ ${\displaystyle \Gamma :P(N)\rightarrow P(N)}$ ${\displaystyle I}$ ${\displaystyle \Gamma }$ ${\displaystyle PTO({\widehat {\mathsf {ID}}}_{1})=\psi (\Omega ^{\varepsilon _{0}})}$ ${\displaystyle PTO({\mathsf {ID}}_{1})=\psi (\varepsilon _{\Omega +1})}$

${\displaystyle {\mathsf {ID}}_{\nu }\#}$se debilita aún más. En , no solo utiliza puntos fijos en lugar de puntos menos fijos, y tiene inducción solo para fórmulas positivas. Esta diferencia, una vez más sutil, hace que el sistema sea aún más débil: , mientras que . ${\displaystyle {\widehat {\mathsf {ID}}}_{\nu }}$ ${\displaystyle {\mathsf {ID}}_{\nu }\#}$ ${\displaystyle PTO({\mathsf {ID}}_{1}\#)=\psi (\Omega ^{\omega })}$ ${\displaystyle PTO({\widehat {\mathsf {ID}}}_{1})=\psi (\Omega ^{\varepsilon _{0}})}$

${\displaystyle {\mathsf {W-ID}}_{\nu }}$es la más débil de todas las variantes de , basada en tipos W. La cantidad de debilitamiento en comparación con las definiciones inductivas iteradas regulares es idéntica a la eliminación de la inducción de barras dado un cierto subsistema de aritmética de segundo orden . , mientras que . ${\displaystyle {\mathsf {ID}}_{\nu }}$ ${\displaystyle PTO({\mathsf {W-ID}}_{1})=\psi _{0}(\Omega \times \omega )}$ ${\displaystyle PTO({\mathsf {ID}}_{1})=\psi (\varepsilon _{\Omega +1})}$

${\displaystyle {\mathsf {U(ID}}_{\nu }{\mathsf {)}}}$es un fortalecimiento "desdoblado" de . No es exactamente un sistema aritmético de primer orden, pero captura lo que se puede obtener mediante razonamiento predicativo basado en definiciones inductivas generalizadas iteradas n-veces. La cantidad de aumento en la fuerza es idéntica al aumento de a : , mientras que . ${\displaystyle {\mathsf {ID}}_{\nu }}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \Gamma _{0}}$ ${\displaystyle PTO({\mathsf {ID}}_{1})=\psi (\varepsilon _{\Omega +1})}$ ${\displaystyle PTO({\mathsf {U(ID}}_{1}{\mathsf {)}})=\psi (\Gamma _{\Omega +1})}$

Resultados

• Sea ν > 0. Si a ∈ T ₀ no contiene ningún símbolo D _μ con ν < μ, entonces "a ∈ W ₀ " es demostrable en ID _ν .
• ID _ω está contenido en . ${\displaystyle \Pi _{1}^{1}-CA+BI}$
• Si una -oración es demostrable en ID _ν , entonces existe tal que . ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \forall x\exists y\varphi (x,y)(\varphi \in \Sigma _{1}^{0})}$ ${\displaystyle p\in N}$ ${\displaystyle \forall n\geq p\exists k<H_{D_{0}D_{\nu }^{n}0}(1)\varphi (n,k)}$
• Si la oración A es demostrable en ID _ν para todo ν < ω, entonces existe k ∈ N tal que . ${\displaystyle \vdash _{k}^{D_{\nu }^{k}0}A^{N}}$

Ordinales de prueba teórica

• El ordinal de prueba teórica de ID _{< ν} es igual a . ${\displaystyle \psi _{0}(\Omega _{\nu })}$
• El ordinal de prueba teórica de ID _ν es igual a . ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\nu }+1})=\psi _{0}(\Omega _{\nu +1})}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle {\widehat {ID}}_{<\omega }}$ ${\displaystyle \Gamma _{0}}$
• El ordinal de prueba teórica de for es igual a . ${\displaystyle {\widehat {ID}}_{\nu }}$ ${\displaystyle \nu <\omega }$ ${\displaystyle \varphi (\varphi (\nu ,0),0)}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle {\widehat {ID}}_{\varphi (\alpha ,\beta )}}$ ${\displaystyle \varphi (1,0,\varphi (\alpha +1,\beta -1))}$
• El ordinal de prueba teórica de for es igual a . ${\displaystyle {\widehat {ID}}_{<\varphi (0,\alpha )}}$ ${\displaystyle \alpha >1}$ ${\displaystyle \varphi (1,\alpha ,0)}$
• El ordinal de prueba teórica de for es igual a . ${\displaystyle {\widehat {ID}}_{<\nu }}$ ${\displaystyle \nu \geq \varepsilon _{0}}$ ${\displaystyle \varphi (1,\nu ,0)}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle ID_{\nu }\#}$ ${\displaystyle \varphi (\omega ^{\nu },0)}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle ID_{<\nu }\#}$ ${\displaystyle \varphi (0,\omega ^{\nu +1})}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle W{\textrm {-}}ID_{\varphi (\alpha ,\beta )}}$ ${\displaystyle \psi _{0}(\Omega _{\varphi (\alpha ,\beta )}\times \varphi (\alpha +1,\beta -1))}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle W{\textrm {-}}ID_{<\varphi (\alpha ,\beta )}}$ ${\displaystyle \psi _{0}(\varphi (\alpha +1,\beta -1)^{\Omega _{\varphi (\alpha ,\beta -1)}+1})}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle U(ID_{\nu })}$ ${\displaystyle \psi _{0}(\varphi (\nu ,0,\Omega +1))}$
• El ordinal demostrativo-teórico de es igual a . ${\displaystyle U(ID_{<\nu })}$ ${\displaystyle \psi _{0}(\Omega ^{\Omega +\varphi (\nu ,0,\Omega )})}$
• El ordinal de prueba teórica de ID ₁ (el ordinal de Bachmann-Howard ) es también el ordinal de prueba teórica de , , y . ${\displaystyle {\mathsf {KP}}}$ ${\displaystyle {\mathsf {KP\omega }}}$ ${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {ML_{1}V}}}$
• El ordinal de prueba teórica de W-ID _ω ( ) es también el ordinal de prueba teórica de . ${\displaystyle \psi _{0}(\Omega _{\omega }\varepsilon _{0})}$ ${\displaystyle {\mathsf {W-KPI}}}$
• El ordinal de prueba teórica de ID _ω (el ordinal de Takeuti-Feferman-Buchholz ) es también el ordinal de prueba teórica de , y . ${\displaystyle {\mathsf {KPI}}}$ ${\displaystyle \Pi _{1}^{1}-{\mathsf {CA}}+{\mathsf {BI}}}$ ${\displaystyle \Delta _{2}^{1}-{\mathsf {CA}}+{\mathsf {BI}}}$
• El ordinal de prueba teórica de ID _<ω^ω ( ) es también el ordinal de prueba teórica de . ${\displaystyle \psi _{0}(\Omega _{\omega ^{\omega }})}$ ${\displaystyle \Delta _{2}^{1}-{\mathsf {CR}}}$
• El ordinal de prueba teórica de ID _<ε0 ( ) es también el ordinal de prueba teórica de y . ${\displaystyle \psi _{0}(\Omega _{\varepsilon _{0}})}$ ${\displaystyle \Delta _{2}^{1}-{\mathsf {CA}}}$ ${\displaystyle \Sigma _{2}^{1}-{\mathsf {AC}}}$

Referencias

1. W. Buchholz, "Un resultado de independencia para ", Anales de lógica pura y aplicada vol. 33 (1987). ${\displaystyle (\Pi _{1}^{1}{\textrm {-CA}}){\textrm {+BI}}}$

• Un resultado de independencia para Π 1 1 − C A + B I {\displaystyle \Pi _{1}^{1}-CA+BI}
• Definiciones inductivas iteradas y subsistemas de análisis: estudios teóricos de prueba recientes
• Definiciones inductivas iteradas en nLab
• Lema para la teoría intuicionista de definiciones inductivas iteradas
• Definiciones inductivas iteradas y Σ 2 1 − A C {\displaystyle \Sigma _{2}^{1}-AC}
• Números y ordinales contables grandes en Agda
• Análisis ordinal en nLab