Buen ordenamiento casi perfecto

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

La inducción bien fundada puede usarse en cualquier conjunto con una relación bien fundada , por lo que interesa saber cuándo un cuasiorden está bien fundado. (Aquí, por abuso de terminología, un cuasiorden${\displaystyle \leq }$Se dice que está bien fundamentado si el orden estricto correspondiente${\displaystyle x\leq y\land y\nleq x}$(es una relación bien fundamentada). Sin embargo, la clase de cuasiórdenes bien fundamentados no es 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 encuentra que este cuasiorden no está bien fundamentado. Al imponer restricciones más estrictas al cuasiordenamiento bien fundamentado original, se puede esperar asegurar que nuestros cuasiordenamientos derivados sigan estando bien fundamentados.

Un ejemplo de esto es la operación de conjunto potencia . Dado un cuasiordenamiento${\displaystyle \leq }$para un conjunto${\displaystyle X}$se puede definir un cuasiorden${\displaystyle \leq ^{+}}$en${\displaystyle X}$conjunto de poderes${\displaystyle P(X)}$al establecer${\displaystyle A\leq ^{+}B}$si y solo si para cada elemento de${\displaystyle A}$uno puede encontrar algún elemento de${\displaystyle B}$que es más grande que él con respecto a${\displaystyle \leq }$. Se puede demostrar que este cuasiordenamiento en${\displaystyle P(X)}$No es necesario que esté bien fundamentado, pero si se considera que el cuasiordenamiento original es un buen cuasiordenamiento, entonces lo es.

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

Un orden parcial bien definido , o wpo , es un wqo que es una relación de ordenación propia, es decir, es antisimétrico .

Entre otras formas de definir los wqo, una es decir que son cuasi-ordenamientos que no contienen secuencias estrictamente decrecientes infinitas (de la forma${\displaystyle x_{0}>x_{1}>x_{2}>\cdots }$) ^{[ a ]} ​​ni secuencias infinitas de elementos incomparables por pares . Por lo tanto, un cuasiorden ( X , ≤) es wqo si y solo si ( X , <) está bien fundado y no tiene anticadenas infinitas .

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

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

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

Dejar${\displaystyle X_{1}}$y${\displaystyle X_{2}}$Sean dos conjuntos wpo disjuntos.${\displaystyle Y=X_{1}\cup X_{2}}$y definir un orden parcial en${\displaystyle Y}$al dejar${\displaystyle y_{1}\leq _{Y}y_{2}}$si y solo si${\displaystyle y_{1},y_{2}\in X_{i}}$por el mismo${\displaystyle i\in \{1,2\}}$y${\displaystyle y_{1}\leq _{X_{i}}y_{2}}$. Entonces${\displaystyle Y}$es wpo y${\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})}$, dónde${\displaystyle \oplus }$ denota la suma natural de ordinales. ^{[ 2 ]}

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

Dado un conjunto wpo${\displaystyle X}$, dejar${\displaystyle X^{*}}$sea ​​el conjunto de secuencias finitas de elementos de${\displaystyle X}$, parcialmente ordenado por la relación de subsecuencia. Es decir,${\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})}$si y solo si existen índices${\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m}$de tal manera que${\displaystyle x_{j}\leq _{X}y_{i_{j}}}$para cada${\displaystyle 1\leq j\leq n}$. Por el lema de Higman ,${\displaystyle X^{*}}$es wpo. El tipo ordinal de${\displaystyle X^{*}}$es ^{[ 2 ] [ 6 ]}$${\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${\displaystyle X}$, dejar${\displaystyle T(X)}$sea ​​el conjunto de todos los árboles enraizados finitos cuyos vértices están etiquetados por elementos de${\displaystyle X}$. Ordenar parcialmente${\displaystyle T(X)}$por la relación de incrustación de árboles . Por el teorema de árboles de Kruskal ,${\displaystyle T(X)}$es wpo. Este resultado no es trivial incluso para el caso${\displaystyle |X|=1}$(que corresponde a árboles sin etiquetar), en cuyo caso${\displaystyle o(T(X))}$es igual al pequeño ordinal de Veblen . En general, para${\displaystyle o(X)}$numerable, tenemos el límite superior${\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))}$en términos de la${\displaystyle \vartheta }$función de colapso ordinal . (El pequeño ordinal de Veblen es igual a${\displaystyle \vartheta (\Omega ^{\omega })}$en esta notación ordinal.) ^{[ 7 ]}

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. ^{[ 8 ]}

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

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

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

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

• Mejor ordenamiento cuasi-ordenado
• Preordenamiento por pozos – Concepto de teoría de conjuntos 
• Buen orden – Clase de ordenaciones matemáticas 

• Dickson, LE (1913). "Finitud de los números impares perfectos y primitivos abundantes con r factores primos distintos". American Journal of Mathematics . 35 (4): 413– 422. doi : 10.2307/2370405 . JSTOR 2370405 . 
• Higman, G. (1952). "Ordenación por divisibilidad en álgebras abstractas". Actas de la Sociedad Matemática de Londres . 2 : 326–336 . doi : 10.1112/plms/s3-2.1.326 .
• Kruskal, JB (1972). "La teoría del cuasiordenamiento bien establecido: un concepto frecuentemente descubierto" . 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 contables". Annals of Mathematics . 108 (1): 41– 89. doi : 10.2307/1970929 . JSTOR 1970929 . 
• 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". Annals of Pure and Applied Logic . 53 (3): 199– 260. doi : 10.1016/0168-0072(91)90022-E .