orden débil

Preliminares sobre la incomparabilidad y la transitividad de la incomparabilidad

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

Defina también una relación homogénea inducida.${\displaystyle \,\lesssim \,}$en${\displaystyle S}$declarando que $${\displaystyle x\lesssim y{\text{ es verdadero }}\quad {\text{ si y solo si }}\quad y<x{\text{ es falso}}}$$ donde, es importante destacar, esta definición no es necesariamente la misma que:${\displaystyle x\lesssim y}$si y solo si${\displaystyle x<y{\text{ o }}x=y.}$ Dos elementos${\displaystyle x,y\in S}$son incomparables con respecto a${\displaystyle \,<\,}$si y solo si${\displaystyle x{\text{ y }}y}$son equivalentes con respecto a${\displaystyle \,\lesssim \,}$(o de forma menos prolija,${\displaystyle \,\lesssim }$-equivalente ), lo que por definición significa que ambos${\displaystyle x\lesssim y{\text{ y }}y\lesssim x}$son verdaderas. La relación "son incomparables con respecto a${\displaystyle \,<}$" es por lo tanto idéntico a (es decir, igual a) la relación "son${\displaystyle \,\lesssim }$-equivalente" (por lo que, en particular, el primero es transitivo si y solo si el segundo lo es). Cuando${\displaystyle \,<\,}$es irreflexiva entonces la propiedad conocida como " transitividad de la incomparabilidad " (definida más adelante) es exactamente la condición necesaria y suficiente para garantizar que la relación "son${\displaystyle \,\lesssim }$-equivalente" sí que forma una relación de equivalencia en${\displaystyle S.}$ Cuando esto ocurre, permite cualquier par de elementos.${\displaystyle x,y\in S}$satisfactorio${\displaystyle x\lesssim y{\text{ y }}y\lesssim x}$ser identificados como un solo objeto (específicamente, se identifican juntos en su clase de equivalencia común ).

Definición

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

1. Irreflexividad : Para todos${\displaystyle x\in S,}$No es cierto que${\displaystyle x<x.}$
   • Esta condición se cumple si y solo si la relación inducida${\displaystyle \,\lesssim \,}$en${\displaystyle S}$es reflexivo , donde${\displaystyle \,\lesssim \,}$se define declarando que${\displaystyle x\lesssim y}$es cierto si y solo si${\displaystyle y<x}$es falso .
