En matemáticas , específicamente en la teoría del orden , un bien cuasi ordenamiento o wqo es un cuasi ordenamiento tal que cualquier secuencia infinita de elementos de contiene un par creciente con .
Motivación
La inducción bien fundada se puede utilizar en cualquier conjunto con una relación bien fundada, por lo que uno está interesado en cuándo un cuasi-orden está bien fundado. (Aquí, por abuso de terminología, un cuasiorder se dice que está bien fundado si el orden estricto correspondiente es una relación bien fundada.) Sin embargo, la clase de cuasiordenadores bien fundamentados no está cerrada bajo ciertas operaciones, es decir, cuando se usa un cuasi-orden para obtener un nuevo cuasi-orden en un conjunto de estructuras derivadas de nuestro conjunto original , este cuasiorder no está bien fundado. Al imponer restricciones más estrictas al quasiordering original bien fundado, se puede esperar asegurar que nuestros cuasiorderings derivados todavía estén bien fundamentados.
Un ejemplo de esto es la operación de conjunto de energía . Dado un quasiordering para un set se puede definir un quasiorder en conjunto de energía configurando si y solo si para cada elemento de uno puede encontrar algún elemento de que es más grande que él con respecto a . Se puede demostrar que este quasiordar sobre no es necesario que esté bien fundado, pero si se considera que el cuasi-ordenamiento original es un bien cuasi-ordenamiento, entonces lo es.
Definicion formal
Un buen cuasi-pedido en un setes un cuasi-pedido (es decir, un reflexiva , transitiva relación binaria ) de tal manera que cualquier infinita secuencia de elementos de contiene un par creciente con . El conjuntose dice que está bien cuasi-ordenado , o en breve wqo .
Un orden bien parcial , o un wpo , es un wqo que es una relación de ordenación adecuada, es decir, es antisimétrica .
Entre otras formas de definir wqo's, uno es decir que son cuasi-ordenamientos que no contienen infinitas secuencias estrictamente decrecientes (de la forma) [1] ni secuencias infinitas de elementos incomparables por pares . Por lo tanto, un cuasi-orden ( X , ≤) es wqo si y solo si ( X , <) está bien fundado y no tiene antichains infinitos .
Ejemplos de
- , el conjunto de números naturales con orden estándar, es un orden bien parcial (de hecho, un orden bien ). Sin emabargo,, el conjunto de enteros positivos y negativos, no es un cuasi-orden bien, porque no está bien fundado (ver Figura 1).
- , el conjunto de números naturales ordenados por divisibilidad, no es un cuasi-orden bien: los números primos son un antichain infinito (ver Figura 2).
- , el conjunto de vectores de números naturales (donde es finito) con ordenamiento por componentes , es un orden parcial ( lema de Dickson ; ver Figura 3). De manera más general, si está bien cuasi-orden, entonces es también un cuasi-orden para todos .
- Dejar ser un conjunto finito arbitrario con al menos dos elementos. El conjuntode palabras terminadas ordenado lexicográficamente (como en un diccionario) no es un cuasi-orden bien porque contiene la secuencia decreciente infinita. Similar,ordenada por la relación de prefijo no es un cuasi-orden bien, porque la secuencia anterior es un antichain infinito de este orden parcial. Sin emabargo,ordenado por la relación de subsecuencia es un orden parcial. [1] (Si tiene un solo elemento, estos tres órdenes parciales son idénticos).
- Más generalmente, , el conjunto de finito -secuencias ordenadas por incrustación es un bien cuasi-orden si y solo sies un cuasi-orden bien ( lema de Higman ). Recuerda que uno incrusta una secuencia en una secuencia encontrando una subsecuencia de que tiene la misma longitud que y eso lo domina término a término. Cuándo es un conjunto desordenado, si y solo si es una subsecuencia de .
- , el conjunto de secuencias infinitas sobre un cuasi-orden bien , ordenado por incrustación, no es un cuasi-orden bien en general. Es decir, el lema de Higman no se traslada a secuencias infinitas. Se han introducido mejores cuasi-ordenamientos para generalizar el lema de Higman a secuencias de longitudes arbitrarias.
- Incrustación entre árboles finitos con nodos etiquetados por elementos de un wqo es un wqo ( teorema del árbol de Kruskal ).
- Incrustación entre árboles infinitos con nodos etiquetados por elementos de un wqo es un wqo (teorema de Nash-Williams ).
- La incrustación entre tipos de órdenes lineales dispersos contables es un cuasi-orden bien ( teorema de Laver ).
- La incrustación entre álgebras booleanas contables es un cuasi-orden. Esto se sigue del teorema de Laver y de un teorema de Ketonen.
- Los gráficos finitos ordenados por una noción de incrustación llamada " grafo menor " son un cuasi-orden de pozo ( teorema de Robertson-Seymour ).
- Los gráficos de profundidad de árbol finita ordenados por la relación de subgrafo inducido forman un cuasi-orden de pozo, [2] al igual que los gráficos ordenados por subgrafos inducidos. [3]
Wqo's versus pedidos parciales de pozo
En la práctica, las manipulaciones de wqo a menudo no son ordenaciones (ver ejemplos arriba), y la teoría es técnicamente más suave [ cita requerida ] si no requerimos antisimetría, por lo que se construye con wqo como noción básica. Por otro lado, según Milner 1985, no se obtiene una ganancia real en generalidad al considerar cuasi-órdenes en lugar de órdenes parciales ... simplemente es más conveniente hacerlo.
Observe que un wpo es un wqo, y que un wqo da lugar a un wpo entre clases de equivalencia inducidas por el núcleo del wqo. Por ejemplo, si ordenamos por divisibilidad, terminamos con si y solo si , así que eso .
Subsecuencias crecientes infinitas
Si es wqo entonces cada secuencia infinita contiene una subsecuencia creciente infinita (con ). Esta subsecuencia a veces se llama perfecta . Esto se puede probar con un argumento de Ramsey : dada alguna secuencia, considera el conjunto de índices tal que no tiene mayor ni igual a su derecha, es decir, con . Si es infinito, entonces el -La subsecuencia extraída contradice la suposición de que es wqo. Entonces es finito, y cualquier con más grande que cualquier índice en se puede utilizar como punto de partida de una subsecuencia creciente infinita.
La existencia de tales subsecuencias crecientes infinitas a veces se toma como una definición de cuasi-ordenamiento bien, lo que lleva a una noción equivalente.
Propiedades de wqos
- Dado un quasiordering el quasiorder definido por está bien fundado si y solo si es un wqo. [4]
- Un quasordenar es un wqo si y solo si el orden parcial correspondiente (obtenido al cociente entre ) no tiene secuencias infinitas descendentes o antichains . (Esto se puede probar usando un argumento de Ramsey como el anterior).
- Dado un buen cuasi-ordenamiento , cualquier secuencia de subconjuntos cerrados hacia arriba eventualmente se estabiliza (lo que significa que existe tal que ; un subconjuntose llama hacia arriba- cerrado si): asumiendo lo contrario , se llega a una contradicción extrayendo una subsecuencia infinita no ascendente.
- Dado un buen cuasi-ordenamiento , cualquier subconjunto de tiene un número finito de elementos mínimos con respecto a , porque de lo contrario los elementos mínimos de constituiría un antichain infinito.
Notas
^ Aquíx<ysignifica: y
- ^ Gasarch, W. (1998), "Una encuesta de combinatoria recursiva", Manual de matemáticas recursivas, vol. 2 , Stud. Lógica encontrada. Math., 139 , Amsterdam: North-Holland, págs. 1041-1176, doi : 10.1016 / S0049-237X (98) 80049-9 , MR 1673598. Ver en particular la página 1160.
- ^ Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Lema 6.13", Dispersidad: Gráficos, Estructuras y Algoritmos , Algoritmos y Combinatoria, 28 , Heidelberg: Springer, p. 137, doi : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ Damaschke, Peter (1990), "Subgrafos inducidos y bien cuasi-ordenamiento", Journal of Graph Theory , 14 (4): 427–435, doi : 10.1002 / jgt.3190140406 , MR 1067237.
- ^ Forster, Thomas (2003). "Mejores cuasi-pedidos y coinducción" . Informática Teórica . 309 (1-3): 111-123. doi : 10.1016 / S0304-3975 (03) 00131-2 . CS1 maint: parámetro desalentado ( enlace )
Referencias
- Dickson, LE (1913). "Finitud de los números abundantes primitivos y perfectos impares con r factores primos distintos". Revista Estadounidense de Matemáticas . 35 (4): 413–422. doi : 10.2307 / 2370405 . JSTOR 2370405 . CS1 maint: parámetro desalentado ( enlace )
- Higman, G. (1952). "Ordenar por divisibilidad en álgebras abstractas". Actas de la London Mathematical Society . 2 : 326–336. doi : 10.1112 / plms / s3-2.1.326 . CS1 maint: parámetro desalentado ( enlace )
- Kruskal, JB (1972). "La teoría del bien-cuasi-ordenamiento: un concepto descubierto con frecuencia". Revista de teoría combinatoria . Serie A. 13 (3): 297-305. doi : 10.1016 / 0097-3165 (72) 90063-5 . CS1 maint: parámetro desalentado ( enlace )
- Ketonen, Jussi (1978). "La estructura de las álgebras de Boole contables". Annals of Mathematics . 108 (1): 41–89. doi : 10.2307 / 1970929 . JSTOR 1970929 .
- Milner, CE (1985). "Teoría básica de WQO y BQO". En Rival, I. (ed.). Gráficos y orden. El papel de los gráficos en la teoría de conjuntos ordenados y sus aplicaciones . D. Reidel Publishing Co. págs. 487–502. ISBN 90-277-1943-8. CS1 maint: parámetro desalentado ( enlace )
- Gallier, Jean H. (1991). "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γo? Una revisión de algunos resultados en la teoría de la prueba". Anales de lógica pura y aplicada . 53 (3): 199–260. doi : 10.1016 / 0168-0072 (91) 90022-E . CS1 maint: parámetro desalentado ( enlace )
Ver también
- Mejor cuasi-pedido
- Ordenamiento previo
- Bien ordenado