Bien-cuasi-ordenamiento

Concepto matemático para comparar objetos.

En matemáticas , específicamente en teoría del orden , un buen cuasi ordenamiento o wqo en un conjunto es un cuasi ordenamiento de para el cual cada secuencia infinita de elementos de contiene un par creciente con ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j.}$

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 saber cuándo un cuasiorden está bien fundado. (Aquí, por abuso de la terminología, se dice que un cuasiorden está bien fundado si el orden estricto correspondiente es una relación bien fundada). Sin embargo, la clase de cuasiórdenes bien fundados no está cerrada bajo ciertas operaciones; es decir, cuando se utiliza un cuasiorden para obtener un nuevo cuasiorden en un conjunto de estructuras derivadas de nuestro conjunto original, se descubre que este cuasiorden no está bien fundado. Al colocar restricciones más fuertes en el cuasiordenamiento bien fundado original, uno puede esperar asegurar que nuestros cuasiórdenes derivados sigan estando bien fundados. ${\displaystyle \leq }$ ${\displaystyle x\leq y\land y\nleq x}$

Un ejemplo de esto es la operación de conjuntos potencia . Dado un cuasiordenamiento para un conjunto, se puede definir un cuasiordenamiento en el conjunto potencia de , estableciendo si y solo si para cada elemento de uno puede encontrar algún elemento de que sea mayor que él con respecto a . Se puede demostrar que este cuasiordenamiento en no necesita estar bien fundado, pero si se toma el cuasiordenamiento original como un cuasiordenamiento bien fundado, entonces lo está. ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle \leq ^{+}}$ ${\displaystyle X}$ ${\displaystyle P(X)}$ ${\displaystyle A\leq ^{+}B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \leq }$ ${\displaystyle P(X)}$

Definición formal

Un cuasiordenamiento adecuado en un conjunto es un cuasiordenamiento (es decir, una relación binaria transitiva reflexiva ) tal que cualquier secuencia infinita de elementos de contiene un par creciente con . Se dice que el conjunto está bien cuasiordenado o, abreviado , wqo . ${\displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle X}$

Un orden parcial bien definido , o wpo , es un wqo que es una relación de ordenamiento adecuada, es decir, es antisimétrica .

Entre otras formas de definir wqo, una es decir que son cuasi-ordenamientos que no contienen secuencias infinitas 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 anticadenas infinitas . ${\displaystyle x_{0}>x_{1}>x_{2}>\cdots }$

Tipo ordinal

Sea bien parcialmente ordenado. Una secuencia (necesariamente finita) de elementos de que no contiene ningún par con se suele llamar secuencia incorrecta . El árbol de secuencias incorrectas es el árbol que contiene un vértice para cada secuencia incorrecta y una arista que une cada secuencia incorrecta no vacía con su padre . La raíz de corresponde a la secuencia vacía. Como no contiene ninguna secuencia incorrecta infinita, el árbol no contiene ningún camino infinito que comience en la raíz. ^{[ cita requerida ]} Por lo tanto, cada vértice de tiene una altura ordinal , que se define por inducción transfinita como . El tipo ordinal de , denotado , es la altura ordinal de la raíz de . ${\displaystyle X}$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle T_{X}}$ ${\displaystyle (x_{1},\ldots ,x_{n-1},x_{n})}$ ${\displaystyle (x_{1},\ldots ,x_{n-1})}$ ${\displaystyle T_{X}}$ ${\displaystyle X}$ ${\displaystyle T_{X}}$ ${\displaystyle v}$ ${\displaystyle T_{X}}$ ${\displaystyle o(v)}$ ${\displaystyle o(v)=\lim _{w\mathrm {\ child\ of\ } v}(o(w)+1)}$ ${\displaystyle X}$ ${\displaystyle o(X)}$ ${\displaystyle T_{X}}$

Una linealización de es una extensión del orden parcial a un orden total. Es fácil verificar que es un límite superior en el tipo ordinal de cada linealización de . De Jongh y Parikh ^[1] demostraron que, de hecho, siempre existe una linealización de que alcanza el tipo ordinal máximo . ${\displaystyle X}$ ${\displaystyle o(X)}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle o(X)}$

Ejemplos

Imagen 1: Números enteros con el orden habitual

Imagen 2: Diagrama de Hasse de los números naturales ordenados por divisibilidad

Imagen 3: Diagrama de Hasse con orden de componentes ${\displaystyle \mathbb {N} ^{2}}$

