Más rápida hasta entender Kruskal ' s Teorema de árbol

Question

Me encontré con el test de Kruskal Árbol Teorema el otro día y pensé que se parecía bastante interesante (sobre todo los más fuertes de la forma finita debido a Friedman). En la actualidad soy de primer año de matemáticas de estudiantes de pregrado, pero he estado a tercer año de primeros cursos de Lógica y Teoría de conjuntos y la Teoría de grafos, que estoy esperando que me ayudará a entender el teorema (antes de que usted preocupado - la comprensión de este teorema no era la razón por la que fui a los cursos).

Ahora estoy preguntando qué tipo de cursos de pregrado, que debo ir a que me permitirá comprender el teorema y su prueba, incluyendo Friedman. Si usted sabe de cualquier buen libro para exponer el tema (especialmente, como la R. P. Quemar "los Números y Funciones", que enseñar la materia a través de una bien elegida conjunto de ejercicios) entonces yo estaría muy agradecido si usted podría decirme sus nombres.

Gracias!

Answer 1

Una buena referencia para que el teorema es el papel de Jean H. Gallier, "¿Qué es tan especial acerca de Kruskal del teorema y el ordinal $\Gamma_0$? Un estudio de algunos de los resultados en la prueba de la teoría." Ann. Pure Appl. La lógica 53 (1991), no. 3, 199-260.

(Con una pequeña fe de erratas en Ann. Pure Appl. La lógica 89 (1997), no. 2-3, 275.)

No sé de ninguna (pregrado) libros donde Friedman resultado se discute en ningún tipo de detalle, pero este papel es muy bueno.

Para algunos antecedentes, puede que también quiera leer el artículo de José B. test de Kruskal, "La teoría del bien cuasi-pedidos: con frecuencia se descubrió concepto." J. Combinatoria, Teoría De La Ser. 13 (1972), 297-305.

Aquí es el de la revisión de MathScinet:

MR0306057 (46 #5184)

Esta es una encuesta documento que describe la historia y el estado actual de la teoría del bien cuasi-conjuntos ordenados. Un wqo es un qo en la que cada estrictamente descendente de la secuencia es finito y cada conjunto de pares incomparable elementos es finito o, de manera equivalente, cada subconjunto no vacío tiene una, pero no más de un número finito de nonequivalent un mínimo de elementos. Si $s$ $t$ son secuencias de una wqo conjunto, a continuación, $s\leq t$ significa que de alguna larga de $t$ majorizes $s$ término por término. Una pregunta básica es: cuando es un conjunto de secuencias a partir de un wqo fijado wqo? El autor traza la historia de este problema y señala que a través de los años muchos de los resultados ha sido redescubierto y publicado. Este papel y esta sección en la RM debe ayudar a eliminar las posibilidades de reproducción de estos resultados.

Revisado por P. F. Conrad

Un buen libro para aprender sobre la cuasi-orden de la teoría misma, a partir de un lógico con perspectiva, es "Recursiva Aspectos Descriptivos de la Teoría de conjuntos" (Oxford Lógica de Guías), por Richard Mansfield y Galeno Weitkamp. Creo que el nivel es bastante accesible. El capítulo sobre wqo teoría es por S. Simpson, que es una muy buena vitrina.