extensión lineal

Ordenamiento matemático de un orden parcial

En la teoría del orden , una rama de las matemáticas , una extensión lineal de un orden parcial es un orden total (u orden lineal) que es compatible con el orden parcial. Como ejemplo clásico, el orden lexicográfico de conjuntos totalmente ordenados es una extensión lineal de su orden de producto .

Definiciones

Extensión lineal de un orden parcial.

Un orden parcial es una relación reflexiva , transitiva y antisimétrica . Dado cualquier orden parcial y en un conjunto es una extensión lineal de exactamente cuando ${\displaystyle \,\leq \,}$ ${\displaystyle \,\leq ^{*}\,}$ ${\displaystyle X,}$ ${\displaystyle \,\leq ^{*}\,}$ ${\displaystyle \,\leq \,}$

1. ${\displaystyle \,\leq ^{*}\,}$es un pedido total , y
2. Por cada si entonces ${\displaystyle x,y\in X,}$ ${\displaystyle x\leq y,}$ ${\displaystyle x\leq ^{*}y.}$

Es esa segunda propiedad la que lleva a los matemáticos a describir como extensible ${\displaystyle \,\leq ^{*}\,}$ ${\displaystyle \,\leq .}$

Alternativamente, una extensión lineal puede verse como una biyección que preserva el orden de un conjunto parcialmente ordenado a una cadena en el mismo conjunto básico. ${\displaystyle P}$ ${\displaystyle C}$

Extensión lineal de un pedido anticipado

Un preorden es una relación reflexiva y transitiva. La diferencia entre un pedido anticipado y un pedido parcial es que un pedido anticipado permite que dos artículos diferentes se consideren "equivalentes", es decir, ambos y retenidos, mientras que un pedido parcial permite esto sólo cuando . Una relación se llama extensión lineal de un preorden si: ${\displaystyle x\precsim y}$ ${\displaystyle y\precsim x}$ ${\displaystyle x=y}$ ${\displaystyle \precsim ^{*}}$ ${\displaystyle \precsim }$

1. ${\displaystyle \precsim ^{*}}$es un pedido anticipado total , y
2. Por cada si entonces y ${\displaystyle x,y\in X,}$ ${\displaystyle x\precsim y}$ ${\displaystyle x\precsim ^{*}y}$
3. Por cada si entonces . Aquí significa " y no ". ${\displaystyle x,y\in X,}$ ${\displaystyle x\prec y}$ ${\displaystyle x\prec ^{*}y}$ ${\displaystyle x\prec y}$ ${\displaystyle x\precsim y}$ ${\displaystyle y\precsim x}$

La diferencia entre estas definiciones está sólo en la condición 3. Cuando la extensión es un orden parcial, no es necesario establecer explícitamente la condición 3, ya que se deriva de la condición 2. Prueba : supongamos que y no . Por la condición 2, . Por reflexividad, "no " implica que . Dado que es un orden parcial e implica "no ". Por lo tanto, . ${\displaystyle x\precsim y}$ ${\displaystyle y\precsim x}$ ${\displaystyle x\precsim ^{*}y}$ ${\displaystyle y\precsim x}$ ${\displaystyle y\neq x}$ ${\displaystyle \precsim ^{*}}$ ${\displaystyle x\precsim ^{*}y}$ ${\displaystyle y\neq x}$ ${\displaystyle y\precsim ^{*}x}$ ${\displaystyle x\prec ^{*}y}$

Sin embargo, para pedidos anticipados generales, se necesita la condición 3 para descartar extensiones triviales. Sin esta condición, el preorden por el cual todos los elementos son equivalentes ( y válidos para todos los pares x , y ) sería una extensión de cada preorden. ${\displaystyle y\precsim x}$ ${\displaystyle x\precsim y}$

Principio de extensión de pedidos

La afirmación de que todo orden parcial puede extenderse a un orden total se conoce como principio de extensión de orden . Edward Marczewski (Szpilrajin) publicó por primera vez una prueba que utiliza el axioma de elección en 1930. Marczewski escribe que el teorema había sido demostrado previamente por Stefan Banach , Kazimierz Kuratowski y Alfred Tarski , nuevamente utilizando el axioma de elección, pero que las pruebas no había sido publicado. ^[1]

Hay una afirmación análoga para los pedidos anticipados: cada pedido anticipado puede ampliarse hasta convertirse en un pedido anticipado total. Esta afirmación fue probada por Hansson. ^{[2] : Lema 3}

En la teoría axiomática moderna de conjuntos, el principio de extensión del orden se considera en sí mismo un axioma de estatus ontológico comparable al axioma de elección. El principio de extensión de orden está implícito en el teorema booleano del ideal primo o el teorema de compacidad equivalente , ^[3] pero la implicación inversa no se cumple. ^[4]

La aplicación del principio de extensión de orden a un orden parcial en el que cada dos elementos son incomparables muestra que (bajo este principio) todo conjunto puede ordenarse linealmente. Esta afirmación de que todo conjunto puede ordenarse linealmente se conoce como principio de ordenamiento , OP, y es un debilitamiento del teorema del bien ordenamiento . Sin embargo, existen modelos de teoría de conjuntos en los que el principio de ordenamiento se cumple mientras que el principio de extensión del orden no. ^[5]

Resultados relacionados