• ${\displaystyle (\mathbb {N} ,\leq )}$, el conjunto de los números naturales con ordenación estándar, es un orden parcial correcto (de hecho, un buen orden ). Sin embargo, , el conjunto de los números enteros positivos y negativos, no es un buen cuasiorden, porque no está bien fundado (véase la figura 1). ${\displaystyle (\mathbb {Z} ,\leq )}$
• ${\displaystyle (\mathbb {N} ,|)}$, el conjunto de los números naturales ordenados por divisibilidad, no es un buen cuasi-orden: los números primos son una anticadena infinita (ver figura 2).
• ${\displaystyle (\mathbb {N} ^{k},\leq )}$, el conjunto de vectores de números naturales (donde es finito) con ordenamiento por componentes , es un buen orden parcial ( lema de Dickson ; ver Fig.3). De manera más general, si es un buen cuasi-orden, entonces es también un buen cuasi-orden para todo . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (X,\leq )}$ ${\displaystyle (X^{k},\leq ^{k})}$ ${\displaystyle k}$
• Sea un conjunto finito arbitrario con al menos dos elementos. El conjunto de palabras sobreordenadas lexicográficamente (como en un diccionario) no es un cuasiorden bien porque contiene la secuencia infinita decreciente . De manera similar, ordenado por la relación de prefijo no es un cuasiorden bien, porque la secuencia anterior es una anticadena infinita de este orden parcial. Sin embargo, ordenado por la relación de subsecuencia es un orden parcial bien. ^[2] (Si tiene solo un elemento, estos tres órdenes parciales son idénticos). ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle b,ab,aab,aaab,\ldots }$ ${\displaystyle X^{*}}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$
• En términos más generales, , el conjunto de sucesiones finitas ordenadas por incrustación es un cuasiorden correcto si y solo si es un cuasiorden correcto ( lema de Higman ). Recordemos que se incrusta una sucesión en una sucesión encontrando una subsecuencia de que tenga la misma longitud que y que la domine término por término. Cuando es un conjunto desordenado, si y solo si es una subsecuencia de . ${\displaystyle (X^{*},\leq )}$ ${\displaystyle X}$ ${\displaystyle (X,\leq )}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle (X,=)}$ ${\displaystyle u\leq v}$ ${\displaystyle u}$ ${\displaystyle v}$
• ${\displaystyle (X^{\omega },\leq )}$, el conjunto de secuencias infinitas sobre un buen cuasiorden , ordenado por incrustación, no es un buen cuasiorden en general. Es decir, el lema de Higman no se traslada a secuencias infinitas. Se han introducido mejores cuasiordenamientos para generalizar el lema de Higman a secuencias de longitudes arbitrarias. ${\displaystyle (X,\leq )}$
• La incrustación entre árboles finitos con nodos etiquetados por elementos de un wqo es un wqo ( teorema del árbol de Kruskal ). ${\displaystyle (X,\leq )}$
• La incrustación entre árboles infinitos con nodos etiquetados por elementos de un wqo es un wqo ( teorema de Nash-Williams ). ${\displaystyle (X,\leq )}$
• La incrustación entre tipos de orden lineal dispersos contables es un cuasi-orden bien definido ( teorema de Laver ).
• La incrustación entre álgebras booleanas numerables es un orden bien cuasi ordenado. Esto se desprende del teorema de Laver y de un teorema de Ketonen.
• Los gráficos finitos ordenados por una noción de incrustación llamada " gráfico menor " son un cuasi-orden ( teorema de Robertson-Seymour ).
• Los gráficos de profundidad de árbol finito ordenados por la relación de subgrafo inducido forman un cuasiorden bien ordenado, ^[3] al igual que los cografos ordenados por subgrafos inducidos. ^[4]

Construir nuevos WPO a partir de los ya existentes

Sean y dos conjuntos wpo disjuntos. Sea , y defina un orden parcial en haciendo que si y solo si para el mismo y . Entonces es wpo, y , donde denota la suma natural de ordinales. ^[1] ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle Y=X_{1}\cup X_{2}}$ ${\displaystyle Y}$ ${\displaystyle y_{1}\leq _{Y}y_{2}}$ ${\displaystyle y_{1},y_{2}\in X_{i}}$ ${\displaystyle i\in \{1,2\}}$ ${\displaystyle y_{1}\leq _{X_{i}}y_{2}}$ ${\displaystyle Y}$ ${\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})}$ ${\displaystyle \oplus }$

