pedidos débiles

Clasificación matemática de un conjunto.

Un orden débil en el conjunto donde se clasifica debajo y y son de igual rango, y está clasificado arriba y I) representación como un orden débil estricto donde se muestra como una flecha de a ; II) representación como un pedido anticipado total mostrado mediante flechas; III) representación como una partición ordenada, con los conjuntos de la partición como elipses punteadas y el orden total de estos conjuntos mostrado con flechas. ${\displaystyle \{a,b,c,d\}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c,b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle c}$
${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle x}$ ${\displaystyle y}$
${\displaystyle \,\leq ,}$

Los 13 posibles ordenamientos débiles estrictos en un conjunto de tres elementos. Los únicos pedidos totales se muestran en negro. Dos ordenamientos están conectados por una arista si difieren por una sola dicotomía. ${\displaystyle \{a,b,c\}.}$

En matemáticas , especialmente en teoría del orden , un ordenamiento débil es una formalización matemática de la noción intuitiva de clasificación de un conjunto , algunos de cuyos miembros pueden estar vinculados entre sí. Los pedidos débiles son una generalización de conjuntos totalmente ordenados (clasificaciones sin vínculos) y, a su vez, se generalizan mediante conjuntos (estrictamente) parcialmente ordenados y pedidos anticipados . ^[1]

Hay varias formas comunes de formalizar ordenamientos débiles, que son diferentes entre sí pero criptomórficas (interconvertibles sin pérdida de información): pueden axiomatizarse como ordenamientos débiles estrictos (conjuntos estrictamente parcialmente ordenados en los que la incomparabilidad es una relación transitiva ), como preordenes totales (relaciones binarias transitivas en las que existe al menos una de las dos relaciones posibles entre cada par de elementos), o como particiones ordenadas ( particiones de los elementos en subconjuntos disjuntos, junto con un orden total en los subconjuntos). En muchos casos también es posible otra representación denominada acuerdo preferencial basado en una función de utilidad .

Los pedidos débiles se cuentan según los números de Bell ordenados . Se utilizan en informática como parte de algoritmos de refinamiento de particiones y en la biblioteca estándar de C++ . ^[2]

Ejemplos

En las carreras de caballos , el uso de acabados fotográficos ha eliminado algunos, pero no todos, empates o (como se les llama en este contexto) empates , por lo que el resultado de una carrera de caballos puede modelarse mediante un orden débil. ^[3] En un ejemplo de la carrera de obstáculos de la Copa Maryland Hunt en 2007, The Bruce fue el claro ganador, pero dos caballos Bug River y Lear Charm empataron en el segundo lugar, con los caballos restantes más atrás; tres caballos no terminaron. ^[4] En el orden débil que describe este resultado, Bruce sería el primero, Bug River y Lear Charm se clasificarían después de The Bruce pero antes que todos los demás caballos que terminaron, y los tres caballos que no terminaron se colocarían en último lugar. el orden pero empatados entre sí.

Los puntos del plano euclidiano pueden ordenarse por su distancia al origen , dando otro ejemplo de ordenamiento débil con infinitos elementos, infinitos subconjuntos de elementos ligados (los conjuntos de puntos que pertenecen a un círculo común centrado en el origen) , e infinitos puntos dentro de estos subconjuntos. Aunque este ordenamiento tiene un elemento más pequeño (el origen mismo), no tiene ningún segundo elemento más pequeño ni ningún elemento más grande.

Las encuestas de opinión en elecciones políticas proporcionan un ejemplo de un tipo de ordenamiento que se asemeja a ordenamientos débiles, pero que se modela mejor matemáticamente de otras maneras. En los resultados de una encuesta, un candidato puede estar claramente por delante de otro, o los dos candidatos pueden estar empatados estadísticamente, lo que significa no que los resultados de su encuesta sean iguales sino más bien que están dentro del margen de error del otro. Sin embargo, si el candidato está estadísticamente empatado y está estadísticamente empatado, todavía es posible que sea claramente mejor que, por lo que estar empatado no es en este caso una relación transitiva . Debido a esta posibilidad, las clasificaciones de este tipo se modelan mejor como semiórdenes que como órdenes débiles. ^[5] ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z,}$

