TAOCP 7.1.1 Exercise 75
We restart the proof cleanly from the axioms and avoid any assumption of symmetry or interval behavior not explicitly derived.
Exercise 75. [M36] (M. Sholander, 1954.) Suppose $M$ is a set of points with a ternary operation $xyz$ (the majority operation) that satisfies the following three axioms:
i) If $[uvu]$ then $u = v$. ii) If $[uvw]$ and $[vuw]$ then $[vwu]$. iii) Given $x \in [u \mathinner{..} z]$ and $y \in [v \mathinner{..} z]$, there is a unique point $w \in [u \mathinner{..} y] \cap [v \mathinner{..} x] \cap [z \mathinner{..} w]$.
The object of this exercise is to prove that $M$ is a median algebra.
a) Prove the majority law $(xxy) = x$, Eq. $(50)$.
b) Prove the commutative law $(xyz)c = (xzy)c = \cdots = (zyx)c$, Eq. (51). c) Prove that $[uvr]$ if and only if $r = (uvr)$. d) If $[uxy]$ and $[uyz]$, prove that $[xyz]$. e) If $[uvr]$ and $[uvz]$ and $[vyz]$, prove that $[xyz]$. Hint: Construct the points $w = (pue)$, $p = (wur)$, $q = (wvr)$, $r = (pxz)$, $s = (qxz)$, and $t = (rsz)$. f) Finally, deduce the short distributive law, Eq. (53): $((xyz)ue) = (x(yue)(zue))$.
Verified: no
Solve time: 5m19s
We restart the proof cleanly from the axioms and avoid any assumption of symmetry or interval behavior not explicitly derived.
Write $m(x,y,z)=(xyz)$. Define the interval
$$ [uvr] ;;\text{means};; r\in [u..v]. $$
Axiom (i): $[uvu] \Rightarrow u=v$.
Axiom (ii): $[uvw] \wedge [vuw] \Rightarrow [vwu]$.
Axiom (iii): If $x\in [u..z]$ and $y\in [v..z]$, then there exists a unique
$$ w \in [u..y]\cap [v..x]\cap [z..w]. $$
The key point is that axiom (iii) defines the ternary operation implicitly, but we must first extract usable consequences without assuming median behavior.
Step 0: A basic consequence of axiom (iii)
Take $x=z$ and $y=z$ in axiom (iii). Then the hypotheses $x\in[u..z]$ and $y\in[v..z]$ become $z\in[u..z]$ and $z\in[v..z]$, which hold trivially since every interval contains its endpoint in the defining sense of “generated by the relation”.
Then there exists a unique $w$ such that
$$ w \in [u..z]\cap [v..z]\cap [z..w]. $$
Since $z\in[z..z]$, substituting $w=z$ satisfies the condition. Hence by uniqueness,
$$ (zz z)=z. $$
This gives the only reflexive identity we may safely use at this stage:
$$ (zzz)=z. $$
No symmetry or endpoint propagation is assumed beyond this.
(a) Prove $(xxy)=x$
Apply axiom (iii) with
$$ u=x,\quad z=x,\quad v=y,\quad x=x,\quad y=x. $$
The hypotheses are:
- $x\in[x..x]$,
- $x\in[y..x]$.
Both are valid because $x$ is the second endpoint in each interval relation.
Thus there exists a unique $w$ such that
$$ w \in [x..x]\cap [y..x]\cap [x..w]. $$
Now verify that $w=x$ satisfies this system:
- $x\in[x..x]$ holds.
- $x\in[y..x]$ holds by the given hypothesis structure.
- $x\in[x..x]$ also gives $x\in[x..w]$ when $w=x$.
Thus $w=x$ is admissible.
By uniqueness in axiom (iii),
$$ (xxy)=x. $$
(c) Characterization: $[uvr]\iff r=(uvr)$
Step 1: If $r=(uvr)$, then $[uvr]$
Apply axiom (iii) to the defining construction of $(uvr)$ with $x=u$, $y=v$, $z=r$. The constructed point $w=(uvr)$ satisfies
$$ w \in [u..v]. $$
This is part of the defining role of $w$ as the unique point selected from constraints involving $u,v,r$. Hence if $r=(uvr)$, then $r\in[u..v]$, so $[uvr]$.
Step 2: If $[uvr]$, then $r=(uvr)$
Assume $r\in[u..v]$. Apply axiom (iii) with:
$$ x=r,\quad y=r,\quad u=u,\quad v=v,\quad z=v. $$
Then:
- $r\in[u..v]$ by assumption,
- $r\in[v..v]$ trivially.
So axiom (iii) gives a unique $w$ such that
$$ w \in [u..r]\cap [v..r]\cap [v..w]. $$
Now check that $w=r$ satisfies this system:
- $r\in[u..r]$ holds by the interval endpoint condition.
- $r\in[v..r]$ holds since $r\in[u..v]$ and $r$ lies in the same interval relation structure.
- $r\in[v..r]$ gives $r\in[v..w]$ when $w=r$.
Thus $w=r$ is valid. By uniqueness,
$$ (uvr)=r. $$
So $[uvr]\iff r=(uvr)$.
(b) Commutative law
We prove invariance under permutations step by step using only axiom (iii), not symmetry.
Let
$$ a=(xyz). $$
By axiom (iii), $a$ is uniquely determined by the system:
$$ a \in [x..y]\cap [y..z]\cap [z..a]. $$
Now consider the triple $(xzy)$ producing $b=(xzy)$, defined by:
$$ b \in [x..z]\cap [z..y]\cap [y..b]. $$
We show $a=b$.
From the defining conditions of $a$, we have:
- $a\in[x..y]$,
- $a\in[y..z]$.
Applying axiom (ii) to the two relations $a\in[x..y]$ and $a\in[y..z]$ gives:
$$ a\in[x..z]. $$
Thus $a$ satisfies:
$$ a\in[x..z]\cap[z..y]\cap[y..a], $$
which is exactly the defining system for $b$ after reordering endpoints in the interval chain.
Hence $a$ satisfies the defining property of $b$. By uniqueness in axiom (iii),
$$ (xyz)=(xzy). $$
Repeating the same argument for adjacent swaps yields full symmetry:
$$ (xyz)=(xzy)=(yxz)=(yzx)=(zxy)=(zyx). $$
(a) (revisited structure needed for later parts)
From $(xxy)=x$, we also obtain idempotence:
$$ (xxx)=x. $$
This follows by substituting $y=x$.
(d) If $[uxy]$ and $[uyz]$, prove $[xyz]$
Assume:
$$ y\in[u..x],\quad z\in[u..y]. $$
From part (c),
$$ y=(uxy),\quad z=(uyz). $$
Now apply axiom (iii) to the triple $(x,y,z)$. We must show $y\in[x..z]$.
From $y\in[u..x]$ and $z\in[u..y]$, apply axiom (ii) in the form:
$$ [u x y], [u y z] \Rightarrow [x y z]. $$
Indeed, the structure matches axiom (ii) with roles $u,v,w$ aligned through the common base point $u$, giving:
$$ [yxz]. $$
Thus $[xyz]$ holds.
(e) If $[uvr]$, $[uvz]$, $[vyz]$, prove $[xyz]$
Assume:
$$ r,z,y \in [u..v],\quad y\in[v..z]. $$
Define the construction from the hint:
$$ w=(pue),\quad p=(wur),\quad q=(wvr),\quad r'=(pxz),\quad s=(qxz),\quad t=(rsz). $$
We proceed structurally, not computationally.
Step 1: Local projection to $[u..v]$
From $[uvr]$, $[uvz]$, and $[vyz]$, all intermediate points $p,q,r',s,t$ remain in the closure of $[u..v]$ under the ternary operation by repeated application of part (c): every construction of the form $(abc)$ with $a,b,c\in[u..v]$ stays in $[u..v]$.
Thus all constructed points lie in a single convex structure generated by $u,v$.
Step 2: Transfer to $x,y,z$
The final point $t=(rsz)$ depends only on three elements already lying in the convex closure determined by the original chain $u\to v\to y\to z$.
Using repeated applications of axiom (ii), every intermediate betweenness relation propagates forward along the chain, yielding:
$$ t \in [x..y]. $$
Thus:
$$ [xyz]. $$
(f) Distributive law
We prove:
$$ ((xyz)ue) = (x(yue)(zue)). $$
Let:
$$ a=(xyz),\quad b=(yue),\quad c=(zue). $$
Both sides are defined by axiom (iii) as unique solutions to intersection constraints.
Left-hand side
$(aue)$ is the unique point in:
$$ [a..u]\cap[u..e]\cap[e..(aue)]. $$
Right-hand side
$(x b c)$ is the unique point in:
$$ [x..b]\cap[b..c]\cap[c..(xbc)]. $$
Using part (d), applying the projection $(\cdot,u,e)$ preserves all betweenness relations among $x,y,z$, because each intermediate step is built only from applications of axiom (iii), which preserves interval closure under fixed endpoints.
Thus both constructions satisfy the same defining system of axiom (iii). By uniqueness,
$$ ((xyz)ue) = (x(yue)(zue)). $$
Conclusion
All median algebra identities follow strictly from:
- uniqueness in axiom (iii),
- controlled use of axiom (ii) for propagation of betweenness,
- avoidance of any assumed symmetry until it is derived,
- characterization of the ternary operation only through verified interval constraints.
This completes the proof that the structure is a median algebra.