2. Transitividad : Para todos${\displaystyle x,y,z\in S,}$si${\displaystyle x<y{\text{ y }}y<z}$entonces${\displaystyle x<z.}$
3. Asimetría : Para todos${\displaystyle x,y\in S,}$si${\displaystyle x<y}$entonces es cierto${\displaystyle y<x}$es falso.
4. Transitividad de la incomparabilidad : Para todos${\displaystyle x,y,z\in S,}$si${\displaystyle x}$es incomparable con${\displaystyle y}$(lo que significa que ninguno${\displaystyle x<y}$ni${\displaystyle y<x}$es cierto) y si${\displaystyle y}$es incomparable con${\displaystyle z,}$entonces${\displaystyle x}$es incomparable con${\displaystyle z.}$
   • Dos elementos${\displaystyle x{\text{ y }}y}$son incomparables con respecto a${\displaystyle \,<\,}$si y solo si son equivalentes con respecto a la relación inducida${\displaystyle \,\lesssim \,}$(lo que por definición significa que${\displaystyle x\lesssim y{\text{ y }}y\lesssim x}$ambas son ciertas), mientras que, como antes,${\displaystyle x\lesssim y}$se declara verdadero si y solo si${\displaystyle y<x}$es falso. Por lo tanto, esta condición se cumple si y solo si la relación simétrica en${\displaystyle S}$definido por "${\displaystyle x{\text{ y }}y}$son equivalentes con respecto a${\displaystyle \,\lesssim \,}$" es una relación transitiva, lo que significa que siempre que${\displaystyle x{\text{ y }}y}$son${\displaystyle \,\lesssim }$-equivalente y también${\displaystyle y{\text{ y }}z}$son${\displaystyle \,\lesssim }$-equivalente entonces necesariamente${\displaystyle x{\text{ and }}z}$son${\displaystyle \,\lesssim }$-equivalente. Esto también se puede reformular como: siempre que${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$y también${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$entonces necesariamente${\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 existe 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) juntas implican asimetría (3). ^{[ 6 ]} La relación de incomparabilidad es siempre simétrica y será reflexiva si y solo si${\displaystyle \,<\,}$es una relación irreflexiva (lo cual se asume en la definición anterior). En consecuencia, un orden parcial estricto${\displaystyle \,<\,}$es un orden débil estricto si y solo si su relación de incomparabilidad inducida es una relación de equivalencia . En este caso, sus clases de equivalencia particionan.${\displaystyle S}$y además, el conjunto${\displaystyle {\mathcal {P}}}$de estas clases de equivalencia pueden ordenarse estrictamente por una relación binaria , también denotada por${\displaystyle \,<,}$que se define para todos${\displaystyle A,B\in {\mathcal {P}}}$por:

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

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

No todo orden parcial obedece la ley transitiva de incomparabilidad. Por ejemplo, consideremos el orden parcial en el conjunto${\displaystyle \{a,b,c\}}$definido por la relación${\displaystyle b<c.}$Las parejas${\displaystyle a,b{\text{ and }}a,c}$son incomparables pero${\displaystyle b}$y${\displaystyle c}$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.

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

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

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

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

Un orden total es un preorden total antisimétrico, es decir, también un orden parcial . Los preórdenes 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 preórdenes totales de una manera que preserve en lugar de invertir el orden de los elementos. Por lo tanto, tomamos el recíproco del complemento: para un orden débil estricto${\displaystyle \,<,}$definir un pedido anticipado total${\displaystyle \,\lesssim \,}$al establecer${\displaystyle x\lesssim y}$siempre que no sea el caso que${\displaystyle y<x.}$En la otra dirección, para definir un ordenamiento débil estricto < a partir de un preorden total${\displaystyle \,\lesssim ,}$colocar${\displaystyle x<y}$siempre que no sea el caso que${\displaystyle y\lesssim x.}$^{[ 8 ]}

En cualquier preorden hay una relación de equivalencia correspondiente donde dos elementos${\displaystyle x}$y${\displaystyle y}$se definen como equivalentes si${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$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 orden débil estricto correspondiente.

Una partición de un conjunto${\displaystyle S}$es una familia de subconjuntos disjuntos no vacíos de${\displaystyle S}$que tienen${\displaystyle S}$como su 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 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${\displaystyle \{a,b\}}$son $${\displaystyle \{a\},\{b\},}$$$${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$$${\displaystyle \{a,b\}.}$$

En un ordenamiento débil estricto, las clases de equivalencia de incomparabilidad dan lugar a una partición de conjuntos, en la que los conjuntos heredan un orden total de sus elementos, generando así una partición ordenada. En sentido contrario, 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.

Para conjuntos de cardinalidad suficientemente pequeña , es posible una cuarta axiomatización, basada en funciones de valor real. Si${\displaystyle X}$Si cualquier conjunto es una función de valor real${\displaystyle f:X\to \mathbb {R} }$en${\displaystyle X}$induce un orden débil estricto en${\displaystyle X}$al establecer $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ El preorden total asociado se obtiene mediante la configuración ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$ y la equivalencia asociada mediante el establecimiento ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

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

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

En términos más generales, si${\displaystyle X}$es un conjunto,${\displaystyle Y}$es un conjunto con un ordenamiento débil estricto${\displaystyle \,<,\,}$y${\displaystyle f:X\to Y}$es una función, entonces${\displaystyle f}$induce un ordenamiento débil estricto en${\displaystyle X}$al establecer $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ Como antes, el preorden total asociado se obtiene configurando ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$ y la equivalencia asociada mediante el establecimiento ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$ Aquí no se da por sentado que${\displaystyle f}$es una función inyectiva , por lo que una clase de dos elementos equivalentes en${\displaystyle Y}$puede inducir una clase más amplia de elementos equivalentes en${\displaystyle X.}$También,${\displaystyle f}$no se asume que sea una función sobreyectiva , por lo que una clase de elementos equivalentes en${\displaystyle Y}$puede inducir una clase más pequeña o vacía en${\displaystyle X.}$Sin embargo, la función${\displaystyle f}$induce una función inyectiva que mapea la partición en${\displaystyle X}$a eso en${\displaystyle Y.}$Así, en el caso de particiones finitas, el número de clases en${\displaystyle X}$es menor o igual al número de clases en${\displaystyle Y.}$

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

Nótese que S ( n , k ) se refiere a los números de Stirling de segundo tipo .

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

Por ejemplo, para un conjunto de tres elementos etiquetados, existe un orden débil en el que los tres elementos están empatados. Hay tres maneras de dividir los elementos en un conjunto de un solo elemento y un grupo de dos elementos empatados, y cada una de estas divisiones da lugar a dos órdenes débiles (uno en el que el conjunto de un solo elemento es menor que el grupo de dos, y otro en el que este orden se invierte), lo que da un total de seis órdenes débiles de este tipo. Además, existe una única manera de dividir el conjunto en tres conjuntos de un solo elemento, que pueden ordenarse de seis maneras diferentes. Por lo tanto, en total, existen 13 órdenes débiles diferentes para tres elementos.

A diferencia de los órdenes parciales, la familia de ordenaciones débiles en un conjunto finito dado no está conectada en general por movimientos que añaden o eliminan una única relación de orden a o de una ordenación dada. Por ejemplo, para tres elementos, la ordenación en la que los tres elementos están ligados difiere en al menos dos pares de cualquier otra ordenación débil en el mismo conjunto, ya sea en la ordenación débil estricta o en las axiomatizaciones de preorden total. Sin embargo, es posible otro tipo de movimiento, en el que las ordenaciones débiles en un conjunto están más altamente conectadas. Definimos una dicotomía como una ordenación débil con dos clases de equivalencia, y definimos una dicotomía como compatible con una ordenación débil dada si cada par de elementos que están relacionados en la ordenación están relacionados de la misma manera o ligados en la dicotomía. Alternativamente, una dicotomía puede definirse como un corte de Dedekind para una ordenación débil. Entonces, una ordenación débil puede caracterizarse por su conjunto de dicotomías compatibles. Para un conjunto finito de elementos etiquetados, cada par de ordenaciones débiles puede conectarse entre sí mediante una secuencia de movimientos que añaden o eliminan una dicotomía a la vez a o desde este conjunto de dicotomías. Además, el grafo no dirigido que tiene las ordenaciones 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 en 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 dimensiones diferentes del permutoedro (incluido el permutoedro mismo, 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 ordenamiento débil correspondiente. ^{[ 16 ]} En esta representación geométrica, el cubo parcial de movimientos en ordenamientos débiles es el grafo que describe la relación de recubrimiento de la red de caras del permutoedro.

Por ejemplo, para${\displaystyle n=3,}$El permutoedro de tres elementos es simplemente un hexágono regular. La red de caras del hexágono (incluyendo el hexágono mismo como cara, pero sin incluir el conjunto vacío) tiene trece elementos: un hexágono, seis aristas y seis vértices, que corresponden a un ordenamiento débil completamente empatado, seis ordenamientos débiles con un empate y seis ordenamientos totales. El grafo de movimientos en estos trece ordenamientos débiles se muestra en la figura.