En la teoría del orden , una rama de las matemáticas, un semiordenador es un tipo de ordenación de elementos con puntuaciones numéricas, donde los elementos con puntuaciones muy diferentes se comparan por sus puntuaciones y donde las puntuaciones dentro de un margen de error dado se consideran incomparables . Los semiordernistas fueron introducidos y aplicados en psicología matemática por Duncan Luce ( 1956 ) como un modelo de preferencia humana. Generalizan ordenamientos estrictamente débiles , en los que los elementos con puntajes iguales pueden estar empatados pero no hay margen de error. Son un caso especial de órdenes parciales y de órdenes de intervalo., y se puede caracterizar entre los órdenes parciales por axiomas adicionales , o por dos subórdenes prohibidos de cuatro elementos.
Definición
Deje que X sea un conjunto de elementos, y dejar
- Para todo x e y , no es posible que tanto x < y como y < x sean verdaderos. Es decir,
relación asimétrica - Para todo x , y , z y w , si x < y , y ~ z , y z < w , entonces x < w .
- Para todo x , y , z y w , si x < y e y < z , entonces x < w o w < z . De manera equivalente, con los mismos supuestos sobre x , y , z , todos los demás elementos w deben ser comparables con al menos uno de x , y o z .
Se sigue del primer axioma que x ~ x , y por lo tanto el segundo axioma (con y = z ) implica que
A través de subórdenes prohibidos
Una orden parcial es un semiorden si y solo si no contiene ninguna de las dos órdenes prohibidas descritas como suborden. [2]
Relación con otros tipos de orden
Órdenes parciales
Se puede definir un orden parcial ( X , ≤) a partir de un semiordenador ( X , <) declarando que x ≤ y siempre que x < y o x = y . De los axiomas que se requiere que obedezca un orden parcial, la reflexividad ( x ≤ x ) se sigue automáticamente de esta definición, la antisimetría (si x ≤ y y y ≤ x entonces x = y ) se sigue del primer axioma semiorder, y la transitividad (si x ≤ y e y ≤ z entonces x ≤ z ) se sigue del segundo axioma de semiorder. A la inversa, a partir de un orden parcial definido de esta manera, el semiorder puede recuperarse declarando que x < y siempre que x ≤ y y x ≠ y . El primero de los axiomas de semiorder enumerados anteriormente se sigue automáticamente de los axiomas que definen un orden parcial, pero los demás no. El segundo y tercer axioma de semiorder prohíben órdenes parciales de cuatro elementos que forman dos cadenas disjuntas: el segundo axioma prohíbe dos cadenas de dos elementos cada una, mientras que el tercer elemento prohíbe una cadena de tres elementos con un elemento no relacionado.
Órdenes débiles
Cada orden débil estricto
Órdenes de intervalo
Una relación es un semiorder si, y solo si, se puede obtener como un orden de intervalo de intervalos de longitud unitaria..
Relaciones cuasitransitivas
Según Amartya K. Sen , [3] los semiordenes fueron examinados por Dean T. Jamison y Lawrence J. Lau [4] y se encontró que era un caso especial de relaciones cuasitransitivas . De hecho, cada semiorder es cuasitransitivo, [5] y la cuasitransitividad es invariante a la suma de todos los pares de elementos incomparables. [6] Eliminar todas las líneas rojas no verticales de la imagen superior da como resultado un diagrama de Hasse para una relación que todavía es cuasitransitiva, pero que viola tanto el axioma 2 como el 3; esta relación podría dejar de ser útil como orden de preferencia.
Teoría de la utilidad
La motivación original para introducir semiordenadores fue modelar las preferencias humanas sin asumir (como hacen los ordenamientos débiles estrictos) que la incomparabilidad es una relación transitiva . Por ejemplo, si x , y , y z representan tres cantidades del mismo material, y x y z difieren por la cantidad más pequeña que es perceptible como una diferencia, mientras que Y es a medio camino entre los dos de ellos, entonces es razonable para una preferencia de existir entre x y z , pero no entre los otros dos pares, violando transitividad. [7]
Por lo tanto, suponga que X es un conjunto de elementos y u es una función de utilidad que asigna los miembros de X a números reales . Se puede definir un orden débil estricto en x declarando que dos elementos son incomparables cuando tienen utilidades iguales y, de lo contrario, utilizando la comparación numérica, pero esto necesariamente conduce a una relación de incomparabilidad transitiva. En cambio, si se establece un umbral numérico (que puede normalizarse a 1) de modo que las utilidades dentro de ese umbral se declaren incomparables, entonces surge un semiorder.
Específicamente, defina una relación binaria
En la otra dirección, no todos los semiordenes pueden definirse a partir de utilidades numéricas de esta manera. Por ejemplo, si un semiorder ( X , <) incluye un subconjunto totalmente ordenado incontable, entonces no existen suficientes números reales suficientemente bien espaciados para representar este subconjunto numéricamente. Sin embargo, cada semiorder finito se puede definir a partir de una función de utilidad. [10] Fishburn (1973) proporciona una caracterización precisa de los semiordenadores que pueden definirse numéricamente.
Si un semiorder se da solo en términos de la relación de orden entre sus pares de elementos, entonces es posible construir una función de utilidad que represente el orden en el tiempo O ( n 2 ) , donde n es el número de elementos en el semiorden. [11]
Enumeración combinatoria
El número de semiordernos distintos en n elementos sin etiquetar viene dado por los números catalanes
mientras que el número de semiordernos en n elementos etiquetados viene dado por la secuencia
Otros resultados
Cualquier semiordenador finito tiene una dimensión de orden como máximo de tres. [14]
Entre todos los pedidos parciales con un número fijo de elementos y un número fijo de pares comparables, los pedidos parciales que tienen el mayor número de extensiones lineales son los semiordenes. [15]
Semiorders son conocidos para obedecer la conjetura de 1 / 3-2 / 3 : en cualquier finito semiorder que no es un orden total, existe un par de elementos de x y y de tal manera que x aparece antes de y entre 1/3 y 2 / 3 de las extensiones lineales del semiorder. [2]
El conjunto de semiordenadores en un conjunto de n elementos está bien graduado : si dos semiordenadores en el mismo conjunto difieren entre sí por la adición o eliminación de k relaciones de orden, entonces es posible encontrar una ruta de k pasos desde el primero. semiorder 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 semiorder. [dieciséis]
Las gráficas de incomparabilidad de semiordenadores se denominan gráficas de indiferencia y son un caso especial de las gráficas de intervalo . [17]
Notas
- ↑ Luce (1956) describe un conjunto equivalente de cuatro axiomas, los dos primeros de los cuales combinan la definición de incomparabilidad y el primer axioma enumerado aquí.
- ↑ a b Brightwell (1989) .
- ^ Sen (1971 , Sección 10, p. 314) Desde Luce modelada indiferencia entre x y y como "ni xRy ni yRx ", mientras que Sen modelada como "tanto xRy y yRx ", la observación de Sen en p.314 es probable que media la última propiedad.
- ^ Jamison y Lau (1970) .
- ^ ya que es transitivo
- ^ más general, para agregar cualquier relación simétrica
- ^ Luce (1956) , p. 179.
- ↑ Luce (1956) , 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.
- ↑ Fishburn (1970) .
- ↑ Este resultado se atribuye típicamente a Scott & Suppes (1958) ; véase, por ejemplo, Rabinovitch (1977) . Sin embargo, Luce (1956) , el teorema 2 demuestra un enunciado más general, que un semiorder finito puede definirse a partir de una función de utilidad y una función de umbral siempre que un cierto orden débil subyacente pueda definirse numéricamente. Para semiorders finitos, es trivial que el orden débil pueda definirse numéricamente con una función de umbral unitario.
- ^ Avery (1992) .
- ^ Kim y Roush (1978) .
- ^ Chandon, Lemaire y Pouget (1978) .
- ^ Rabinovitch (1978) .
- ^ Fishburn y Trotter (1992) .
- ^ Doignon y Falmagne (1997) .
- ^ Roberts (1969) .
Referencias
- Avery, Peter (1992), "Una prueba algorítmica de que los semiordenadores son representables", Journal of Algorithms , 13 (1): 144-147, doi : 10.1016 / 0196-6774 (92) 90010-A , MR 1146337.
- Brightwell, Graham R. (1989), "Semiorders and the 1 / 3-2 / 3 conjecture", 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, MR 0517680.
- Doignon, Jean-Paul; Falmagne, Jean-Claude (1997), "Familias de relaciones bien graduadas", Matemáticas discretas , 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", J. Psicología matemática , 7 : 144-149, doi : 10.1016 / 0022-2496 (70) 90062-3 , MR 0253942.
- Fishburn, Peter C. (1973), "Representaciones de intervalo para órdenes de intervalo y semiordenes", J. Psicología matemática , 10 : 91-105, doi : 10.1016 / 0022-2496 (73) 90007-2 , MR 0316322.
- Fishburn, Peter C .; Trotter, WT (1992), "Extensiones lineales de semiordenes: un problema de maximización", Matemáticas discretas , 103 (1): 25–40, doi : 10.1016 / 0012-365X (92) 90036-F , MR 1171114.
- Jamison, Dean T .; Lau, Lawrence J. (septiembre de 1973), "Semiorders 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), "Semiorders and the Theory of Choice: A Correction", Econometrica , 43 (5–6): 979–980, doi : 10.2307 / 1911339 , JSTOR 1911339.
- Jamison, Dean T .; Lau, Lawrence J. (julio de 1970), Semiorders, Revealed Preference, and the Theory of the Consumer Demand , Universidad de Stanford, Instituto de Estudios Matemáticos en Ciencias Sociales. Presentado 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 semiordenadores", Journal of Combinatorics, Information & System Sciences , 3 (2): 58-61, MR 0538212.
- 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.
- Rabinovitch, Issie (1977), "El teorema de Scott-Suppes sobre semiordenes", J. Psicología matemática , 15 (2): 209-212, doi : 10.1016 / 0022-2496 (77) 90030-x , MR 0437404.
- Rabinovitch, Issie (1978), "The dimension of semiorders", 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. Segunda Conf. Teoría de Grafos de Ann Arbor, 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.
Otras lecturas
- Pirlot, M .; Vincke, Ph. (1997), Semiorders: Propiedades, representaciones, aplicaciones , Teoría y Biblioteca de Decisiones. Serie B: Métodos matemáticos y estadísticos, 36 , Dordrecht: Kluwer Academic Publishers Group, ISBN 0-7923-4617-3, MR 1472236.