Axiomatizaciones

Supongamos que en todo eso hay una relación binaria homogénea en un conjunto (es decir, es un subconjunto de ) y, como de costumbre, escribe y dice que se cumple o es verdadera si y sólo si ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S\times S}$ ${\displaystyle x<y}$ ${\displaystyle x<y}$ ${\displaystyle (x,y)\in \,<.\,}$

Pedidos estrictos y débiles

Preliminares sobre incomparabilidad y transitividad de la incomparabilidad

Se dice que dos elementos y de son incomparables con respecto a si ni ni es verdadero. ^[1] Un orden parcial estricto es un ordenamiento débil estricto si y sólo si la incomparabilidad con respecto a es una relación de equivalencia . La incomparabilidad con respecto a es siempre una relación simétrica homogénea en Es reflexiva si y sólo si es irreflexiva (lo que significa que siempre es falsa), lo cual se asumirá de modo que la transitividad es la única propiedad que esta "relación de incomparabilidad" necesita para ser una relación de equivalencia . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S.}$ ${\displaystyle \,<\,}$ ${\displaystyle x<x}$

Defina también una relación homogénea inducida declarando que ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$

$${\displaystyle x\lesssim y{\text{ is true }}\quad {\text{ if and only if }}\quad y<x{\text{ is false}}}$$

noequivalentes-equivalenteexactamenteclase de equivalencia ${\displaystyle x\lesssim y}$ ${\displaystyle x<y{\text{ or }}x=y.}$ ${\displaystyle x,y\in S}$ ${\displaystyle \,<\,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle \,<}$ ${\displaystyle \,\lesssim }$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle S.}$ ${\displaystyle x,y\in S}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$

Definición

Un ordenamiento débil estricto en un conjunto es un orden parcial estricto en el cual la relación de incomparabilidad inducida por es una relación transitiva . ^[1] Explícitamente, un orden débil estricto es una relación homogénea que tiene las cuatro propiedades siguientes: ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$

1. Irreflexividad : Para todosno es cierto que ${\displaystyle x\in S,}$ ${\displaystyle x<x.}$
   • Esta condición se cumple si y sólo si la relación inducida en es reflexiva , donde se define declarando que es verdadera si y sólo si es falsa . ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$
2. Transitividad : Para todossientonces ${\displaystyle x,y,z\in S,}$ ${\displaystyle x<y{\text{ and }}y<z}$ ${\displaystyle x<z.}$
3. Asimetría : para todos,sies verdadero, entonceses falso. ${\displaystyle x,y\in S,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$
4. Transitividad de incomparabilidad : Para todosies incomparable con(lo que significa que ninies verdadero) y sies incomparable conentonceses incomparable con ${\displaystyle x,y,z\in S,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z.}$
   • Dos elementos son incomparables con respecto a si y sólo si son equivalentes con respecto a la relación inducida (que por definición significa que ambos son verdaderos), mientras que como antes, se declara verdadero si y sólo si es falso. Por lo tanto, esta condición se cumple si y sólo si la relación simétrica definida por " son equivalentes con respecto a " es una relación transitiva, lo que significa que siempre que sean -equivalentes y también sean -equivalentes, entonces necesariamente son -equivalentes. Esto también se puede reformular como: siempre y también entonces necesariamente ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$ ${\displaystyle S}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim }$ ${\displaystyle y{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$ ${\displaystyle x\lesssim z{\text{ and }}z\lesssim x.}$

Las propiedades (1), (2) y (3) son las propiedades definitorias de un orden parcial estricto, aunque hay cierta redundancia en esta lista ya que la asimetría (3) implica irreflexividad (1), y también porque la irreflexividad (1) y La transitividad (2) en conjunto implica asimetría (3). ^[6] La relación de incomparabilidad es siempre simétrica y será reflexiva si y sólo si es una relación irreflexiva (que se asume en la definición anterior). En consecuencia, un orden parcial estricto es un orden débil estricto si y sólo si su relación de incomparabilidad inducida es una relación de equivalencia . En este caso, sus clases de equivalencia se dividen y además, el conjunto de estas clases de equivalencia puede estar estrictamente ordenado en su totalidad mediante una relación binaria , también denotada por que está definida para todos por: ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \,<,}$ ${\displaystyle A,B\in {\mathcal {P}}}$

${\displaystyle A<B{\text{ if and only if }}a<b}$para algunos (o equivalentemente, para todos) los representantes ${\displaystyle a\in A{\text{ and }}b\in B.}$

Por el contrario, cualquier orden total estricto en una partición de da lugar a un ordenamiento débil estricto definido por si y sólo si existen conjuntos en esta partición tales que ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle a<b}$ ${\displaystyle A,B\in {\mathcal {P}}}$ ${\displaystyle a\in A,b\in B,{\text{ and }}A<B.}$

