Relaciones binarias | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila. Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. Todas las definiciones requieren tácitamente transitividad y reflexividad . |
En matemáticas , especialmente en la teoría del orden , un ordenamiento débil es una formalización matemática de la noción intuitiva de una clasificación de un conjunto , algunos de cuyos miembros pueden estar vinculados entre sí. Los órdenes débiles son una generalización de conjuntos totalmente ordenados (clasificaciones sin empates) y, a su vez, se generalizan mediante conjuntos parcialmente ordenados y preordenes . [1]
Hay varias formas comunes de formalizar ordenamientos débiles, que son diferentes entre sí pero criptomórficos (interconvertibles sin pérdida de información): pueden axiomatizarse como ordenamientos débiles estrictos (conjuntos parcialmente ordenados en los que la incomparabilidad es una relación transitiva ), como total preordenes (relaciones transitivas binarias en las que existe al menos una de las dos posibles relaciones 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 arreglo preferencial basado en una función de utilidad .
Los pedidos débiles se cuentan por 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 de
En las carreras de caballos , el uso de foto-acabados ha eliminado algunos, pero no todos, empates o (como se les llama en este contexto) eliminatorias , por lo que el resultado de una carrera de caballos puede ser modelado por un orden débil. [3] En un ejemplo de la carrera de obstáculos de la Maryland Hunt Cup 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, The Bruce sería el primero, Bug River y Lear Charm se clasificarían después de The Bruce pero antes de todos los otros caballos que terminaron, y los tres caballos que no terminaron se colocarían en último lugar. el orden pero atados entre sí.
Los puntos del plano euclidiano pueden ordenarse por su distancia desde el origen , dando otro ejemplo de un orden 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 orden 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 las elecciones políticas proporcionan un ejemplo de un tipo de ordenamiento que se asemeja a los 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 no significa que los resultados de la encuesta sean iguales, sino que están dentro del margen de error del otro. Sin embargo, si el candidato está estadísticamente relacionado con y está estadísticamente relacionado con todavía podría ser posible para ser claramente mejor que por lo que estar atado no es en este caso una relación transitiva . Debido a esta posibilidad, las clasificaciones de este tipo se modelan mejor como semiordenadores que como ordenamientos débiles. [5]
Axiomatizaciones
Supongamos que a lo largo de eso es una relación binaria homogénea en un conjunto (es decir, es un subconjunto de ) y como de costumbre, escribe y di eso se cumple o es cierto si y solo si
Órdenes estrictas y débiles
- Preliminares sobre incomparabilidad
Dos elementos y de se dice que son incomparables con respecto a si ninguno ni es verdad. [1] Incomparabilidad con respecto aes en sí misma una relación simétrica homogénea en Definir también una relación homogénea inducida en declarando que
- Definición
Un pedido estricto y débil en un set.es una orden parcial estricta en para lo cual la relación de incomparabilidad inducida en por es una relación transitiva . [1] Explícitamente, una estricta orden débil enes una relación homogénea en que tiene las cuatro propiedades siguientes:
- Irreflexividad : para todos no es cierto que
- Esta condición se cumple si y solo si la relación inducida en es reflexivo , donde se define declarando que es cierto si y solo si es falso .
- Transitividad : para todos Si y luego
- Asimetría : para todos Si es verdad entonces Es falso.
- Transitividad de la incomparabilidad : para todos Si es incomparable con (lo que significa que ni ni es cierto) y si es incomparable con luego es incomparable con
- Dos elementos y son incomparables con respecto a si y solo si son equivalentes con respecto a la relación inducida (que por definición significa que y son ambos verdaderos), donde como antes, se declara verdadero si y solo si Es falso. Por tanto, esta condición se cumple si y sólo si la relación simétrica en definido por " y son equivalentes con respecto a "es una relación transitiva.
Las propiedades (1), (2) y (3) son las propiedades definitorias de un orden parcial estricto, aunque esta lista de estas tres propiedades es algo redundante en que la asimetría implica irreflexividad, y en que la irreflexividad y la transitividad juntas implican asimetría. [6] La relación de incomparabilidad es siempre simétrica y será reflexiva si y solo sies una relación irreflexiva (que es asumida por la definición anterior). En consecuencia, una orden parcial estrictaes un orden débil estricto si y solo si su relación de incomparabilidad inducida es una relación de equivalencia . En este caso, su partición de clases de equivalencia y además, el set de estas clases de equivalencia pueden ser estrictamente ordenadas por una relación binaria , también denotada por que esta definido para todos por:
- si y solo si para algunos (o de manera equivalente, para todos) representantes y
Por el contrario, cualquier orden total estricta en una partición de da lugar a un estricto orden débil en definido por si y solo si existen conjuntos en esta partición tal que y
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 Las parejas y 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 orden débil estricto.
La transitividad de la incomparabilidad (junto con la transitividad) también puede expresarse en las siguientes formas:
- Si entonces para todos ya sea o o ambos.
O:
- Si es incomparable con entonces para todos ya sea ( y ) o ( y ) o ( es incomparable con y es incomparable con ).
Total de pedidos por adelantado
Los órdenes 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 ordenamientos 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 por adelantado total satisface las siguientes propiedades:
- Para todos y Si y luego (transitividad).
- Para todos y o (fuerte conexión).
- Por lo tanto, para todos (reflexividad).
Un pedido total es un preorden total que es antisimétrico, es decir, que también es un pedido parcial . Los pedidos anticipados totales a veces también se denominan relaciones de preferencia .
El complemento de un orden estrictamente débil es un preorden total, y viceversa, pero parece más natural relacionar los órdenes estrictos débiles y los preordenes totales de una manera que preserva en lugar de revertir el orden de los elementos. Por lo tanto, tomamos la inversa del complemento: para un orden débil estricto <, defina un preorden total configurando siempre que no sea el caso que En la otra dirección, para definir un orden débil estricto
En cualquier preorden hay una relación de equivalencia correspondiente donde dos elementos y se definen como equivalentes si y En el caso de un preorden total, el orden parcial correspondiente en el conjunto de clases de equivalencia es un orden total. Dos elementos son equivalentes en un preorden total si y solo si son incomparables en el correspondiente orden estricto débil.
Particiones ordenadas
Una partición de un conjunto es una familia de subconjuntos disjuntos no vacíos de eso tiene como su unión. Una partición, junto con un orden total de los conjuntos de la partición, da una estructura llamada por Richard P. Stanley una 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 están
- y
En un estricto ordenamiento débil, 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 orden estrictamente débil en el que dos elementos son incomparables cuando pertenecen al mismo conjunto en la partición y, de lo contrario, heredan el orden de los conjuntos que los contienen.
Representación por funciones
Para conjuntos de cardinalidad suficientemente pequeña , es posible una tercera axiomatización, basada en funciones de valor real. Si es cualquier conjunto, entonces una función de valor real en induce un estricto orden débil en configurando si y solo si El pedido anticipado total asociado se da configurando si y solo si y la equivalencia asociada estableciendo si y solo si
Las relaciones no cambian cuando es reemplazado por ( función compuesta ), dondees una función de valor real estrictamente creciente definida en al menos el rango deAsí, 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]
Si es finito o contable, cada orden débil en se puede representar 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 enAsí, mientras que en la mayoría de los modelos de relación de preferencias la relación define una función de utilidad hasta transformaciones que preservan el orden, no existe tal función para las preferencias lexicográficas .
De manera más general, si es un conjunto, es un conjunto con un estricto orden débil y es una función, entonces induce un estricto orden débil en configurando si y solo si Como antes, el pedido anticipado total asociado se da configurando si y solo si y la equivalencia asociada estableciendo si y solo si No se asume aquí que es una función inyectiva , por lo que una clase de dos elementos equivalentes en puede inducir una clase mayor de elementos equivalentes en También, no se supone que sea una función sobreyectiva , por lo que una clase de elementos equivalentes en puede inducir una clase más pequeña o vacía en Sin embargo, la función induce una función inyectiva que mapea la partición en a eso en Así, en el caso de particiones finitas, el número de clases en es menor o igual que el número de clases en
Tipos relacionados de pedidos
Los semiordenadores generalizan ordenamientos débiles estrictos, pero no asumen una transitividad de incomparabilidad. [13] Un orden débil estricto que es tricotómico se denomina orden total estricto . [14] El preorden total que es el inverso de su complemento es en este caso un orden total .
Por un estricto orden débil 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 por lo cual ni ni : en el total de preorden correspondiente a un estricto orden débil obtenemos y mientras que en el orden parcial dado por el cierre reflexivo 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 orden débil estricto es un tipo de orden parcial serie-paralelo .
Todas las órdenes 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 preordenes totales) en un -el conjunto de elementos viene dado por la siguiente secuencia (secuencia A000670 en la OEIS ):
Elementos | Alguna | Transitivo | Reflexivo | Hacer un pedido | Orden parcial | Reserva total | Orden total | Relación de equivalencia |
---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | dieciséis | 13 | 4 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3.994 | 4.096 | 355 | 219 | 75 | 24 | 15 |
norte | 2 n 2 | 2 n 2 - n | ∑n k = 0 k ! S ( n , k ) | n ! | ∑n k = 0 S ( n , k ) | |||
OEIS | A002416 | A006905 | A053763 | A000798 | A001035 | A000670 | A000142 | A000110 |
Estos números también se denominan números de Fubini o números de Bell ordenados .
Por ejemplo, para un conjunto de tres elementos etiquetados, hay un orden débil en el que los tres elementos están vinculados. Hay tres formas de dividir los elementos en un conjunto singleton y un grupo de dos elementos vinculados, 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 invertida), 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 formas diferentes. Por lo tanto, en total, hay 13 órdenes débiles diferentes en tres elementos.
Estructura de adyacencia
A diferencia de los órdenes parciales, la familia de ordenamientos débiles en un conjunto finito dado no está, en general, conectada por movimientos que agregan o eliminan una relación de un solo orden hacia o desde un ordenamiento dado. Por ejemplo, para tres elementos, el orden en el que los tres elementos están vinculados difiere en al menos dos pares de cualquier otro orden débil en el mismo conjunto, ya sea en el orden 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 para que sea 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 se mueven 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 en el 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 correspondiente orden débil. [16] En esta representación geométrica, el cubo parcial de movimientos en órdenes débiles es el gráfico que describe la relación de cobertura de la red de caras del permutoedro.
Por ejemplo, para el permutoedro en tres elementos es solo un hexágono regular. La celosía 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 ligado, seis ordenamientos débiles con una corbata y seis pedidos en total. El gráfico de movimientos en estos 13 ordenamientos débiles se muestra en la figura.
Aplicaciones
Como se mencionó anteriormente, los pedidos débiles tienen aplicaciones en la teoría de la utilidad. [12] En la 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 lazos en estos ordenamientos se llama "degeneración", y se han utilizado varios tipos de reglas de desempate para refinar este ordenamiento débil 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 ciencias de la computación , en algoritmos basados en el 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 particionan 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 ordenamiento total que es el resultado del algoritmo. [18]
En la biblioteca estándar para el lenguaje de programación C ++ , los tipos de datos de conjuntos y conjuntos múltiples clasifican su entrada mediante una función de comparación que se especifica en el momento de la instanciación de la plantilla, y que se supone que implementa un orden débil estricto. [2]
Ver también
- Comparabilidad
- Preordenar - Relación binaria reflexiva y transitiva
Referencias
- ^ a b c Roberts, Fred; Tesman, Barry (2011), Applied Combinatorics (2ª ed.), CRC Press, Sección 4.2.4 Órdenes débiles, págs. 254-256, ISBN 9781420099836.
- ^ a b Josuttis, Nicolai M. (2012), The C ++ Standard Library: A Tutorial and Reference , Addison-Wesley, p. 469, ISBN 9780132977739.
- ^ de Koninck, JM (2009), Esos números fascinantes , American Mathematical Society, p. 4, ISBN 9780821886311.
- ^ Baker, Kent (29 de abril de 2007), "The Bruce espera la victoria de la Hunt Cup: Bug River, Lear Charm termina empatado por el segundo" , The Baltimore Sun , archivado desde el original el 29 de marzo de 2015.
- ^ 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.
- ^ Flaška, V .; Ježek, J .; Kepka, T .; Kortelainen, J. (2007), Cierres transitivos de relaciones binarias I (PDF) , Praga: Escuela de Matemáticas - Física Universidad Charles, p. 1, S2CID 47676001 , archivado desde el original (PDF) el 2018-04-06, Lema 1.1 (iv). Tenga en cuenta que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
- ^ Esta relación también se llama fuertemente conectada .
- ^ Ehrgott, Matthias (2005), Optimización multicriterio , Springer, Proposición 1.9, p. 10, ISBN 9783540276593.
- ^ Stanley, Richard P. (1997), Combinatoria enumerativa, vol. 2 , Cambridge Studies in Advanced Mathematics, 62 , Cambridge University Press, pág. 297.
- ^ 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 : Amer. Matemáticas. Soc., Págs. 167-176, MR 0332508.
- ^ Gross, OA (1962), "Arreglos preferenciales", The American Mathematical Monthly , 69 (1): 4–8, doi : 10.2307 / 2312725 , JSTOR 2312725 , MR 0130837.
- ^ a b 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, 7 , Addison-Wesley, Teorema 3.1 , ISBN 978-0-201-13506-0.
- ^ Luce, R. Duncan (1956), "Semiorders y una teoría de la discriminación de la utilidad" (PDF) , Econometrica , 24 (2): 178-191, doi : 10.2307 / 1905751 , JSTOR 1905751 , MR 0078632.
- ^ a b Velleman, Daniel J. (2006), Cómo probarlo: un enfoque estructurado , Cambridge University Press, p. 204, ISBN 9780521675994.
- ^ 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. 188-196.
- ^ Ziegler, Günter M. (1995), Conferencias sobre politopos , Textos de posgrado en matemáticas, 152 , Springer, p. 18.
- ^ Chvátal, Vašek (1983), Programación lineal , Macmillan, págs. 29–38, ISBN 9780716715870.
- ^ Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Técnicas de refinamiento de particiones: un interesante conjunto de herramientas algorítmicas", International Journal of Foundations of Computer Science , 10 (2): 147-170, doi : 10.1142 / S0129054199000125 , MR 1759929.