En la teoría de pedidos, un mejor cuasi-ordenamiento o bqo es un cuasi-ordenamiento que no admite un cierto tipo de arreglo defectuoso. Cada mejor cuasi-pedido es un bien cuasi-pedido .
Motivación
Aunque el buen cuasi-ordenamiento es una noción atractiva, muchas operaciones infinitarias importantes no conservan el buen cuasi-ordenamiento. Un ejemplo de Richard Rado ilustra esto. [1] En un artículo de 1965, Crispin Nash-Williams formuló la noción más fuerte de mejor cuasi-ordenamiento para demostrar que la clase de árboles de altura ω está bien cuasi-ordenada bajo la relación topológica menor . [2] Desde entonces, se ha demostrado que muchos cuasi-ordenamientos son bien cuasi-ordenamientos al demostrar que son mejores-cuasi-ordenamientos. Por ejemplo, Richard Laver estableció el teorema de Laver (anteriormente una conjetura de Roland Fraïssé ) al demostrar que la clase de tipos de orden lineal disperso está mejor-cuasi-ordenada. [3] Más recientemente, Carlos Martínez-Ranero ha demostrado que, bajo el axioma de forzamiento adecuado , la clase de líneas de Aronszajn está mejor-cuasi-ordenada bajo la relación de incrustabilidad. [4]
Definición
Es común en la teoría del mejor cuasi ordenamiento escribir para la secuencia con el primer término omitido. Escribirpara el conjunto de sucesiones finitas, estrictamente crecientes con términos eny definir una relación en como sigue: si hay tal que es un segmento inicial estricto de y . La relaciónno es transitivo .
Un bloque es un subconjunto infinito de que contiene un segmento inicial [ aclaración necesaria ] de cada subconjunto infinito de. Para un cuasi-pedido, a -patrón es una función de algún bloque dentro . A-patrón se dice que es malo si[ aclaración necesaria ] para cada par tal que ; de lo contrarioes bueno . Un cuasi-ordense llama un mejor cuasi-ordenamiento si no hay un mal-patrón.
Para facilitar el trabajo con esta definición, Nash-Williams define una barrera como un bloque cuyos elementos son incomparables por pares bajo la relación de inclusión. A-array es un-patrón cuyo dominio es una barrera. Al observar que cada bloque contiene una barrera, se ve que es un mejor cuasi-ordenamiento si y solo si no hay mal -formación.
Definición alternativa de Simpson
Simpson introdujo una definición alternativa de mejor cuasi ordenamiento en términos de funciones de Borel , dónde , el conjunto de subconjuntos infinitos de , se le da la topología de producto habitual . [5]
Dejar ser un cuasi-ordenante y dotar con la topología discreta . A-array es una función de Borel para algún subconjunto infinito de . A-formación es malo si para cada ; es bueno de otra manera. El cuasi-ordenamientoes un mejor cuasi-ordenamiento si no hay mal-array en este sentido.
Teoremas mayores
Muchos resultados importantes en la teoría del cuasi-ordenamiento mejor son consecuencias del Lema de la matriz mínimamente incorrecta, que aparece en el artículo de Simpson [5] de la siguiente manera. Véase también el artículo de Laver, [6] donde, como resultado, se estableció por primera vez el Lema de matriz mínimamente incorrecta. La técnica estaba presente en el artículo original de 1965 de Nash-Williams.
Suponer es un cuasi-orden . [ aclaración necesaria ] Una clasificación parcial de es un ordenamiento parcial bien fundado de tal que . Para mal-arrays (en el sentido de Simpson) y , definir:
Decimos un mal -formación es mínimamente malo (con respecto a la clasificación parcial) si no hay nada malo -formación tal que . Las definiciones de y dependen de una clasificación parcial de . La relación no es la parte estricta de la relación .
Teorema (Lema de matriz mínimamente incorrecta) . Dejarser un cuasi-orden equipado con una clasificación parcial y suponga es un mal -formación. Entonces hay un mínimo de mal-formación tal que .
Ver también
Referencias
- ^ Rado, Richard (1954). "Ordenamiento parcial de conjuntos de vectores". Mathematika . 1 (2): 89–95. doi : 10.1112 / S0025579300000565 . Señor 0066441 .
- ^ Nash-Williams, C. St. JA (1965). "En árboles infinitos bien cuasi-ordenados". Procedimientos matemáticos de la Sociedad Filosófica de Cambridge . 61 (3): 697–720. Código Bibliográfico : 1965PCPS ... 61..697N . doi : 10.1017 / S0305004100039062 . ISSN 0305-0041 . Señor 0175814 .
- ^ Laver, Richard (1971). "Sobre la conjetura del tipo de orden de Fraisse". Los anales de las matemáticas . 93 (1): 89-111. doi : 10.2307 / 1970754 . JSTOR 1970754 .
- ^ Martínez-Ranero, Carlos (2011). "Líneas de Aronszajn bien cuasi-ordenadas". Fundamenta Mathematicae . 213 (3): 197–211. doi : 10.4064 / fm213-3-1 . ISSN 0016-2736 . Señor 2822417 .
- ^ a b Simpson, Stephen G. (1985). "Teoría BQO y conjetura de Fraïssé" . En Mansfield, Richard; Weitkamp, Galen (eds.). Aspectos recursivos de la teoría descriptiva de conjuntos . The Clarendon Press, Oxford University Press. págs. 124–38 . ISBN 978-0-19-503602-2. Señor 0786122 .
- ^ Laver, Richard (1978). "Mejores cuasi-ordenamientos y una clase de árboles". En Rota, Gian-Carlo (ed.). Estudios en fundamentos y combinatoria . Prensa académica. págs. 31–48. ISBN 978-0-12-599101-8. Señor 0520553 .