El lema de Kőnig o el lema del infinito de Kőnig es un teorema en la teoría de grafos debido al matemático húngaro Dénes Kőnig, quien lo publicó en 1927. [1] Da una condición suficiente para que un grafo infinito tenga una trayectoria infinitamente larga. Los aspectos de computabilidad de este teorema han sido investigados a fondo por investigadores en lógica matemática , especialmente en teoría de computabilidad . Este teorema también tiene un papel importante en las matemáticas constructivas y la teoría de la prueba .
Declaración del lema
Deje que G sea una conectada , localmente finito , gráfico infinito (esto significa: dos vértices pueden estar conectados por un camino, el gráfico tiene infinitamente muchos vértices, y cada vértice es adyacente a solamente un número finito de otros vértices). Entonces G contiene un rayo : un camino simple (un camino sin vértices repetidos) que comienza en un vértice y continúa desde él a través de un número infinito de vértices.
Un caso especial común de esto es que cada árbol infinito contiene un vértice de grado infinito o un camino simple infinito.
Prueba
Comience con cualquier vértice v 1 . Cada uno de los infinitos vértices de G se puede alcanzar desde v 1 con una ruta simple, y cada una de esas rutas debe comenzar con uno de los numerosos vértices adyacentes a v 1 . Debe haber uno de esos vértices adyacentes a través del cual se pueden alcanzar infinitos vértices sin pasar por v 1 . Si no lo hubiera, entonces todo el gráfico sería la unión de un número finito de conjuntos finitos y, por lo tanto, finitos, lo que contradice la suposición de que el gráfico es infinito. Por tanto, podemos elegir uno de estos vértices y llamarlo v 2 .
Ahora se pueden alcanzar infinitos vértices de G desde v 2 con una ruta simple que no incluye el vértice v 1 . Cada uno de estos caminos debe comenzar con uno de los numerosos vértices adyacentes a v 2 . Entonces, un argumento similar al anterior muestra que debe haber uno de esos vértices adyacentes a través del cual se pueden alcanzar infinitos vértices; elige uno y llámalo v 3 .
Continuando de esta manera, se puede construir un camino infinito simple usando inducción matemática y una versión débil del axioma de elección dependiente . En cada paso, la hipótesis de inducción establece que hay infinitos nodos alcanzables por una ruta simple desde un nodo particular v i que no pasa por uno de un conjunto finito de vértices. El argumento de la inducción es que uno de los vértices adyacentes a v i satisface la hipótesis de inducción, incluso cuando v i se suma al conjunto finito.
El resultado de este argumento de inducción es que para todo n es posible elegir un vértice v n como describe la construcción. El conjunto de vértices elegidos en la construcción es entonces una cadena en el gráfico, porque cada uno fue elegido para ser adyacente al anterior, y la construcción garantiza que el mismo vértice nunca se elija dos veces.
Aspectos de computabilidad
Los aspectos de computabilidad del lema de Kőnig se han investigado a fondo. La forma del lema de Kőnig más conveniente para este propósito es la que establece que cualquier subárbol infinito de ramificación finita detiene un camino infinito. Aquídenota el conjunto de números naturales (considerado como un número ordinal ) yel árbol cuyos nodos son todas secuencias finitas de números naturales, donde el padre de un nodo se obtiene eliminando el último elemento de una secuencia. Cada secuencia finita se puede identificar con una función parcial deconsigo mismo, y cada camino infinito puede identificarse con una función total. Esto permite un análisis utilizando las técnicas de la teoría de la computabilidad.
Un subárbol de en el que cada secuencia tiene sólo un número finito de extensiones inmediatas (es decir, el árbol tiene un grado finito cuando se ve como un gráfico) se denomina ramificación finita . No todos los subárboles infinitos de tiene una ruta infinita, pero el lema de Kőnig muestra que cualquier subárbol de ramificación finita debe tener dicha ruta.
Para cualquier subárbol T dela notación Ext ( T ) denota el conjunto de nodos de T a través de los cuales hay un camino infinito. Incluso cuando T es computable, el conjunto Ext ( T ) puede no ser computable. Cada subárbol T deque tiene una ruta tiene una ruta calculable desde Ext ( T ).
Se sabe que hay subárboles computables de ramificación no finita de que no tienen un camino aritmético , y de hecho ningún camino hiperaritmético . [2] Sin embargo, cada subárbol computable decon una ruta debe tener una ruta calculable a partir de la O de Kleene , la canónicajuego completo. Esto se debe a que el conjunto Ext ( T ) siempre es(ver jerarquía analítica ) cuando T es computable.
Se ha realizado un análisis más detallado para árboles delimitados computablemente. Un subárbol dese llama acotado computablemente o acotado recursivamente si hay una función computable f de a de modo que para cada secuencia en el árbol y cada n , el n- ésimo elemento de la secuencia es como máximo f ( n ). Por lo tanto, f da un límite de cuán "ancho" es el árbol. Los siguientes teoremas básicos se aplican a subárboles infinitos, computablemente acotados y computables de.
- Cualquiera de estos árboles tiene una ruta calculable a partir de , el conjunto completo canónico de Turing que puede decidir el problema de la detención .
- Cualquiera de estos árboles tiene un camino que es bajo . Esto se conoce como el teorema de base baja .
- Cualquier árbol de este tipo tiene un camino libre de hiperinmunidad . Esto significa que cualquier función computable a partir de la ruta está dominada por una función computable.
- Para cualquier subconjunto no computable X deel árbol tiene un camino que no computa X .
Una forma débil del lema de Kőnig que establece que cada árbol binario infinito tiene una rama infinita se usa para definir el subsistema WKL 0 de aritmética de segundo orden . Este subsistema tiene un papel importante en la matemática inversa . Aquí, un árbol binario es uno en el que cada término de cada secuencia en el árbol es 0 o 1, es decir, el árbol está acotado computablemente a través de la función constante 2. La forma completa del lema de Kőnig no se puede demostrar en WKL 0 , pero es equivalente al subsistema más fuerte ACA 0 .
Relación con las matemáticas constructivas y la compacidad.
La demostración dada anteriormente no se considera generalmente constructiva , porque en cada paso usa una prueba por contradicción para establecer que existe un vértice adyacente desde el cual se pueden alcanzar infinitos otros vértices, y debido a la dependencia de una forma débil de el axioma de la elección . Los hechos sobre los aspectos computacionales del lema sugieren que no se puede dar ninguna prueba que pueda ser considerada constructiva por las principales escuelas de matemáticas constructivas .
El teorema del abanico de LEJ Brouwer ( 1927 ) es, desde un punto de vista clásico, el contrapositivo de una forma del lema de Kőnig. Un subconjunto S dese llama barra si alguna función de al set tiene algún segmento inicial en S . Una barra es separable si cada secuencia está en la barra o no en la barra (esta suposición es necesaria porque el teorema normalmente se considera en situaciones en las que no se asume la ley del centro excluido ). Una barra es uniforme si hay algún número N de modo que cualquier función de a tiene un segmento inicial en la barra de no más de . El teorema del ventilador de Brouwer dice que cualquier barra desmontable es uniforme.
Esto se puede demostrar en un entorno clásico considerando la barra como una cubierta abierta del espacio topológico compacto.. Cada secuencia en la barra representa un conjunto abierto básico de este espacio, y estos conjuntos abiertos básicos cubren el espacio por suposición. Por compacidad, esta cubierta tiene una subcubierta finita. El N del teorema del abanico puede tomarse como la longitud de la secuencia más larga cuyo conjunto abierto básico está en la subcubierta finita. Esta prueba topológica se puede utilizar en matemáticas clásicas para mostrar que la siguiente forma del lema de Kőnig se cumple: para cualquier número natural k , cualquier subárbol infinito del árbol tiene un camino infinito.
Relación con el axioma de elección
El lema de Kőnig puede considerarse un principio de elección; la primera prueba anterior ilustra la relación entre el lema y el axioma de elección dependiente . En cada paso de la inducción, se debe seleccionar un vértice con una propiedad particular. Aunque está probado que existe al menos un vértice apropiado, si hay más de un vértice adecuado puede que no haya elección canónica. De hecho, no se necesita toda la fuerza del axioma de la elección dependiente; como se describe a continuación, basta el axioma de elección contable .
Si el gráfico es contable, los vértices están bien ordenados y se puede elegir canónicamente el vértice adecuado más pequeño. En este caso, el lema de Kőnig se puede demostrar en aritmética de segundo orden con comprensión aritmética y, a fortiori, en teoría de conjuntos ZF (sin elección).
El lema de Kőnig es esencialmente la restricción del axioma de elección dependiente a relaciones completas R, de modo que para cada x solo hay un número finito de z tales que xRz . Aunque el axioma de elección es, en general, más fuerte que el principio de elección dependiente, esta restricción de elección dependiente es equivalente a una restricción del axioma de elección. En particular, cuando la ramificación en cada nodo se realiza en un subconjunto finito de un conjunto arbitrario que no se supone que sea contable, la forma del lema de Kőnig que dice "Todo árbol infinito de ramificación finita tiene un camino infinito" es equivalente al principio de que todo árbol El conjunto contable de conjuntos finitos tiene una función de elección, es decir, el axioma de elección contable para conjuntos finitos. [3] Esta forma del axioma de elección (y por tanto del lema de Kőnig) no se puede demostrar en la teoría de conjuntos ZF.
Generalización
En la categoría de conjuntos , el límite inverso de cualquier sistema inverso de conjuntos finitos no vacíos es no vacío. Esto puede verse como una generalización del lema de Kőnig y puede demostrarse con el teorema de Tychonoff , considerando los conjuntos finitos como espacios discretos compactos, y luego usando la caracterización de la propiedad de intersección finita de compacidad.
Ver también
- Árbol de Aronszajn , por la posible existencia de contraejemplos al generalizar el lema a cardinalidades superiores.
- Título de PA
Notas
- ^ Kőnig (1927) como se explica en Franchella (1997)
- ^ Rogers (1967) , pág. 418ff.
- ^ Truss (1976) , pág. 273; Howard y Rubin (1998) [ página necesaria ] ; compárese con Lévy (1979) , ejercicio IX.2.18.
Referencias
- Brouwer, LEJ (1927), Sobre los dominios de la definición de funciones. publicado en van Heijenoort, Jean, ed. (1967), De Frege a Gödel
- Franchella, Miriam (1997), "Sobre los orígenes del lema infinito de Dénes König", Archivo de Historia de las Ciencias Exactas (51 (1) 3: 2-3): 3–27, doi : 10.1007 / BF00376449
- Howard, Paul; Rubin, Jean (1998), Consecuencias del axioma de elección , Encuestas y monografías matemáticas, 59 , Providence, RI: American Mathematical Society
- Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche" , Acta Sci. Matemáticas. (Szeged) (en alemán) (3 (2-3)): 121–130, archivado desde el original el 23 de diciembre de 2014 , consultado el 23 de diciembre de 2014
- Lévy, Azriel (1979), Teoría básica de conjuntos , Springer, ISBN 3-540-08417-7, MR 0533962; reimpresión, Dover, 2002, ISBN 0-486-42079-5 .
- Rogers, Hartley, Jr. (1967), Teoría de funciones recursivas y computabilidad efectiva , McGraw-Hill, MR 0224462
- Truss, J. (1976), "Algunos casos del lema de König", en Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej (eds.), Teoría de conjuntos y teoría de la jerarquía: un tributo conmemorativo a Andrzej Mostowski , Lecture Notes in Mathematics, 537 , Springer, págs. 273-284, doi : 10.1007 / BFb0096907 , MR 0429557
Otras lecturas
- Cenzer, Douglas (1999), "clases de teoría de la computabilidad ", Manual de teoría de la computabilidad , Elsevier, págs. 37–85 , doi : 10.1016 / S0049-237X (99) 80018-4 , ISBN 0-444-89882-4, MR 1720779
- Kőnig, D. (1926), "Sur les correspondances multivoques des ensembles" (PDF) , Fundamenta Mathematicae (en francés) (8): 114-134
- Kőnig, D. (1936), Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (en alemán), Leipzig: Akad. Verlag
- Simpson, Stephen G. (1999), Subsistemas de aritmética de segundo orden , Perspectivas en lógica matemática, Springer, ISBN 3-540-64882-8, MR 1723993
- Soare, Robert I. (1987), Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente , Perspectivas en lógica matemática, Springer, ISBN 3-540-15299-7, MR 0882921
enlaces externos
- Enciclopedia de Filosofía de Stanford: Matemáticas Constructivas
- El proyecto Mizar ha formalizado completamente y comprobado automáticamente la prueba de una versión del lema de König en el archivo TREES_2 .