Dados los conjuntos wpo y , definamos un orden parcial en el producto cartesiano , haciendo que si y solo si y . Entonces es wpo (esta es una generalización del lema de Dickson ), y , donde denota el producto natural de ordinales. ^[1] ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle Y=X_{1}\times X_{2}}$ ${\displaystyle (a_{1},a_{2})\leq _{Y}(b_{1},b_{2})}$ ${\displaystyle a_{1}\leq _{X_{1}}b_{1}}$ ${\displaystyle a_{2}\leq _{X_{2}}b_{2}}$ ${\displaystyle Y}$ ${\displaystyle o(Y)=o(X_{1})\otimes o(X_{2})}$ ${\displaystyle \otimes }$

Dado un conjunto wpo , sea el conjunto de sucesiones finitas de elementos de , parcialmente ordenados por la relación de subsecuencia. Es decir, sea si y solo si existen índices tales que para cada . Por el lema de Higman , es wpo. El tipo ordinal de es ^{[1] [5]} ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})}$ ${\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m}$ ${\displaystyle x_{j}\leq _{X}y_{i_{j}}}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle X^{*}}$ ${\displaystyle X^{*}}$ $${\displaystyle o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}}$$

Dado un conjunto wpo , sea el conjunto de todos los árboles finitos con raíz cuyos vértices están etiquetados por elementos de . Parcialmente ordenado por la relación de incrustación de árboles . Por el teorema del árbol de Kruskal , es wpo. Este resultado no es trivial incluso para el caso (que corresponde a árboles no etiquetados), en cuyo caso es igual al ordinal pequeño de Veblen . En general, para contable, tenemos el límite superior en términos de la función de colapso ordinal . (El ordinal pequeño de Veblen es igual a en esta notación ordinal). ^[6] ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle T(X)}$ ${\displaystyle |X|=1}$ ${\displaystyle o(T(X))}$ ${\displaystyle o(X)}$ ${\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))}$ ${\displaystyle \vartheta }$ ${\displaystyle \vartheta (\Omega ^{\omega })}$

Órdenes parciales de Wqo versus well

En la práctica, las wqo que se manipulan no suelen ser ordenamientos (ver los ejemplos anteriores), y la teoría es técnicamente más fluida ^{[ cita requerida ]} si no requerimos antisimetría, por lo que se construye con las wqo como noción básica. Por otro lado, según Milner 1985, no se obtiene ninguna ganancia real en generalidad al considerar cuasiórdenes en lugar de órdenes parciales... simplemente es más conveniente hacerlo así.

Obsérvese 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, obtenemos si y solo si , de modo que . ${\displaystyle \mathbb {Z} }$ ${\displaystyle n\equiv m}$ ${\displaystyle n=\pm m}$ ${\displaystyle (\mathbb {Z} ,|)\approx (\mathbb {N} ,|)}$

Subsecuencias infinitas crecientes

Si es wqo entonces cada secuencia infinita contiene una subsecuencia infinita creciente (con ). A veces, una subsecuencia de este tipo se llama perfecta . Esto se puede demostrar mediante un argumento de Ramsey : dada alguna secuencia , considere el conjunto de índices tales que no tiene mayor o igual a su derecha, es decir, con . Si es infinito, entonces la subsecuencia extraída contradice la suposición de que es wqo. Por lo tanto , es finito, y cualquier con mayor que cualquier índice en se puede usar como punto de partida de una subsecuencia infinita creciente. ${\displaystyle (X,\leq )}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots ,}$ ${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }$ ${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$ ${\displaystyle (x_{i})_{i}}$ ${\displaystyle I}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle X}$ ${\displaystyle I}$ ${\displaystyle x_{n}}$ ${\displaystyle n}$ ${\displaystyle I}$

La existencia de tales subsecuencias infinitas crecientes se toma a veces como una definición de buen ordenamiento, lo que conduce a una noción equivalente.

Propiedades de wqos

