Semiorden

Ordenamiento numérico con margen de error

Diagrama de Hasse de un semiorden. Dos elementos son comparables cuando sus coordenadas verticales difieren en al menos una unidad (el espacio entre las líneas azules continuas).

En la teoría del orden , una rama de las matemáticas, un semiorden es un tipo de ordenación para ítems con puntuaciones numéricas, donde los ítems con puntuaciones muy diferentes se comparan por sus puntuaciones y donde las puntuaciones dentro de un margen de error dado se consideran incomparables . Los semiórdenes fueron introducidos y aplicados en psicología matemática por Duncan Luce  (1956) como un modelo de preferencia humana. Generalizan los ordenamientos débiles estrictos , en los que los ítems con puntuaciones iguales pueden estar empatados pero no hay margen de error. Son un caso especial de órdenes parciales y de órdenes de intervalo , y pueden caracterizarse entre los órdenes parciales por axiomas adicionales , o por dos subórdenes prohibidos de cuatro ítems.

Teoría de la utilidad

La motivación original para introducir semiórdenes fue modelar las preferencias humanas sin asumir que la incomparabilidad es una relación transitiva . Por ejemplo, supongamos que , , y representan tres cantidades del mismo material, y que es mayor que por la cantidad más pequeña que es perceptible como una diferencia, mientras que está a medio camino entre las dos. Entonces, una persona que desea más del material preferiría , pero no tendría una preferencia entre los otros dos pares. En este ejemplo, y son incomparables en el orden de preferencia, como lo son y , pero y son comparables, por lo que la incomparabilidad no obedece a la ley transitiva. ^[1] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$

Para modelar esto matemáticamente, supongamos que a los objetos se les dan valores numéricos de utilidad , dejando cualquier función de utilidad que asigne los objetos a comparar (un conjunto ) a números reales . Establezca un umbral numérico (que puede normalizarse a 1) de modo que las utilidades dentro de ese umbral entre sí se declaren incomparables, y defina una relación binaria sobre los objetos, estableciendo siempre que . Entonces forma un semiorden. ^[2] Si, en cambio, los objetos se declaran comparables siempre que sus utilidades difieran, el resultado sería un ordenamiento débil estricto , para el cual la incomparabilidad de los objetos (basada en la igualdad de números) sería transitiva. ^[1] ${\displaystyle u}$ ${\displaystyle X}$ ${\displaystyle <}$ ${\displaystyle x<y}$ ${\displaystyle u(x)\leq u(y)-1}$ ${\displaystyle (X,<)}$

Axiomática

Un semiorden, definido a partir de una función de utilidad como la anterior, es un conjunto parcialmente ordenado con las dos propiedades siguientes: ^[3]

• Siempre que dos pares de elementos disjuntos sean comparables, por ejemplo como y , debe haber una comparación adicional entre estos elementos, porque implicaría mientras que implicaría . Por lo tanto, es imposible tener dos órdenes lineales de dos puntos mutuamente incomparables . ^[3] ${\displaystyle w<x}$ ${\displaystyle y<z}$ ${\displaystyle u(w)\leq u(y)}$ ${\displaystyle w<z}$ ${\displaystyle u(w)\geq u(y)}$ ${\displaystyle y<x}$
• Si tres elementos forman un ordenamiento lineal , entonces cada cuarto punto debe ser comparable con al menos uno de ellos, porque implicaría mientras que implicaría , mostrando en ambos casos que es comparable a o a . Por lo tanto, es imposible tener un ordenamiento lineal de tres puntos con un cuarto punto incomparable. ^[3] ${\displaystyle w<x<y}$ ${\displaystyle z}$ ${\displaystyle u(z)\leq u(x)}$ ${\displaystyle z<y}$ ${\displaystyle u(z)\geq u(x)}$ ${\displaystyle w<z}$ ${\displaystyle z}$ ${\displaystyle w}$ ${\displaystyle y}$

