Sigo enfrentándome a El lema de König "Todo árbol infinito de ramas finitas sobre $\mathbb{N}$ tiene una rama infinita". ¿Por qué no se considera "obvio" sino que necesita una prueba cuidadosa?
Parece algo obvio, pero supongo que se me pasa algo por alto.
Si te refieres a tomar el Lemma de König como casi un axioma de la teoría de conjuntos, entonces estás en un terreno poco claro. Aunque se trata de una afirmación intuitivamente obvia, observe que, a primera vista, también lo es la siguiente afirmación:
Si $T$ es un árbol de altura $\omega_1$ en la que todos los niveles son contables, entonces existe una rama cofinal a través de $T$ .
Lamentablemente, lo anterior es falso como la existencia de Árboles de Aronszajn implica inmediatamente.
Para que no piense que el núcleo de la diferencia está entre $\omega$ y $\omega_1$ es que la primera es cerrada bajo la función exponencial (cardinal) $\lambda \mapsto 2^\lambda$ mientras que este último no lo es, nótese que incluso si asumimos que $\kappa$ es un cardenal inaccesible La declaración
Si $T$ es un árbol de altura $\kappa$ en el que todos los niveles tienen cardinalidad $< \kappa$ entonces hay una rama cofinal a través de $T$
sólo es verdadera si, además, $\kappa$ est poco compacto .
Debemos tener mucho cuidado cuando atribuimos el adjetivo obvio . Podemos demostrar el Lemma de König cuidadosamente a partir de los axiomas habituales, y por lo tanto no hay nada malo en exigir que lo hagamos.
Sin embargo, hay que tener en cuenta que un forma débil del lema de König est se toma como axioma básico en ciertos subsistemas importantes de la aritmética de segundo orden, y se ha demostrado que muchos teoremas matemáticamente interesantes son equivalentes a este axioma sobre subsistemas incluso más débiles.
Dos de las respuestas indican cómo los análogos ingenuos del resultado fallan en cardinales más grandes. Una prueba de la obviedad de un resultado es lo maleable que es, y estos fallos indican que hay obstáculos sutiles.
Una cuestión adicional que las respuestas anteriores no han abordado es que aunque un árbol infinito de ramas finitas sea muy fácil de describir, esto no significa que ninguna de sus ramas lo sea. Para un ejemplo de esta cuestión, véase esta respuesta y para versiones más refinadas, véase la sección sobre "aspectos de computabilidad" en el Entrada de Wikipedia para el lema de König.
Informalmente, solemos decir que un resultado que afirma la existencia de un objeto es obvio, si el objeto puede ser fácilmente calculado a partir de los datos. En el caso que nos ocupa, podemos precisar esta afirmación informal en el contexto de la teoría de la computabilidad, y tenemos resultados precisos que demuestran que falla. Cuanto más difícil sea exhibir una rama, menos convincente será nuestra afirmación de obviedad. (Y podemos ir más allá y combinar ambas pruebas, viendo cuánto más difícil es exhibir una rama cuando relajamos la suposición de que el árbol es de ramas finitas: hay árboles computables sobre $\mathbb N$ con ramas pero sin hiperaritmética ramas).
Sin embargo, una tercera prueba de obviedad radica en las consecuencias ("directas") de un principio, aunque esta prueba quizá tenga menos peso que las otras. El lema de König para árboles sobre $\mathbb N$ es equivalente sobre la teoría débil $\mathsf{RCA}_0$ al teorema de Ramsey infinito para los triples: Fijar un conjunto finito de colores, y asignar un color a cada $3$ -conjunto de números naturales. Entonces hay un subconjunto infinito de $\mathbb N$ todos los cuales $3$ -tienen el mismo color. (Para $\mathsf{RCA}_0$ y las matemáticas inversas, véase aquí .) De nuevo, es "computacionalmente exigente" exponer un conjunto homogéneo infinito de este tipo, incluso en los casos en que la coloración es muy fácil de describir. Para una prueba directa de la equivalencia de estos principios, véase aquí . El teorema de Ramsey para los triples implica trivialmente el resultado correspondiente para los pares. En su libro Ordenaciones lineales Joseph Rosenstein presenta el siguiente ejemplo de una coloración sencilla del $2$ -sin conjuntos homogéneos simples e infinitos: Ordenar linealmente los $2$ -conjuntos de números naturales diciendo que $\{a,b\}<\{c,d\}$ si $a+b<c+d$ o ( $a+b=c+d$ pero $\min\{a,b\}<\min\{c,d\}$ ). Este orden comienza $$\{0,1\}<\{0,2\}<\{0,3\}<\{1,2\}<\{0,4\}<\{1,3\}<\{0,5\}<\dots$$ Ahora colorea de rojo esos pares $\{a,b\}$ que aparecen en lugares pares en esta enumeración, y colorea de azul los que aparecen en lugares Impares.
Podría ser instructivo ver que el lema de Kőnig es falso (y por qué falla) en un entorno computable. Véase este exposición muy clara de Andrej Bauer y en particular el teorema 3.5.
Mira una demostración informal del lema de König (me refiero a una demostración/prueba para los casos simples que te interesan - como otros ya han comentado, las cosas se ponen rápidamente más peliagudas para los árboles de mayor cardinalidad).
Vuelve a mirar con atención. ¿Implica en algún momento la apelación a un principio de elección (alguna versión del axioma de elección)? Si es así, ¿qué versión? Si se apela a una versión de la Elección, ¿es que ¿principio de elección "obvio"? ¿Por qué? E incluso si usted dijera que ese principio de elección también es "obvio", ¿no habría que señalar que son ¿apelando a una versión de Choice?
Estoy de acuerdo en que fuera de contexto este lema parece tan trivial que no justifica ninguna discusión. En un contexto un poco más amplio, la no trivialidad emerge, en (al menos) dos formas. En primer lugar, está la cuestión de qué principio de elección se requiere para el resultado. El resultado parece muy obvio, pero requiere una forma del axioma de elección, por lo que (al menos para los lógicos) ya no es un resultado trivial.
En segundo lugar, se plantea la cuestión natural de ampliar el resultado para contemplar cardinalidades más grandes, que (¿sorprendentemente?) la situación no es tan obvia en absoluto (véase Árbol de Aronszajn ). Así, el caso especial de caminos de cardinalidades contables es cierto, pero depende de algún axioma de elección. Pero para cardinalidades mayores la situación no es tan obvia. A mí me parece que el lema es menos trivial entonces.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