No todo orden parcial obedece a la ley transitiva de incomparabilidad. Por ejemplo, considere el orden parcial en el conjunto definido por la relación. Los pares son incomparables pero y están relacionados, por lo que la incomparabilidad no forma una relación de equivalencia y este ejemplo no es un ordenamiento débil estricto. ${\displaystyle \{a,b,c\}}$ ${\displaystyle b<c.}$ ${\displaystyle a,b{\text{ and }}a,c}$ ${\displaystyle b}$ ${\displaystyle c}$

Para la transitividad de la incomparabilidad, cada una de las siguientes condiciones es necesaria , y para órdenes parciales estrictas también es suficiente :

• Si entonces para todos uno o ambos. ${\displaystyle x<y}$ ${\displaystyle z,}$ ${\displaystyle x<z{\text{ or }}z<y}$
• Si es incomparable con entonces para todos , ya sea ( ) o ( ) o ( es incomparable con y es incomparable con ). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x<z{\text{ and }}y<z}$ ${\displaystyle z<x{\text{ and }}z<y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle y}$

Total de pedidos anticipados

Los pedidos débiles estrictos están muy relacionados con los pedidos anticipados totales o los pedidos débiles (no estrictos) , y los mismos conceptos matemáticos que se pueden modelar con pedidos débiles estrictos se pueden modelar igualmente bien con los pedidos anticipados totales. Un pedido anticipado total o un pedido débil es un pedido anticipado en el que dos elementos cualesquiera son comparables. ^[7] Un pedido anticipado total satisface las siguientes propiedades: ${\displaystyle \,\lesssim \,}$

