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]
Normas
El juego se desarrolla en una hidra , un árbol finito, con raíces y conectado , con las siguientes propiedades:
- La raíz de tiene una etiqueta especial, normalmente denotada .
- Cualquier otro nodo de tiene una etiqueta .
- Todos los nodos directamente encima de la raíz de tienen una etiqueta .
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 :
- Si la etiqueta de es 0 y es la raíz de , entonces = .
- 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 .
- 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.
- Si la etiqueta de es , se obtiene reemplazando la etiqueta de con .
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]
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]
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]
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]
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 .
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 ]
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.
La expresión ordinal resultante solo es útil si está en forma normal. Algunos ejemplos son:
Referencias
- ^ abc 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
- ^ ab 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.