• Dado un cuasiordenamiento, el cuasiordenamiento definido por está bien fundado si y sólo si es un wqo. ^[7] ${\displaystyle (X,\leq )}$ ${\displaystyle (P(X),\leq ^{+})}$ ${\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}$ ${\displaystyle (X,\leq )}$
• Un cuasiordenamiento es un wqo si y solo si el orden parcial correspondiente (obtenido mediante cociente entre ) no tiene secuencias descendentes infinitas o anticadenas . (Esto se puede demostrar utilizando un argumento de Ramsey como el anterior). ${\displaystyle x\sim y\iff x\leq y\land y\leq x}$
• Dado un buen cuasi-ordenamiento , cualquier secuencia de subconjuntos cerrados hacia arriba eventualmente se estabiliza (lo que significa que existe tal que ; un subconjunto se llama cerrado hacia arriba si ): suponiendo lo contrario , se llega a una contradicción al extraer una subsecuencia infinita no ascendente. ${\displaystyle (X,\leq )}$ ${\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}=S_{n+1}=\cdots }$ ${\displaystyle S\subseteq X}$ ${\displaystyle \forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S}$ ${\displaystyle \forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}}$
• Dado un buen cuasi-ordenamiento , cualquier subconjunto de tiene un número finito de elementos mínimos con respecto a , ya que de lo contrario los elementos mínimos de constituirían una anticadena infinita. ${\displaystyle (X,\leq )}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle S}$

Véase también

• Mejor cuasi-ordenamiento  – relación matemáticaPages displaying wikidata descriptions as a fallback
• Prewellordering  : concepto de teoría de conjuntos
• Buen orden  – Clase de ordenamientos matemáticos

Notas

^ Aquí x < y significa:y ${\displaystyle x\leq y}$ ${\displaystyle x\neq y.}$

Referencias

1. de Jongh, Dick HG; Parikh, Rohit (1977). "Ordenamientos y jerarquías bien parciales". Indagationes Mathematicae (Actas) . 80 (3): 195–207. doi : 10.1016/1385-7258(77)90067-1 .
2. Gasarch, W. (1998), "Un estudio de la combinatoria recursiva", Handbook of Recursive Mathematics, vol. 2 , Stud. Logic Found. Math., vol. 139, Ámsterdam: Holanda Septentrional, págs. 1041–1176, doi :10.1016/S0049-237X(98)80049-9, MR  1673598. Véase en particular la página 1160.
3. Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Lema 6.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 137, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.
4. Damaschke, Peter (1990), "Subgrafos inducidos y buen ordenamiento", Journal of Graph Theory , 14 (4): 427–435, doi :10.1002/jgt.3190140406, MR  1067237.
5. Schmidt, Diana (1979). Ordenamientos bien parciales y sus tipos de orden máximos (Habilitationsschrift). Heidelberg.Republicado en: Schmidt, Diana (2020). "Ordenamientos bien parciales y sus tipos de orden máximo". En Schuster, Peter M.; Seisenberger, Monika; Weiermann, Andreas (eds.). Órdenes bien cuasi en computación, lógica, lenguaje y razonamiento . Tendencias en lógica. Vol. 53. Springer. págs. 351–391. doi :10.1007/978-3-030-30229-0_13.
6. Rathjen, Michael; Weiermann, Andreas (1993). "Investigaciones teóricas de prueba sobre el teorema de Kruskal". Anales de lógica pura y aplicada . 60 : 49–88. doi : 10.1016/0168-0072(93)90192-G .
7. Forster, Thomas (2003). "Mejores cuasiordenamientos y coinducción". Ciencias Informáticas Teóricas . 309 (1–3): 111–123. doi :10.1016/S0304-3975(03)00131-2.

• Dickson, LE (1913). "Finitud de los números impares perfectos y abundantes primitivos con r factores primos distintos". American Journal of Mathematics . 35 (4): 413–422. doi :10.2307/2370405. JSTOR  2370405.
• Higman, G. (1952). "Ordenamiento por divisibilidad en álgebras abstractas". Actas de la London Mathematical Society . 2 : 326–336. doi :10.1112/plms/s3-2.1.326.
• Kruskal, JB (1972). "La teoría del buen ordenamiento: un concepto descubierto con frecuencia". Journal of Combinatorial Theory . Serie A. 13 (3): 297–305. doi : 10.1016/0097-3165(72)90063-5 .
• Ketonen, Jussi (1978). "La estructura de las álgebras booleanas numerables". Anales de Matemáticas . 108 (1): 41–89. doi :10.2307/1970929. JSTOR  1970929.
• Milner, EC (1985). "Teoría básica de WQO y BQO". En Rival, I. (ed.). Grafos y orden. El papel de los grafos en la teoría de conjuntos ordenados y sus aplicaciones . D. Reidel Publishing Co. págs. 487–502. ISBN 90-277-1943-8.
• Gallier, Jean H. (1991). "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γo? Un estudio de algunos resultados en teoría de la demostración". Anales de lógica pura y aplicada . 53 (3): 199–260. doi :10.1016/0168-0072(91)90022-E.