Hidra de Buchholz

Juego de hidra en lógica matemática

En matemáticas , especialmente en lógica matemática , teoría de grafos y teoría de números , el juego de la hidra de Buchholz es un tipo de juego de la hidra , que es un juego para un solo jugador basado en la idea de cortar piezas de un árbol matemático . El juego de la hidra se puede utilizar para generar una función de rápido crecimiento , , que eventualmente domina todas las funciones recursivas que son demostrablemente totales en " ", y la terminación de todos los juegos de la hidra no es demostrablemente total en . ^[1] ${\displaystyle BH(n)}$ ${\displaystyle {\textrm {ID}}_{\nu }}$ ${\displaystyle {\textrm {(}}\Pi _{1}^{1}{\textrm {-CA)+BI}}}$

Normas

El juego se desarrolla en una hidra , un árbol finito, con raíces y conectado , con las siguientes propiedades: ${\displaystyle A}$

• La raíz de tiene una etiqueta especial, normalmente denotada . ${\displaystyle A}$ ${\displaystyle +}$
• Cualquier otro nodo de tiene una etiqueta . ${\displaystyle A}$ ${\displaystyle \nu \leq \omega }$
• Todos los nodos directamente encima de la raíz de tienen una etiqueta . ${\displaystyle A}$ ${\displaystyle 0}$

Si el jugador decide eliminar el nodo superior de , la hidra elegirá un , donde es un número de turno actual, y luego se transformará en una nueva hidra de la siguiente manera. Sea , representa el padre de , y sea , representa la parte de la hidra que queda después de que se haya eliminado. La definición de depende de la etiqueta de : ${\displaystyle \sigma }$ ${\displaystyle A}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle A(\sigma ,n)}$ ${\displaystyle \tau }$ ${\displaystyle \sigma }$ ${\displaystyle A^{-}}$ ${\displaystyle \sigma }$ ${\displaystyle A(\sigma ,n)}$ ${\displaystyle \sigma }$

• Si la etiqueta de es 0 y es la raíz de , entonces = . ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle A}$ ${\displaystyle A(\sigma ,n)}$ ${\displaystyle A^{-}}$
• Si la etiqueta de es 0 pero no es la raíz de , se crean copias de y de todos sus hijos, y se agregan las aristas entre ellos y el padre de . Este nuevo árbol es . ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle A(\sigma ,n)}$
• Si la etiqueta de es para algún , sea el primer nodo de abajo que tenga una etiqueta . Defina como el subárbol obtenido al comenzar con y reemplazar la etiqueta de con y con 0. se obtiene entonces tomando y reemplazando con . En este caso, el valor de no importa. ${\displaystyle \sigma }$ ${\displaystyle u}$ ${\displaystyle u\in \mathbb {N} }$ ${\displaystyle \varepsilon }$ ${\displaystyle \sigma }$ ${\displaystyle v<u}$ ${\displaystyle B}$ ${\displaystyle A_{\varepsilon }}$ ${\displaystyle \varepsilon }$ ${\displaystyle u-1}$ ${\displaystyle \sigma }$ ${\displaystyle A(\sigma ,n)}$ ${\displaystyle A}$ ${\displaystyle \sigma }$ ${\displaystyle B}$ ${\displaystyle n}$
• Si la etiqueta de es , se obtiene reemplazando la etiqueta de con . ${\displaystyle \sigma }$ ${\displaystyle \omega }$ ${\displaystyle A(\sigma ,n)}$ ${\displaystyle \sigma }$ ${\displaystyle n+1}$

Si es la cabeza más a la derecha de , se escribe . Una serie de movimientos se denomina estrategia. Una estrategia se denomina estrategia ganadora si, después de una cantidad finita de movimientos, la hidra se reduce a su raíz. Esto siempre termina, aunque la hidra pueda crecer muchísimo. ^[1] ${\displaystyle \sigma }$ ${\displaystyle A}$ ${\displaystyle A(n)}$

Teorema de la hidra

El artículo de Buchholz en 1987 mostró que la correspondencia canónica entre una hidra y un árbol infinitario bien fundado (o el término correspondiente en el sistema de notación  asociado a la función de Buchholz, que no pertenece necesariamente al sistema de notación ordinal ), preserva las secuencias fundamentales de elección de las hojas más a la derecha y la  operación en un árbol infinitario bien fundado o la  operación en el término correspondiente en . ^[1] ${\displaystyle T}$ ${\displaystyle OT\subset T}$ ${\displaystyle (n)}$ ${\displaystyle [n]}$ ${\displaystyle T}$

El teorema de la hidra para la hidra de Buchholz, que establece que no existen estrategias perdedoras para ninguna hidra, no se puede demostrar en . ^[2] ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$

BH(n)