• Transitividad : Para todos si entonces ${\displaystyle x,y,{\text{ and }}z,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$ ${\displaystyle x\lesssim z.}$
• Conexión fuerte : para todos ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • Lo que implica reflexividad : para todos. ${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

Un orden total es un preorden total que es antisimétrico, es decir, que también es un orden parcial . Los pedidos anticipados totales a veces también se denominan relaciones de preferencia .

El complemento de un orden débil estricto es un preorden total, y viceversa, pero parece más natural relacionar los órdenes débiles estrictos y los preorden totales de una manera que preserve, en lugar de invertir, el orden de los elementos. Por lo tanto, tomamos lo contrario del complemento: para un ordenamiento débil estricto, definir un preorden total estableciendo siempre que no sea el caso que En la otra dirección, definir un ordenamiento débil estricto < a partir de un preorden total establecido siempre que no sea el caso que ^[8] ${\displaystyle \,<,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x.}$ ${\displaystyle \,\lesssim ,}$ ${\displaystyle x<y}$ ${\displaystyle y\lesssim x.}$

En cualquier pedido anticipado existe una relación de equivalencia correspondiente donde dos elementos y se definen como equivalentes si. En el caso de un pedido anticipado total , el orden parcial correspondiente en el conjunto de clases de equivalencia es un pedido total. Dos elementos son equivalentes en un preorden total si y sólo si son incomparables en el orden débil estricto correspondiente. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

Particiones ordenadas

Una partición de un conjunto es una familia de subconjuntos disjuntos no vacíos de que tienen como unión. Una partición, junto con un orden total en los conjuntos de la partición, da una estructura llamada por Richard P. Stanley partición ordenada ^[9] y por Theodore Motzkin una lista de conjuntos . ^[10] Una partición ordenada de un conjunto finito puede escribirse como una secuencia finita de los conjuntos en la partición: por ejemplo, las tres particiones ordenadas del conjunto son ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \{a,b\}}$

$${\displaystyle \{a\},\{b\},}$$

$${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$

$${\displaystyle \{a,b\}.}$$

En un ordenamiento débil estricto, las clases de equivalencia de incomparabilidad dan una partición de conjuntos, en la que los conjuntos heredan un ordenamiento total de sus elementos, dando lugar a una partición ordenada. En la otra dirección, cualquier partición ordenada da lugar a un ordenamiento débil estricto en el que dos elementos son incomparables cuando pertenecen al mismo conjunto en la partición y, en caso contrario, heredan el orden de los conjuntos que los contienen.

Representación por funciones

Para conjuntos de cardinalidad suficientemente pequeña , es posible una cuarta axiomatización, basada en funciones de valor real. Si hay algún conjunto, entonces una función de valor real induce un orden débil estricto al establecer ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$ ${\displaystyle X}$ ${\displaystyle X}$

$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$

${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

Las relaciones no cambian cuando se reemplaza por ( función compuesta ), donde hay una función de valor real estrictamente creciente definida en al menos el rango de Así, por ejemplo, una función de utilidad define una relación de preferencia . En este contexto, los pedidos débiles también se conocen como acuerdos preferenciales . ^[11] ${\displaystyle f}$ ${\displaystyle g\circ f}$ ${\displaystyle g}$ ${\displaystyle f.}$

Si es finito o contable, cada orden débil puede representarse mediante una función de esta manera. ^[12] Sin embargo, existen órdenes débiles estrictas que no tienen una función real correspondiente. Por ejemplo, no existe tal función para el orden lexicográfico. Por lo tanto, mientras que en la mayoría de los modelos de relaciones de preferencia la relación define una función de utilidad hasta las transformaciones que preservan el orden, no existe tal función para las preferencias lexicográficas . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{n}.}$

De manera más general, si es un conjunto, es un conjunto con un ordenamiento débil estricto y es una función, entonces induce un ordenamiento débil estricto al establecer ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \,<,\,}$ ${\displaystyle f:X\to Y}$ ${\displaystyle f}$ ${\displaystyle X}$

$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$

función inyectivafunción sobreyectiva ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y.}$ ${\displaystyle X}$ ${\displaystyle Y.}$

Tipos de pedidos relacionados

Los semiórdenes generalizan ordenamientos débiles estrictos, pero no asumen transitividad de incomparabilidad. ^[13] Un orden débil estricto que es tricotómico se llama orden total estricto . ^[14] El preorden total que es el inverso de su complemento es en este caso un orden total .

Para un orden débil estricto, otra relación reflexiva asociada es su cierre reflexivo , un orden parcial (no estricto). Las dos relaciones reflexivas asociadas difieren con respecto a diferentes y para las cuales ni ni : en el preorden total correspondiente a un orden débil estricto obtenemos y mientras que en el orden parcial dado por la clausura reflexiva no obtenemos ni ni. Para órdenes totales estrictos estas dos relaciones reflexivas asociadas son las mismas: el orden total correspondiente (no estricto). ^[14] El cierre reflexivo de un ordenamiento débil estricto es un tipo de orden parcial serie-paralelo . ${\displaystyle \,<\,}$ ${\displaystyle \,\leq .}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a,}$ ${\displaystyle a\leq b}$ ${\displaystyle b\leq a.}$

Todos los pedidos débiles en un conjunto finito

enumeración combinatoria

El número de órdenes débiles distintas (representadas como órdenes débiles estrictas o como pedidos anticipados totales) en un conjunto de elementos viene dada por la siguiente secuencia (secuencia A000670 en el OEIS ): ${\displaystyle n}$

Tenga en cuenta que S ( n , k ) se refiere a los números de Stirling del segundo tipo .

Estos números también se denominan números de Fubini o números ordenados de Bell .

Por ejemplo, para un conjunto de tres elementos etiquetados, hay un orden débil en el que los tres elementos están empatados. Hay tres formas de dividir los elementos en un conjunto singleton y un grupo de dos elementos empatados, y cada una de estas particiones da dos órdenes débiles (una en la que el singleton es más pequeño que el grupo de dos y otra en la que este orden es invertido), dando seis órdenes débiles de este tipo. Y hay una única forma de dividir el conjunto en tres singletons, que se pueden ordenar totalmente de seis maneras diferentes. Así, en total, hay 13 órdenes débiles diferentes en tres artículos.