Por el contrario, a cada orden parcial finito que evita los dos ordenamientos prohibidos de cuatro puntos descritos anteriormente se le pueden dar valores de utilidad que lo conviertan en un semiorden. ^[4] Por lo tanto, en lugar de ser una consecuencia de una definición en términos de utilidad, estos ordenamientos prohibidos, o sistemas equivalentes de axiomas , pueden tomarse como una definición combinatoria de semiórdenes. ^[5] Si un semiorden sobre elementos se da solo en términos de la relación de orden entre sus pares de elementos, obedeciendo estos axiomas, entonces es posible construir una función de utilidad que represente el orden en el tiempo , donde es una instancia de notación O grande . ^[6] ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O}$

En el caso de los ordenamientos de conjuntos infinitos de elementos, los ordenamientos que se pueden definir mediante funciones de utilidad y los que se pueden definir mediante órdenes prohibidos de cuatro puntos difieren entre sí. Por ejemplo, si un semiorden (tal como se define mediante órdenes prohibidos) incluye un subconjunto incontable totalmente ordenado , entonces no existen suficientes números reales suficientemente bien espaciados para que sea representable mediante una función de utilidad. Fishburn (1973) proporciona una caracterización precisa de los semiórdenes que se pueden definir numéricamente. ^[7] ${\displaystyle (X,<)}$

Relación con otros tipos de orden

Órdenes parciales

Se puede definir un orden parcial a partir de un semiorden declarando que siempre que o . De los axiomas que se requiere que obedezca un orden parcial, la reflexividad ( ) se sigue automáticamente de esta definición. La antisimetría (si y entonces ) se sigue del primer axioma de semiorden. La transitividad (si y entonces ) se sigue del segundo axioma de semiorden. Por lo tanto, la relación binaria definida de esta manera cumple con los tres requisitos de un orden parcial: ser reflexiva, antisimétrica y transitiva. ${\displaystyle (X,\leq )}$ ${\displaystyle (X,<)}$ ${\displaystyle x\leq y}$ ${\displaystyle x<y}$ ${\displaystyle x=y}$ ${\displaystyle x\leq x}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle x=y}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq z}$ ${\displaystyle x\leq z}$ ${\displaystyle (X,\leq )}$