Supongamos que un árbol consta de una sola rama con  nodos, etiquetados como . Llamemos a dicho árbol . No se puede demostrar  que para todos , existe  tal que  sea una estrategia ganadora. (La última expresión significa tomar el árbol , luego transformarlo con , luego , luego , etc. hasta .) ^[2] ${\displaystyle x}$ ${\displaystyle +,0,\omega ,...,\omega }$ ${\displaystyle R^{n}}$ ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle R_{x}(1)(2)(3)...(k)}$ ${\displaystyle R_{x}}$ ${\displaystyle n=1}$ ${\displaystyle n=2}$ ${\displaystyle n=3}$ ${\displaystyle n=k}$

Definir  como la más pequeña  tal que,  como se definió anteriormente, es una estrategia ganadora. Por el teorema de la hidra, esta función está bien definida, pero su totalidad no se puede demostrar en . Las hidras crecen extremadamente rápido, porque la cantidad de vueltas necesarias para matar es mayor que el número de Graham o incluso la cantidad de vueltas para matar a una hidra de Kirby-Paris; y tiene una hidra de Kirby-Paris completa como su rama. Para ser precisos, se cree que su tasa de crecimiento es comparable a  con respecto al sistema no especificado de secuencias fundamentales sin una prueba. Aquí,  denota la función de Buchholz, y es el ordinal de Takeuti-Feferman-Buchholz que mide la fuerza de . ${\displaystyle BH(x)}$ ${\displaystyle k}$ ${\displaystyle R_{x}(1)(2)(3)...(k)}$ ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$ ${\displaystyle R_{x}(1)(2)}$ ${\displaystyle R_{x}(1)(2)(3)(4)(5)(6)}$ ${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(x)}$ ${\displaystyle \psi _{0}}$ ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$

Los dos primeros valores de la función BH están virtualmente degenerados:  y . De manera similar a la función de árbol débil,  es muy grande, pero no tanto. ^{[ cita requerida ]} ${\displaystyle BH(1)=0}$ ${\displaystyle BH(2)=1}$ ${\displaystyle BH(3)}$

La hidra de Buchholz finalmente supera a TREE(n) y SCG(n) , ^{[ cita requerida ]} aunque es probable que sea más débil que el cargador, así como los números de los juegos de promesa finita.

Análisis

Es posible hacer una correspondencia biunívoca entre algunas hidras y ordinales . Para convertir un árbol o subárbol en un ordinal:

• Convierte inductivamente todos los hijos inmediatos del nodo en ordinales.
• Sume los ordinales de los hijos. Si no hubiera hijos, el resultado será 0.
• Si la etiqueta del nodo no es +, se aplica , donde es la etiqueta del nodo y es la función de Buchholz. ${\displaystyle \psi _{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \psi }$

La expresión ordinal resultante solo es útil si está en forma normal. Algunos ejemplos son:

Referencias

1. Buchholz, Wilfried (1987), "Un resultado de independencia para ", Anales de lógica pura y aplicada , 33 (2): 131–155, doi :10.1016/0168-0072(87)90078-9, MR  0874022 ${\displaystyle (\Pi _{1}^{1}{\text{-CA}})+{\text{BI}}}$
2. Hamano, Masahiro; Okada, Mitsuhiro (1997), "Una prueba de independencia directa del juego Hydra de Buchholz en árboles etiquetados finitos", Archive for Mathematical Logic , 37 (2): 67–89, doi :10.1007/s001530050084, MR  1620664

Lectura adicional

• Hamano, Masahiro; Okada, Mitsuhiro (1997), "Una relación entre la reducción de pruebas de Gentzen, el juego de la hidra de Kirby-Paris y el juego de la hidra de Buchholz", Mathematical Logic Quarterly , 43 (1): 103–120, doi :10.1002/malq.19970430113, MR  1429324
• Gordeev, Lev (diciembre de 2001), "Revisión de 'Una prueba de independencia directa del juego Hydra de Buchholz en árboles etiquetados finitos'", Boletín de lógica simbólica , 7 (4): 534–535, doi :10.2307/2687805, ISSN  1079-8986, JSTOR  2687805
• Kirby, Laurie; Paris, Jeff (1982), "Resultados de independencia accesibles para la aritmética de Peano" (PDF) , Bull. London Math. Soc. , 14 (4): 285–293, doi :10.1112/blms/14.4.285 , consultado el 3 de septiembre de 2021
• Ketonen, Jussi; Solovay, Robert (1981), "Funciones de Ramsey de rápido crecimiento", Annals of Mathematics , 113 (2): 267–314, doi :10.2307/2006985, ISSN  0003-486X, JSTOR  2006985 , consultado el 3 de septiembre de 2021
• Takeuti, Gaisi (2013), Teoría de la prueba (2.ª edición (reimpresión) ed.), Newburyport: Dover Publications, ISBN 978-0-486-32067-0, OCLC  1162507470

Enlaces externos

• "Hidras", el cofre del tesoro matemático de Agnijo , recuperado el 4 de septiembre de 2021

 Este artículo incorpora texto disponible bajo la licencia CC BY-SA 3.0.