Mejor cuasi-ordenamiento

En teoría del orden, un quasi-ordenamiento mejor o bqo es un quasi-ordenamiento que no admite un cierto tipo de matriz incorrecta. Todo quasi-ordenamiento mejor es un quasi-ordenamiento bueno .

Motivación

Aunque el cuasiordenamiento adecuado es una noción atractiva, muchas operaciones infinitarias importantes no preservan el cuasiordenamiento adecuado. 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 cuasiordenamiento para demostrar que la clase de árboles de altura ω está bien cuasiordenada bajo la relación topológica menor . ^[2] Desde entonces, se ha demostrado que muchos cuasiordenamientos son buenos cuasiordenamientos al demostrar que son mejores cuasiordenamientos. 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 dispersos está mejor cuasiordenada. ^[3] Más recientemente, Carlos Martínez-Ranero ha demostrado que, bajo el axioma de forzamiento propio , la clase de líneas de Aronszajn está mejor ordenada bajo la relación de incrustabilidad. ^[4]

Definición

En la teoría de cuasiordenamiento mejorado, es común escribir para la secuencia con el primer término omitido. Escriba para el conjunto de secuencias finitas, estrictamente crecientes con términos en , y defina una relación en de la siguiente manera: si existe tal que es un segmento inicial estricto de y . La relación no es transitiva . ${\displaystyle {_{*}}x}$ ${\displaystyle x}$ ${\displaystyle [\omega ]^{<\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \triangleleft }$ ${\displaystyle [\omega ]^{<\omega }}$ ${\displaystyle s\triangleleft t}$ ${\displaystyle u\in [\omega ]^{<\omega }}$ ${\displaystyle s}$ ${\displaystyle u}$ ${\displaystyle t={}_{*}u}$ ${\displaystyle \triangleleft }$

Un bloque es un subconjunto infinito de que contiene un segmento inicial ^{[ aclaración necesaria ]} de cada subconjunto infinito de . Para un cuasiordenamiento , un -patrón es una función de algún bloque en . Se dice que un -patrón es malo si ^{[ aclaración necesaria ]} para cada par tal que ; en caso contrario es bueno . Un cuasiordenamiento se denomina un cuasiordenamiento mejor si no hay un -patrón malo. ${\displaystyle B}$ ${\displaystyle [\omega ]^{<\omega }}$ ${\displaystyle \bigcup B}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle B}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle f\colon B\to Q}$ ${\displaystyle f(s)\not \leq _{Q}f(t)}$ ${\displaystyle s,t\in B}$ ${\displaystyle s\triangleleft t}$ ${\displaystyle f}$ ${\displaystyle Q}$ ${\displaystyle Q}$

Para que sea más fácil trabajar 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 . Una matriz es un patrón cuyo dominio es una barrera. Al observar que cada bloque contiene una barrera, se ve que es un cuasiordenamiento mejor si y solo si no hay una matriz incorrecta. ${\displaystyle \subset }$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$

Definición alternativa de Simpson

Simpson introdujo una definición alternativa de mejor cuasi-ordenamiento en términos de funciones de Borel , donde , el conjunto de subconjuntos infinitos de , recibe la topología de producto habitual . ^[5] ${\displaystyle [\omega ]^{\omega }\to Q}$ ${\displaystyle [\omega ]^{\omega }}$ ${\displaystyle \omega }$

Sea un cuasi-ordenamiento y dote de la topología discreta . Un -arreglo es una función de Borel para algún subconjunto infinito de . Un -arreglo es malo si para cada ; es bueno en caso contrario. El cuasi-ordenamiento es un cuasi-ordenamiento mejor si no hay un -arreglo malo en este sentido. ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle [A]^{\omega }\to Q}$ ${\displaystyle A}$ ${\displaystyle \omega }$ ${\displaystyle Q}$ ${\displaystyle f}$ ${\displaystyle f(X)\not \leq _{Q}f({_{*}}X)}$ ${\displaystyle X\in [A]^{\omega }}$ ${\displaystyle f}$ ${\displaystyle Q}$ ${\displaystyle Q}$

Teoremas mayores

Muchos de los resultados más importantes de la teoría del cuasiordenamiento mejorado son consecuencia del lema de la matriz mínima 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 se planteó por primera vez el lema de la matriz mínima incorrecta como resultado. La técnica estaba presente en el artículo original de Nash-Williams de 1965.

Supongamos que es un cuasi-orden . ^{[ aclaración necesaria ]} Una clasificación parcial de es un ordenamiento parcial bien fundado de tal que . Para matrices incorrectas (en el sentido de Simpson) y , defina: ${\displaystyle (Q,\leq _{Q})}$ ${\displaystyle \leq '}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle q\leq 'r\to q\leq _{Q}r}$ ${\displaystyle Q}$ ${\displaystyle f\colon [A]^{\omega }\to Q}$ ${\displaystyle g\colon [B]^{\omega }\to Q}$

${\displaystyle g\leq ^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)\leq 'f(X){\text{ for every }}X\in [B]^{\omega }}$

${\displaystyle g<^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)<'f(X){\text{ for every }}X\in [B]^{\omega }}$

Decimos que una matriz mala es mínimamente mala (con respecto a la clasificación parcial ) si no existe ninguna matriz mala 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 . ${\displaystyle Q}$ ${\displaystyle g}$ ${\displaystyle \leq '}$ ${\displaystyle Q}$ ${\displaystyle f}$ ${\displaystyle f<^{*}g}$ ${\displaystyle \leq ^{*}}$ ${\displaystyle <'}$ ${\displaystyle \leq '}$ ${\displaystyle Q}$ ${\displaystyle <^{*}}$ ${\displaystyle \leq ^{*}}$

Teorema (Lema del arreglo mínimo malo) . Sea un cuasiorden equipado con una clasificación parcial y supongamos que es un arreglo malo. Entonces existe un arreglo mínimo malo tal que . ${\displaystyle Q}$ ${\displaystyle f}$ ${\displaystyle Q}$ ${\displaystyle Q}$ ${\displaystyle g}$ ${\displaystyle g\leq ^{*}f}$

Véase también

• Bien-cuasi-ordenamiento
• Buen orden

Referencias

1. Rado, Richard (1954). "Ordenamiento parcial correcto de conjuntos de vectores". Mathematika . 1 (2): 89–95. doi :10.1112/S0025579300000565. MR  0066441.
2. Nash-Williams, C. St. JA (1965). "Sobre árboles infinitos bien ordenados". Actas matemáticas de la Sociedad filosófica de Cambridge . 61 (3): 697–720. Bibcode :1965PCPS...61..697N. doi :10.1017/S0305004100039062. ISSN  0305-0041. MR  0175814. S2CID  227358387.
3. Laver, Richard (1971). "Sobre la conjetura del tipo de orden de Fraïssé". Anales de Matemáticas . 93 (1): 89–111. doi :10.2307/1970754. JSTOR  1970754.
4. Martínez-Ranero, Carlos (2011). "Líneas de Aronszajn bien casi ordenadas". Fundamentos Mathematicae . 213 (3): 197–211. doi : 10.4064/fm213-3-1 . ISSN  0016-2736. SEÑOR  2822417.
5. 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.Sr. 0786122  .
6. Laver, Richard (1978). "Mejores cuasiordenamientos y una clase de árboles". En Rota, Gian-Carlo (ed.). Estudios sobre fundamentos y combinatoria . Academic Press. pp. 31–48. ISBN 978-0-12-599101-8.Sr. 0520553  .