Por el contrario, supongamos que es un orden parcial que se ha construido de esta manera a partir de un semiorden. Entonces el semiorden puede recuperarse declarando que siempre que y . Sin embargo, no todo orden parcial conduce a un semiorden de esta manera: el primero de los axiomas de semiorden enumerados anteriormente se sigue automáticamente de los axiomas que definen un orden parcial, pero los otros no. Un orden parcial que incluye cuatro elementos que forman dos cadenas de dos elementos conduciría a una relación que viola el segundo axioma de semiorden, y un orden parcial que incluye cuatro elementos que forman una cadena de tres elementos y un elemento no relacionado violaría el tercer axioma de semiorden (cf. imágenes en la sección #Axiomática). ${\displaystyle (X,\leq )}$ ${\displaystyle x<y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\neq y}$ ${\displaystyle (X,<)}$

Órdenes débiles

Todo ordenamiento débil estricto < es también un semiorden. Más particularmente, la transitividad de < y la transitividad de incomparabilidad con respecto a < implican juntas el axioma 2 anterior, mientras que la transitividad de incomparabilidad por sí sola implica el axioma 3. El semiorden que se muestra en la imagen superior no es un ordenamiento débil estricto, ya que el vértice más a la derecha es incomparable con sus dos vecinos izquierdos más cercanos, pero son comparables.

Órdenes de intervalo

El semiorden definido a partir de una función de utilidad puede definirse de manera equivalente como el orden de intervalo definido por los intervalos , ^[8] por lo que cada semiorden es un ejemplo de un orden de intervalo. Una relación es un semiorden si, y solo si, puede obtenerse como un orden de intervalo de intervalos de longitud unitaria . ${\displaystyle u}$ ${\displaystyle [u(x),u(x)+1]}$ ${\displaystyle (\ell _{i},\ell _{i}+1)}$

Relaciones cuasititransitivas

Según Amartya K. Sen , ^[9] los semiórdenes fueron examinados por Dean T. Jamison y Lawrence J. Lau ^[10] y se descubrió que eran un caso especial de relaciones cuasititransitivas . De hecho, cada semiorden es cuasititransitivo, ^[11] y la cuasititransitividad es invariante a la suma de todos los pares de elementos incomparables. ^[12] Al eliminar todas las líneas rojas no verticales de la imagen superior se obtiene un diagrama de Hasse para una relación que sigue siendo cuasititransitiva, pero viola tanto el axioma 2 como el 3; esta relación podría ya no ser útil como orden de preferencia.

Enumeración combinatoria

El número de semiórdenes distintos en elementos no etiquetados viene dado por los números Catalan ^[13] mientras que el número de semiórdenes en elementos etiquetados viene dado por la secuencia ^[14] ${\displaystyle n}$ $${\displaystyle {\frac {1}{n+1}}{\binom {2n}{n}},}$$ ${\displaystyle n}$

1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... (secuencia A006531 en la OEIS )

Otros resultados

Cualquier semiorden finito tiene dimensión de orden como máximo tres. ^[15]

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 los semiórdenes. ^[16]

Se sabe que los semiórdenes obedecen a la conjetura 1/3–2/3 : en cualquier semiorden finito que no sea un orden total, existe un par de elementos y tal que aparece antes que entre 1/3 y 2/3 de las extensiones lineales del semiorden. ^[3] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

El conjunto de semiórdenes de un conjunto de elementos está bien graduado : si dos semiórdenes del mismo conjunto difieren entre sí por la adición o eliminación de relaciones de orden, entonces es posible encontrar un camino de pasos desde el primer semiorden al segundo, de tal manera que cada paso del camino agrega o elimina una sola relación de orden y cada estado intermedio en el camino es en sí mismo un semiorden. ^[17] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$

Los gráficos de incomparabilidad de semiórdenes se denominan gráficos de indiferencia y son un caso especial de los gráficos de intervalo . ^[18]

Notas

1. Luce (1956), pág. 179.
2. Luce (1956), el Teorema 3 describe una situación más general en la que el umbral de comparabilidad entre dos utilidades es una función de la utilidad en lugar de ser idénticamente 1; sin embargo, esto no conduce a una clase diferente de ordenamientos.
3. abcdBrightwell (1989).
4. Este resultado se atribuye generalmente a Scott y Suppes (1958); véase, por ejemplo, Rabinovitch (1977).
5. Luce (1956, p. 181) utilizó cuatro axiomas, los dos primeros de los cuales combinan la asimetría y la definición de incomparabilidad, mientras que cada uno de los dos restantes es equivalente a una de las propiedades de prohibición anteriores.
6. Avery (1992).
7. Fishburn (1973).
8. Fishburn (1970).
9. Sen (1971, Sección 10, p. 314) Dado que Luce modeló la indiferencia entre x e y como "ni xRy ni yRx ", mientras que Sen la modeló como "tanto xRy como yRx ", es probable que la observación de Sen en la p. 314 se refiera a la última propiedad.
10. Jamison y Lau (1970).
11. ya que es transitivo
12. más general, para agregar cualquier relación simétrica
13. Dean y Keller (1968); Kim y Roush (1978)
14. Chandon, Lemaire y Pouget (1978).
15. Rabinovitch (1978).
16. Fishburn y Trotter (1992).
17. Doignon y Falmagne (1997).
18. Roberts (1969).

Referencias

• Avery, Peter (1992), "Una prueba algorítmica de que los semiórdenes son representables", Journal of Algorithms , 13 (1): 144–147, doi :10.1016/0196-6774(92)90010-A, MR  1146337.
• Brightwell, Graham R. (1989), "Semiórdenes y la conjetura 1/3–2/3", Order , 5 (4): 369–380, doi :10.1007/BF00353656, S2CID  86860160.
• Chandon, J.-L.; Lemaire, J.; Pouget, J. (1978), "Dénombrement des quasi-ordres sur un ensemble fini", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (62): 61–80, 83, SEÑOR  0517680.
• Dean, RA; Keller, Gordon (1968), "Órdenes parciales naturales", Revista Canadiense de Matemáticas , 20 : 535–554, doi : 10.4153/CJM-1968-055-7 , MR  0225686.
• Doignon, Jean-Paul; Falmagne, Jean-Claude (1997), "Familias de relaciones bien graduadas", Discrete Mathematics , 173 (1–3): 35–44, doi : 10.1016/S0012-365X(96)00095-7 , MR  1468838.
• Fishburn, Peter C. (1970), "Indiferencia intransitiva con intervalos de indiferencia desiguales", Journal of Mathematical Psychology , 7 : 144–149, doi :10.1016/0022-2496(70)90062-3, MR  0253942.
• Fishburn, Peter C. (1973), "Representaciones de intervalos para órdenes y semiórdenes de intervalos", Journal of Mathematical Psychology , 10 : 91–105, doi :10.1016/0022-2496(73)90007-2, MR  0316322.
• 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.
• Jamison, Dean T .; Lau, Lawrence J. (septiembre de 1973), "Semiórdenes y la teoría de la elección", Econometrica , 41 (5): 901–912, doi :10.2307/1913813, JSTOR  1913813.
• Jamison, Dean T.; Lau, Lawrence J. (septiembre-noviembre de 1975), "Semiórdenes y la teoría de la elección: una corrección", Econometrica , 43 (5-6): 979-980, doi :10.2307/1911339, JSTOR  1911339.
• Jamison, Dean T.; Lau, Lawrence J. (julio de 1970), Semiórdenes, preferencia revelada y la teoría de la demanda del consumidor , Universidad de Stanford, Instituto de Estudios Matemáticos en las Ciencias SocialesPresentado en el Congreso Mundial de Economía, Cambridge, septiembre de 1970.
• Jamison, Dean T.; Lau, Lawrence J. (octubre de 1977), "La naturaleza del equilibrio con preferencias semiordenadas", Econometrica , 45 (7): 1595–1605, doi :10.2307/1913952, JSTOR  1913952.
• Kim, KH; Roush, FW (1978), "Enumeración de clases de isomorfismo de semiórdenes", Journal of Combinatorics, Information &System Sciences , 3 (2): 58–61, MR  0538212.
• Luce, R. Duncan (1956), "Semiórdenes y una teoría de discriminación de utilidad" (PDF) , Econometrica , 24 (2): 178–191, doi :10.2307/1905751, JSTOR  1905751, MR  0078632.
• Rabinovitch, Issie (1977), "El teorema de Scott-Suppes sobre semiórdenes", Journal of Mathematical Psychology , 15 (2): 209–212, doi :10.1016/0022-2496(77)90030-x, MR  0437404.
• Rabinovitch, Issie (1978), "La dimensión de los semiórdenes", Journal of Combinatorial Theory, Serie A , 25 (1): 50–61, doi : 10.1016/0097-3165(78)90030-4 , MR  0498294.
• Roberts, Fred S. (1969), "Gráficos de indiferencia", Técnicas de prueba en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) , Academic Press, Nueva York, págs. 139-146, MR  0252267.
• Scott, Dana ; Suppes, Patrick (1958), "Aspectos fundamentales de las teorías de la medición", The Journal of Symbolic Logic , 23 (2): 113–128, doi :10.2307/2964389, JSTOR  2964389, MR  0115919.
• Sen, Amartya K. (julio de 1971), "Funciones de elección y preferencia revelada" (PDF) , The Review of Economic Studies , 38 (3): 307–317, doi :10.2307/2296384, JSTOR  2296384.

Lectura adicional

• Pirlot, M.; Vincke, Ph. (1997), Semiórdenes: propiedades, representaciones, aplicaciones , Theory and Decision Library. Serie B: Métodos matemáticos y estadísticos, vol. 36, Dordrecht: Kluwer Academic Publishers Group, ISBN 0-7923-4617-3, Sr.  1472236.