Median algebra: Difference between revisions

Content deleted Content added

Inline

Revision as of 11:21, 13 July 2008

In mathematics, a median algebra is a set with a ternary operation < x,y,z > satisfying a set of axioms which generalise the notion of median, or majority vote, as a Boolean function.

The axioms are

< x,y,y > = y
< x,y,z > = < z,x,y >
< x,y,z > = < x,z,y >
< < x,w,y > ,w,z > = < x,w, < y,w,z > >

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

< x,y,y > = y
< u,v, < u,w,x > > = < u,x, < w,u,v > >

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 < 0,x,1 > = x is a distributive lattice.

References

Birkhoff, Garrett; Kiss (1947). "A ternary operation in distributive lattices". Bull. Amer. Math. Soc. 53: 749–752. {{cite journal}}: Unknown parameter |fitst2= ignored (help)
Isbell, John R. (August 1980). "Median algebra". Trans. Amer. Math. Soc. 260 (2): 319–362.
Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. Vol. 4.0. pp. 64–74. ISBN 0-321-53496-4.

External links

Median Algebra Proof

This algebra-related article is a stub. You can help Wikipedia by expanding it.

@@ Line 2: / Line 2: @@
 The axioms are
-#   &lt; x,x,y &gt; = x
+#   &lt; x,y,y &gt; = y
 #   &lt; x,y,z &gt; = &lt; z,x,y &gt;
 #   &lt; x,y,z &gt; = &lt; x,z,y &gt;
 #   &lt; &lt; x,w,y &gt; ,w,z &gt; = &lt; x,w, &lt; y,w,z &gt; &gt;
+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
+*  &lt; x,y,y &gt; = y
+*  &lt; u,v, &lt; u,w,x &gt; &gt; = &lt; u,x, &lt; w,u,v &gt; &gt;
+also suffice.
+In a [[Boolean algebra (introduction)|Boolean algebra]] the median function <math>\langle x,y,z \rangle = (x \vee y) \wedge (y \vee z) \wedge (z \vee x)</math> 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 &lt; 0,x,1 &gt; = x is a [[distributive lattice]].
 ==References==
-* {{cite journal | last=Isbell | first=John R. | title=Median algebra | journal=[[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]] | volume=260 | number=2 | date=August 1980 | pages=319-362 }}
+* {{cite journal | last=Birkhoff | first=Garrett | authorlink=Garrett Birkhoff | last2=Kiss | fitst2=S.A. | title=A ternary operation in distributive lattices | journal=[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]] | volume=53 | date=1947 | pages=749-752 }}
+* {{cite journal | last=Isbell | first=John R. | title=Median algebra | journal=[[Transactions of the American Mathematical Society|Trans. Amer. Math. Soc.]] | volume=260 | issue=2 | date=August 1980 | pages=319-362 }}
 * {{ cite book | last=Knuth | first=Donald E. | authorlink=Donald Knuth | title=Introduction to combinatorial algorithms and Boolean functions | series=[[The Art of Computer Programming]] | volume=4.0 | date=2008 | isbn=0-321-53496-4 | pages=64-74 }}