El principio de extensión de orden se puede demostrar constructivamente para conjuntos finitos utilizando algoritmos de clasificación topológica , donde el orden parcial se representa mediante un gráfico acíclico dirigido con los elementos del conjunto como vértices . Varios algoritmos pueden encontrar una extensión en el tiempo lineal . ^[6] A pesar de la facilidad de encontrar una única extensión lineal, el problema de contar todas las extensiones lineales de un orden parcial finito es #P-completo ; sin embargo, puede estimarse mediante un esquema de aproximación aleatorio en tiempo totalmente polinomial . ^{[7] [8]} Entre todos los órdenes parciales con un número fijo de elementos y un número fijo de pares comparables, los órdenes parciales que tienen el mayor número de extensiones lineales son semiórdenes . ^[9]

La dimensión de orden de un orden parcial es la cardinalidad mínima de un conjunto de extensiones lineales cuya intersección es el orden parcial dado; de manera equivalente, es el número mínimo de extensiones lineales necesarias para garantizar que cada par crítico del orden parcial se invierta en al menos una de las extensiones.

Se puede considerar que los antimatroides son órdenes parciales generalizadoras; En esta visión, las estructuras correspondientes a las extensiones lineales de un orden parcial son las palabras básicas del antimatroide. ^[10]

Esta área también incluye uno de los problemas abiertos más famosos de la teoría del orden, la conjetura 1/3-2/3 , que establece que en cualquier conjunto finito parcialmente ordenado que no está totalmente ordenado existe un par de elementos de para los cuales las extensiones lineales de en el cual número entre 1/3 y 2/3 del número total de extensiones lineales de ^{[11] [12]} Una forma equivalente de plantear la conjetura es que, si se elige una extensión lineal de uniformemente al azar, existe un par que tiene probabilidad entre 1/3 y 2/3 de estar ordenado como Sin embargo, para ciertos conjuntos infinitos parcialmente ordenados, con una probabilidad canónica definida en sus extensiones lineales como límite de las probabilidades para órdenes parciales finitos que cubren el orden parcial infinito, la conjetura 1/3-2/3 no se cumple. ^[13] ${\displaystyle P}$ ${\displaystyle (x,y)}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle x<y}$ ${\displaystyle P.}$ ${\displaystyle P}$ ${\displaystyle (x,y)}$ ${\displaystyle x<y.}$

combinatoria algebraica

Contar el número de extensiones lineales de un poset finito es un problema común en combinatoria algebraica . Este número viene dado por el coeficiente principal del polinomio de orden multiplicado por ${\displaystyle |P|!.}$

El cuadro joven puede considerarse como extensiones lineales de un ideal de orden finito en el poset infinito y se cuentan mediante la fórmula de longitud del gancho . ${\displaystyle \mathbb {N} \times \mathbb {N} ,}$

Referencias

1. Marczewski, Edward (1930), "Sur l'extension de l'ordre partiel" (PDF) , Fundamenta Mathematicae (en francés), 16 : 386–389, doi : 10.4064/fm-16-1-386-389.
2. Hansson, Bengt (1968). "Estructuras de elección y relaciones de preferencia". Síntesis . 18 (4): 443–458. ISSN  0039-7857.
3. Jech, Thomas (2008) [publicado originalmente en 1973], El axioma de la elección , Publicaciones de Dover , ISBN 978-0-486-46624-8.
4. Felgner, U.; Truss, JK (marzo de 1999), "La independencia del teorema ideal primo del principio de extensión de orden", The Journal of Symbolic Logic , 64 (1): 199–215, CiteSeerX 10.1.1.54.8336 , doi :10.2307/ 2586759, JSTOR  2586759 .
5. Mathias, ARD (1971), "El principio de extensión del orden", en Scott, Dana S.; Jech, Thomas J. (eds.), Teoría de conjuntos axiomáticos (Universidad de California, Los Ángeles, California, 10 de julio - 5 de agosto de 1967) , Actas de simposios en matemáticas puras, vol. 13, Sociedad Estadounidense de Matemáticas, págs. 179–183.
6. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "Sección 22.4: Clasificación topológica", Introducción a los algoritmos (2ª ed.), MIT Press, págs. 549–552, ISBN 978-0-262-03293-3.
7. Brightwell, Graham R.; Winkler, Peter (1991), "Contando extensiones lineales", Orden , 8 (3): 225–242, doi :10.1007/BF00383444, S2CID  119697949
8. Bubley, Russ; Dyer, Martin (1999), "Generación aleatoria más rápida de extensiones lineales", Matemáticas discretas , 201 (1–3): 81–88, doi : 10.1016/S0012-365X(98)00333-1 , S2CID  2942330.
9. Fishburn, Peter C .; Trotter, WT (1992), "Extensiones lineales de semiórdenes: un problema de maximización", Matemáticas discretas , 103 (1): 25–40, doi : 10.1016/0012-365X(92)90036-F , MR  1171114.
10. Björner, Anders; Ziegler, Günter M. (1992), "Introducción a los Greedoids", en White, Neil (ed.), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge University Press, págs. 284–357, ISBN 978-0-521-38165-9. Véase especialmente el punto (1) en la pág. 294.
11. Kislitsyn, SS (1968), "Conjuntos finitos parcialmente ordenados y sus conjuntos de permutaciones asociados", Matematicheskie Zametki , 4 : 511–518.
12. Brightwell, Graham R. (1999), "Pares equilibrados en órdenes parciales", Matemáticas discretas , 201 (1–3): 25–52, doi :10.1016/S0012-365X(98)00311-2.
13. Brightwell, GR; Felsner, S.; Trotter, WT (1995), "Los pares de equilibrio y la conjetura del producto cruzado", Order , 12 (4): 327–349, CiteSeerX 10.1.1.38.7841 , doi :10.1007/BF01110378, MR  1368815, S2CID  14793475 .