Estructura de adyacencia

El permutoedro de cuatro elementos, un poliedro convexo tridimensional . Tiene 24 vértices, 36 aristas y 14 caras bidimensionales, que, junto con todo el poliedro tridimensional, corresponden a los 75 ordenamientos débiles de cuatro elementos.

A diferencia de los órdenes parciales, la familia de ordenamientos débiles en un conjunto finito dado no está generalmente conectada por movimientos que agregan o eliminan una relación de orden única hacia o desde un ordenamiento dado. Por ejemplo, para tres elementos, el orden en el que están vinculados los tres elementos difiere en al menos dos pares de cualquier otro ordenamiento débil en el mismo conjunto, ya sea en el ordenamiento débil estricto o en las axiomatizaciones totales de preorden. Sin embargo, es posible un tipo diferente de movimiento, en el que los ordenamientos débiles de un conjunto están más conectados. Defina una dicotomía como un ordenamiento débil con dos clases de equivalencia y defina una dicotomía para que sea compatible con un ordenamiento débil dado si cada dos elementos que están relacionados en el ordenamiento están relacionados de la misma manera o vinculados en la dicotomía. Alternativamente, una dicotomía puede definirse como un corte de Dedekind para un orden débil. Entonces, un ordenamiento débil puede caracterizarse por su conjunto de dicotomías compatibles. Para un conjunto finito de elementos etiquetados, cada par de ordenamientos débiles pueden estar conectados entre sí mediante una secuencia de movimientos que agregan o eliminan una dicotomía a la vez hacia o desde este conjunto de dicotomías. Además, el grafo no dirigido que tiene los ordenamientos débiles como vértices y estos movimientos como aristas, forma un cubo parcial . ^[15]

Geométricamente, los ordenamientos totales de un conjunto finito dado pueden representarse como los vértices de un permutoedro , y las dicotomías de este mismo conjunto como las facetas del permutoedro. En esta representación geométrica, los ordenamientos débiles del conjunto corresponden a las caras de todas las diferentes dimensiones del permutoedro (incluido el permutoedro en sí, pero no el conjunto vacío, como una cara). La codimensión de una cara da el número de clases de equivalencia en el orden débil correspondiente. ^[16] En esta representación geométrica, el cubo parcial de movimientos en ordenamientos débiles es el gráfico que describe la relación de cobertura de la red de caras del permutoedro.

Por ejemplo, el permutoedro de tres elementos es simplemente un hexágono regular. La red de caras del hexágono (nuevamente, incluyendo el hexágono mismo como una cara, pero sin incluir el conjunto vacío) tiene trece elementos: un hexágono, seis aristas y seis vértices, correspondientes al orden débil completamente vinculado, seis ordenamientos débiles. con un empate y seis pedidos en total. En la figura se muestra el gráfico de movimientos en estos 13 ordenamientos débiles. ${\displaystyle n=3,}$

Aplicaciones

Como se mencionó anteriormente, los órdenes débiles tienen aplicaciones en la teoría de la utilidad. ^[12] En programación lineal y otros tipos de problemas de optimización combinatoria , la priorización de soluciones o de bases suele estar dada por un orden débil, determinado por una función objetivo de valor real ; El fenómeno de los vínculos en estos ordenamientos se llama "degeneración", y se han utilizado varios tipos de reglas de desempate para refinar este ordenamiento débil y convertirlo en un ordenamiento total con el fin de prevenir problemas causados ​​por la degeneración. ^[17]

Los órdenes débiles también se han utilizado en informática , en algoritmos basados ​​en refinamiento de particiones para búsqueda lexicográfica en amplitud y ordenamiento topológico lexicográfico . En estos algoritmos, un orden débil en los vértices de un gráfico (representado como una familia de conjuntos que dividen los vértices, junto con una lista doblemente enlazada que proporciona un orden total en los conjuntos) se refina gradualmente a lo largo del algoritmo, eventualmente produciendo un orden total que es el resultado del algoritmo. ^[18]

