Extensión lineal

Ordenación matemática 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 producto .

Definiciones

Extensión lineal de un orden parcial

Un orden parcial es una relación reflexiva , transitiva y antisimétrica . Dados cualesquiera órdenes parciales 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 orden total , y
2. Para 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 desde un conjunto parcialmente ordenado a una cadena en el mismo conjunto base. ${\displaystyle P}$ ${\displaystyle C}$

Extensión lineal de un preorden

Un preorden es una relación reflexiva y transitiva. La diferencia entre un preorden y un orden parcial es que un preorden permite que dos elementos diferentes se consideren "equivalentes", es decir, que se cumplen tanto y , mientras que un orden parcial permite esto solo cuando . Una relación se denomina 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. Para cada si entonces , y ${\displaystyle x,y\in X,}$ ${\displaystyle x\precsim y}$ ${\displaystyle x\precsim ^{*}y}$
3. Para 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á solamente en la condición 3. Cuando la extensión es un orden parcial, no es necesario enunciar explícitamente la condición 3, ya que se sigue de la condición 2. Demostración : supóngase que y no . Por la condición 2, . Por reflexividad, "no " implica que . Puesto que es un orden parcial, e implican "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 los preordenes 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 se cumple 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 orden

La afirmación de que todo orden parcial puede extenderse a un orden total se conoce como principio de extensión de orden . Una prueba que utiliza el axioma de elección fue publicada por primera vez por Edward Marczewski (Szpilrajin) 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ían sido publicadas. ^[1]

Existe una afirmación análoga para los preordenes: cada preorden puede extenderse a un preorden total. Esta afirmación fue demostrada por Hansson. ^{[2] : Lema 3}

En la teoría axiomática moderna de conjuntos, el principio de extensión de orden se considera 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 del ideal primo de Boole o en 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 (según este principio) todo conjunto puede ordenarse linealmente. Esta afirmación de que todo conjunto puede ordenarse linealmente se conoce como principio de ordenación , OP, y es un debilitamiento del teorema de buen ordenamiento . Sin embargo, hay modelos de teoría de conjuntos en los que se cumple el principio de ordenación mientras que el principio de extensión de orden no. ^[5]

Resultados relacionados

El principio de extensión de orden es demostrable de manera constructiva para conjuntos finitos utilizando algoritmos de ordenamiento topológico , donde el orden parcial está representado por un grafo acíclico dirigido con los elementos del conjunto como sus vértices . Varios algoritmos pueden encontrar una extensión en 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 completamente aleatorio en tiempo 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; equivalentemente, 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.

Los antimatroides pueden considerarse como órdenes parciales generalizadores; 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 las que el número está entre 1/3 y 2/3 del número total de extensiones lineales de ^{[11] [12]} Una forma equivalente de enunciar la conjetura es que, si uno elige una extensión lineal de uniformemente al azar, hay un par que tiene una probabilidad entre 1/3 y 2/3 de estar ordenado como Sin embargo, para ciertos conjuntos parcialmente ordenados infinitos, con una probabilidad canónica definida en sus extensiones lineales como un 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 conjunto de elementos finitos es un problema común en la combinatoria algebraica . Este número se obtiene multiplicando el coeficiente principal del polinomio de orden por ${\displaystyle |P|!.}$

Las tablas jóvenes pueden considerarse como extensiones lineales de un ideal de orden finito en el poset infinito y se cuentan mediante la fórmula de longitud de 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 , Dover Publications , ISBN 978-0-486-46624-8.
4. Felgner, U.; Truss, JK (marzo de 1999), "La independencia del teorema del ideal primo respecto 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 de 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 sobre matemáticas puras, vol. 13, American Mathematical Society, págs. 179–183.
6. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "Sección 22.4: Ordenació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), "Conteo de extensiones lineales", Order , 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", Discrete Mathematics , 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", Discrete Mathematics , 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, Enciclopedia de Matemáticas y sus Aplicaciones, vol. 40, Cambridge University Press, págs. 284–357, ISBN 978-0-521-38165-9. Véase especialmente el punto (1) de la pág. 294.
11. Kislitsyn, SS (1968), "Conjuntos finitos parcialmente ordenados y sus conjuntos asociados de permutaciones", Matematicheskie Zametki , 4 : 511–518.
12. Brightwell, Graham R. (1999), "Pares equilibrados en órdenes parciales", Discrete Mathematics , 201 (1–3): 25–52, doi :10.1016/S0012-365X(98)00311-2.
13. Brightwell, GR; Felsner, S.; Trotter, WT (1995), "Pares de equilibrio y la conjetura del producto vectorial", Order , 12 (4): 327–349, CiteSeerX 10.1.1.38.7841 , doi :10.1007/BF01110378, MR  1368815, S2CID  14793475 .