Álgebra mediana

En matemáticas , un álgebra de medianas es un conjunto con una operación ternaria que satisface un conjunto de axiomas que generalizan las nociones de medianas de ternas de números reales y de función mayoritaria booleana . ${\displaystyle \langle x,y,z\rangle }$

Los axiomas son

1. ${\displaystyle \langle x,y,y\rangle =y}$
2. ${\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }$
3. ${\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }$
4. ${\displaystyle \langle \langle x,w,y\rangle ,w,z\rangle =\langle x,w,\langle y,w,z\rangle \rangle }$

El segundo y tercer axiomas implican conmutatividad: es posible (pero no fácil) demostrar que en presencia de los otros tres, el axioma (3) es redundante. El cuarto axioma implica asociatividad. Hay otros posibles sistemas de axiomas: por ejemplo los dos

• ${\displaystyle \langle x,y,y\rangle =y}$
• ${\displaystyle \langle u,v,\langle u,w,x\rangle \rangle =\langle u,x,\langle w,u,v\rangle \rangle }$

también basta.

En un álgebra booleana , o más generalmente en una red distributiva , la función mediana satisface estos axiomas, de modo que cada álgebra booleana y cada red distributiva forman un álgebra mediana. ${\displaystyle \langle x,y,z\rangle =(x\vee y)\wedge (y\vee z)\wedge (z\vee x)}$

Birkhoff y Kiss demostraron que un álgebra mediana con elementos 0 y 1 satisfactorios es una red distributiva . ${\displaystyle \langle 0,x,1\rangle =x}$

Relación con las gráficas de mediana

Un gráfico de mediana es un gráfico no dirigido en el que por cada tres vértices , y hay un vértice único que pertenece a los caminos más cortos entre dos de , y . Si este es el caso, entonces la operación define un álgebra de mediana que tiene los vértices del gráfico como elementos. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle \langle x,y,z\rangle }$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle \langle x,y,z\rangle }$

Por el contrario, en cualquier álgebra mediana, se puede definir un intervalo como el conjunto de elementos tales que . Se puede definir una gráfica a partir de un álgebra de mediana creando un vértice para cada elemento de álgebra y una arista para cada par de modo que el intervalo no contenga otros elementos. Si el álgebra tiene la propiedad de que cada intervalo es finito, entonces esta gráfica es una gráfica mediana y representa con precisión el álgebra en el sentido de que la operación mediana definida por los caminos más cortos en la gráfica coincide con la operación mediana original del álgebra. ${\displaystyle [x,z]}$ ${\displaystyle y}$ ${\displaystyle \langle x,y,z\rangle =y}$ ${\displaystyle (x,z)}$ ${\displaystyle [x,z]}$

Referencias

• Birkhoff, Garrett ; Beso, SA (1947). "Una operación ternaria en redes distributivas". Toro. América. Matemáticas. Soc. 53 (8): 749–752. doi : 10.1090/S0002-9904-1947-08864-9 .
• Isbell, John R. (agosto de 1980). "Álgebra mediana". Trans. América. Matemáticas. Soc. 260 (2). Sociedad Estadounidense de Matemáticas: 319–362. doi : 10.2307/1998007 . JSTOR  1998007.
• Knuth, Donald E. (2008). Introducción a los algoritmos combinatorios y funciones booleanas . El arte de la programación informática . vol. 4. Upper Saddle River, Nueva Jersey: Addison-Wesley. págs. 64–74. ISBN 978-0-321-53496-5.

enlaces externos

• Prueba de álgebra mediana