En la biblioteca estándar para el lenguaje de programación C++ , los tipos de datos set y multiset clasifican su entrada mediante una función de comparación que se especifica en el momento de la creación de instancias de la plantilla y que se supone que implementa un ordenamiento débil estricto. ^[2]

Ver también

• Comparabilidad  – Propiedad de elementos relacionados por desigualdades
• Preorden  - Relación binaria reflexiva y transitiva
• Componente débil  : partición de vértices de un gráfico dirigido: los subconjuntos equivalentes en el orden débil más fino consistente con una relación dada

Referencias

1. Roberts, Fred; Tesman, Barry (2011), Combinatoria aplicada (2ª ed.), CRC Press, Sección 4.2.4 Órdenes débiles, págs. 254–256, ISBN 9781420099836.
2. Josuttis, Nicolai M. (2012), La biblioteca estándar de C++: tutorial y referencia, Addison-Wesley, p. 469, ISBN 9780132977739.
3. de Koninck, JM (2009), Esos números fascinantes, Sociedad Matemática Estadounidense, p. 4, ISBN 9780821886311.
4. Baker, Kent (29 de abril de 2007), "The Bruce aguanta la victoria en la Copa Hunt: Bug River, Lear Charm terminan empatados por el segundo", The Baltimore Sun , archivado desde el original el 29 de marzo de 2015.
5. Regenwetter, Michel (2006), Elección social conductual: modelos probabilísticos, inferencia estadística y aplicaciones, Cambridge University Press, págs. 113 y siguientes, ISBN 9780521536660.
6. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007), Cierres transitivos de relaciones binarias I (PDF) , Praga: Facultad de Matemáticas - Universidad Carolina de Física, p. 1, S2CID  47676001, archivado desde el original (PDF) el 6 de abril de 2018, Lema 1.1 (iv). Tenga en cuenta que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
7. Esta relación también se llama fuertemente conectada .
8. Ehrgott, Matthias (2005), Optimización multicriterio, Springer, Proposición 1.9, p. 10, ISBN 9783540276593.
9. Stanley, Richard P. (1997), Combinatoria enumerativa, vol. 2 , Estudios de Cambridge en Matemáticas Avanzadas, vol. 62, Cambridge University Press, pág. 297.
10. Motzkin, Theodore S. (1971), "Clasificación de números para cilindros y otros números de clasificación", Combinatoria (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Ángeles, California, 1968) , Providence, RI: América. Matemáticas. Soc., págs. 167-176, SEÑOR  0332508.
11. Gross, OA (1962), "Acuerdos preferenciales", The American Mathematical Monthly , 69 (1): 4–8, doi :10.2307/2312725, JSTOR  2312725, MR  0130837.
12. Roberts, Fred S. (1979), Teoría de la medición, con aplicaciones a la toma de decisiones, la utilidad y las ciencias sociales , Enciclopedia de las matemáticas y sus aplicaciones, vol. 7, Addison-Wesley, Teorema 3.1, ISBN 978-0-201-13506-0.
13. Luce, R. Duncan (1956), "Semiórdenes y una teoría de la discriminación de utilidad" (PDF) , Econometrica , 24 (2): 178–191, doi :10.2307/1905751, JSTOR  1905751, MR  0078632.
14. Velleman, Daniel J. (2006), Cómo demostrarlo: un enfoque estructurado, Cambridge University Press, p. 204, ISBN 9780521675994.
15. Eppstein, David ; Falmagne, Jean-Claude ; Ovchinnikov, Sergei (2008), Teoría de los medios: matemáticas aplicadas interdisciplinarias , Springer, sección 9.4, Órdenes débiles y complejos cúbicos, págs..
16. Ziegler, Günter M. (1995), Conferencias sobre politopos , Textos de posgrado en matemáticas, vol. 152, Springer, pág. 18.
17. Chvátal, Vašek (1983), Programación lineal, Macmillan, págs. 29–38, ISBN 9780716715870.
18. Habib, Michel; Pablo, Christophe; Viennot, Laurent (1999), "Técnicas de refinamiento de particiones: un interesante conjunto de herramientas algorítmicas", Revista Internacional de Fundamentos de Ciencias de la Computación , 10 (2): 147–170, doi :10.1142/S0129054199000125, MR  1759929.