Ordenamiento lexicográfico - posets vs preorders

Question

Encontré la siguiente definición de ordenación lexicográfica en Wikipedia (y definiciones similares en otros lugares):

Dados dos conjuntos parcialmente ordenados $A$ y $B$ el orden lexicográfico en el producto cartesiano $A \times B$ se define como $(a,b) \le (a',b')$ si y sólo si $a < a'$ o ( $a = a'$ y $b \le b'$ ). El resultado es una orden parcial. Si $A$ y $B$ están totalmente ordenados, entonces el resultado es un orden total también.

¿Esta definición funciona igualmente bien si $A$ y $B$ ¿son preordenados, en lugar de posets? En otras palabras, ¿la propiedad antisimétrica de las relaciones de ordenación en A y B supone alguna diferencia en este caso?

Answer 1

Sí, si $\langle A,\le_A\rangle$ y $\langle B,\le_B\rangle$ son preórdenes, la misma construcción produce una preorden $\langle A\times B,\preceq\rangle$ . En concreto, para $\langle a,b\rangle,\langle c,d\rangle\in A\times B$ definir $\langle a,b\rangle\preceq \langle c,d\rangle$ si $a<_A c$ o $a\le_A c$ y $b\le_B d$ . Claramente $\preceq$ es reflexivo, por lo que sólo hay que comprobar que es transitivo.

Añadido: Debería haber dicho explícitamente lo que quiero decir con $a<_A c$ para el pre-pedido $\le_A$ . I no significa que $a\le_A c$ y $a\ne c$ . Más bien, quiero decir que $a\le_A c$ y $c\not\le_A a$ . Equivalentemente, quiero decir que $a\le_A c$ y $a\not\sim_A c$ , donde $a\sim_A c$ si $a\le_A c$ y $c\le_A a$ . Aquí $\sim_A$ es la relación de equivalencia en $A$ cuyas clases de equivalencia son conjuntos de $\le_A$ -miembros indistinguibles de $A$ y la relación inducida en $A/\sim_A$ por $\le_A$ es un orden parcial. La cuestión es que si $a\sim_A a'$ Quiero tratar $a$ y $a'$ exactamente iguales.

Si se tratara de pedidos parciales $\le_A$ y $\le_B$ Podría definir $\langle a,b\rangle\preceq \langle c,d\rangle$ si $a<_A c$ o $a=c$ y $b\le_B d$ utilizando la definición habitual de orden lexicográfico. Nótese, sin embargo, que para los órdenes parciales esa definición es equivalente a decir que $\langle a,b\rangle\preceq \langle c,d\rangle$ si $a<_A c$ o $a\le_A c$ y $b\le_B d$ : si $\langle a,b\rangle\preceq \langle c,d\rangle$ según esta última definición, entonces $a<_A c$ , en cuyo caso $\langle a,b\rangle\preceq \langle c,d\rangle$ por la definición habitual también, o $a\le_A c$ , $a\not<_A c$ y $b\le_B d$ , en cuyo caso $a=c$ y $b\le_B d$ , y de nuevo $\langle a,b\rangle\preceq \langle c,d\rangle$ según la definición habitual. En el caso de los preórdenes no son equivalentes, porque un preorden no tiene por qué ser antisimétrico. En el caso de los preórdenes, la formulación equivalente es la siguiente $\langle a,b\rangle\preceq \langle c,d\rangle$ si $a<_A c$ o $a\sim_A c$ y $b\le_B d$ .

Para ello supongamos que $\langle a,b\rangle\preceq\langle c,d\rangle\preceq\langle e,f\rangle$ claramente $a\le_A c\le_A e$ . Si cualquiera de los dos $a<_A c$ o $c<_A e$ entonces $a<_A e$ y $\langle a,b\rangle\preceq\langle e,f\rangle$ . De lo contrario, tenemos $b\le_B d$ y $d\le_B f$ Así que $b\le_B f$ , y de nuevo $\langle a,b\rangle\preceq\langle e,f\rangle$ .