Namespaces
Variants
Actions

Difference between revisions of "Median algebra"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎References: expand bibliodata)
m (→‎References: isbn link)
 
Line 24: Line 24:
 
* Garrett Birkhoff, S.A. Kiss, "A ternary operation in distributive lattices", ''Bull. Amer. Math. Soc.'' '''53''' (1947) pp. 749-752  {{ZBL|0031.25002}}
 
* Garrett Birkhoff, S.A. Kiss, "A ternary operation in distributive lattices", ''Bull. Amer. Math. Soc.'' '''53''' (1947) pp. 749-752  {{ZBL|0031.25002}}
 
* John R. Isbell, "Median algebra", ''Trans. Amer. Math. Soc.'' '''260''' (1980) pp. 319-362 {{ZBL|0446.06007}}
 
* John R. Isbell, "Median algebra", ''Trans. Amer. Math. Soc.'' '''260''' (1980) pp. 319-362 {{ZBL|0446.06007}}
* Donald E. Knuth, "Introduction to combinatorial algorithms and Boolean functions", ser. The Art of Computer Programming 4.0 (2008) pp. 64-74 ISBN 0-321-53496-4 {{ZBL|1178.68372}}
+
* Donald E. Knuth, "Introduction to combinatorial algorithms and Boolean functions", ser. The Art of Computer Programming 4.0 (2008) pp. 64-74 {{ISBN|0-321-53496-4}} {{ZBL|1178.68372}}

Latest revision as of 18:11, 14 October 2023


2020 Mathematics Subject Classification: Primary: 08-XX [MSN][ZBL]

A set with a ternary operation $\langle x,y,z \rangle$ satisfying a set of axioms which generalise the notion of median, or majority vote, as a Boolean function.

The axioms are

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

The second and third axioms imply commutativity: it is possible (but not easy) to show that in the presence of the other three, axiom (3) is redundant. The fourth axiom implies associativity. There are other possible axiom systems: for example the two

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

also suffice.

In a Boolean algebra the median function $\langle x,y,z \rangle = (x \vee y) \wedge (y \vee z) \wedge (z \vee x)$ satisfies these axioms, so that every Boolean algebra is a median algebra.

Birkhoff and Kiss showed that a median algebra with elements 0 and 1 satisfying $\langle 0,x,1 \rangle = x$ is a distributive lattice.

References

  • Garrett Birkhoff, S.A. Kiss, "A ternary operation in distributive lattices", Bull. Amer. Math. Soc. 53 (1947) pp. 749-752 Zbl 0031.25002
  • John R. Isbell, "Median algebra", Trans. Amer. Math. Soc. 260 (1980) pp. 319-362 Zbl 0446.06007
  • Donald E. Knuth, "Introduction to combinatorial algorithms and Boolean functions", ser. The Art of Computer Programming 4.0 (2008) pp. 64-74 ISBN 0-321-53496-4 Zbl 1178.68372
How to Cite This Entry:
Median algebra. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Median_algebra&oldid=42702