El lema de Kőnig o lema del infinito de Kőnig es un teorema de la teoría de grafos que se debe al matemático húngaro Dénes Kőnig, quien lo publicó en 1927. [1] Proporciona una condición suficiente para que un grafo infinito tenga un camino infinitamente largo. Los aspectos de computabilidad de este teorema han sido investigados exhaustivamente por investigadores en lógica matemática , especialmente en teoría de la computabilidad . Este teorema también tiene papeles importantes en las matemáticas constructivas y la teoría de la prueba .
Sea un grafo conexo , localmente finito e infinito . Esto significa que cada dos vértices pueden estar conectados por un camino finito, cada vértice es adyacente a solo un número finito de otros vértices y el grafo tiene un número infinito de vértices. Entonces 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 útil del lema es que todo árbol infinito contiene un vértice de grado infinito o un camino simple infinito. Si es localmente finito, cumple las condiciones del lema y tiene un rayo, y si no es localmente finito, entonces tiene un vértice de grado infinito.
La construcción de un rayo, en un grafo que cumpla las condiciones del lema, puede realizarse paso a paso, manteniendo en cada paso un camino finito que puede extenderse hasta alcanzar infinitos vértices (no necesariamente todos a lo largo del mismo camino que los demás). Para comenzar este proceso, comience con cualquier vértice único . Este vértice puede considerarse como un camino de longitud cero, que consta de un vértice y ninguna arista. Según los supuestos del lema, cada uno de los infinitos vértices de puede alcanzarse mediante un camino simple que comienza en .
A continuación, siempre que el camino actual termine en algún vértice , considere los infinitos vértices que se pueden alcanzar por caminos simples que extienden el camino actual, y para cada uno de estos vértices construya un camino simple hacia él que extienda el camino actual. Hay infinitos de estos caminos extendidos, cada uno de los cuales conecta desde a uno de sus vecinos, pero solo tiene un número finito de vecinos. Por lo tanto, se sigue por una forma del principio del palomar que al menos uno de estos vecinos se usa como el siguiente paso en infinitos de estos caminos extendidos. Sea un vecino de este tipo, y extienda el camino actual por un borde, el borde desde a . Esta extensión conserva la propiedad de que se pueden alcanzar infinitos vértices por caminos simples que extienden el camino actual.
Al repetir este proceso para extender el camino se obtiene una secuencia infinita de caminos finitos simples, cada uno de los cuales extiende el camino anterior en la secuencia con una arista más. La unión de todos estos caminos es el rayo cuya existencia prometía el lema.
Los aspectos computacionales del lema de König han sido investigados a fondo. Para ello, es conveniente enunciar el lema de König en la forma que cualquier subárbol infinito de ramificación finita tiene un camino infinito. Aquí denota el conjunto de números naturales (considerados como un número ordinal ) y el árbol cuyos nodos son todos secuencias finitas de números naturales, donde el padre de un nodo se obtiene eliminando el último elemento de una secuencia. Cada secuencia finita puede identificarse con una función parcial de a sí misma, 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 solo un número finito de extensiones inmediatas (es decir, el árbol tiene un grado finito cuando se lo ve como un grafo) se llama de ramificación finita . No todo subárbol infinito de tiene un camino infinito, pero el lema de König muestra que cualquier subárbol infinito de ramificación finita debe tener dicho camino.
Para cualquier subárbol de la notación denota el conjunto de nodos de a través del cual hay un camino infinito. Incluso cuando es computable el conjunto puede no ser computable. Siempre que un subárbol de tiene un camino infinito, el camino es computable desde , paso a paso, eligiendo codiciosamente un sucesor en en cada paso. La restricción a asegura que este proceso codicioso no pueda quedarse estancado.
Existen subárboles computables de ramificación no finita que no tienen un camino aritmético , y de hecho, no tienen un camino hiperaritmético . [2] Sin embargo, cada subárbol computable de con un camino debe tener un camino computable a partir del O de Kleene , el conjunto completo canónico . Esto se debe a que el conjunto es siempre (para el significado de esta notación, consulte jerarquía analítica ) cuando es computable.
Se ha llevado a cabo un análisis más detallado para árboles acotados computablemente. Un subárbol de se denomina acotado computablemente o acotado recursivamente si existe una función computable de a tal que para cada secuencia en el árbol y cada número natural , el elemento n de la secuencia es como máximo . Por lo tanto, proporciona un límite para el "ancho" del árbol. Los siguientes teoremas básicos se aplican a subárboles computables, acotados computablemente y infinitos de .
Una forma débil del lema de Kőnig que establece que cada árbol binario infinito tiene una rama infinita se utiliza para definir el subsistema WKL 0 de la aritmética de segundo orden . Este subsistema tiene un papel importante en las matemáticas inversas . Aquí un árbol binario es uno en el que cada término de cada secuencia en el árbol es 0 o 1, lo que significa que el árbol está acotado computacionalmente a través de la función constante 2. La forma completa del lema de Kőnig no es demostrable en WKL 0 , pero es equivalente al subsistema más fuerte ACA 0 .
La prueba dada anteriormente no se considera generalmente constructiva , porque en cada paso utiliza una prueba por contradicción para establecer que existe un vértice adyacente desde el cual se puede llegar a una infinidad de otros vértices, y debido a la dependencia de una forma débil del axioma de elección . Los hechos sobre los aspectos computacionales del lema sugieren que no se puede dar ninguna prueba que sea 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 de se llama barra si cualquier función de a del conjunto tiene algún segmento inicial en S . Una barra es separable si cada secuencia está en la barra o no está en la barra (esta suposición es necesaria porque el teorema se considera ordinariamente en situaciones donde no se supone la ley del medio excluido ). Una barra es uniforme si hay algún número tal que cualquier función de a tiene un segmento inicial en la barra de longitud no mayor que . El teorema del abanico de Brouwer dice que cualquier barra separable es uniforme.
Esto se puede demostrar en un contexto 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. La N del teorema del abanico se puede tomar 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 se cumple la siguiente forma del lema de König: para cualquier número natural k , cualquier subárbol infinito del árbol tiene un camino infinito.
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 se demuestra 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 elección dependiente; como se describe a continuación, basta con el axioma de elección numerable .
Si el grafo es numerable, los vértices están bien ordenados y se puede elegir canónicamente el vértice más pequeño adecuado. En este caso, el lema de König es demostrable en aritmética de segundo orden con comprensión aritmética y, a fortiori, en la 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 enteras tales que para cada una hay solo un número finito de tales que . 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 numerable, 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 conjunto numerable de conjuntos finitos tiene una función de elección, es decir, el axioma de elección numerable para conjuntos finitos. [3] Esta forma del axioma de elección (y, por lo tanto, del lema de König) no es demostrable en la teoría de conjuntos ZF.
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 Tichonoff , considerando los conjuntos finitos como espacios discretos compactos y luego utilizando la propiedad de intersección finita para caracterizar la compacidad.
