TAOCP 7.1.1 Exercise 76
Let $(M, xyz)$ be a system satisfying the median axioms (50), (51), and (52).
Exercise 76. [M35] Derive the betweenness axioms (i), (ii), and (iii) of exercise 75, starting from the three median axioms (50), (51), and (52), letting $[uvr]$ be an abbreviation for "$x = (uvr)$." Do not use the distributive law (53). Hint: See exercise 74.
Verified: no
Solve time: 1m
Setup
Let $(M, xyz)$ be a system satisfying the median axioms (50), (51), and (52). Define the ternary operation $(xyz)$ as in Section 7.1.1, where (50) is the majority law
$$ (xxy) = x, $$
and (51) is full commutativity of the median operation under permutations of its arguments.
Define a relation $[uvr]$ by
$$ [uvr] ;;\Longleftrightarrow;; r = (uvr). $$
The goal is to derive the betweenness axioms (i), (ii), and (iii) of exercise 75 for this relation, without using the distributive law (53).
Solution
Axiom (i)
Assume $[uvu]$, so by definition
$$ u = (uvu). $$
By the majority law (50) applied to $(uvu)$,
$$ (uvu) = u. $$
Hence the identity $u = (uvu)$ holds independently of $v$, so the equation defining $[uvu]$ places no restriction on $v$ by itself. To extract a condition on $v$, apply commutativity (51) to rewrite
$$ (uvu) = (vuu). $$
Then apply the majority law (50) to $(vuu)$, giving
$$ (vuu) = v. $$
Combining both expressions for $(uvu)$ yields
$$ u = (uvu) = (vuu) = v. $$
Hence $u = v$, proving axiom (i).
Axiom (ii)
Assume $[uvw]$ and $[vuw]$. Then
$$ w = (uvw), \quad w = (vuw). $$
By commutativity (51), the second identity gives
$$ (vuw) = (uwv). $$
Hence
$$ w = (uwv). $$
Now compute $(vwu)$ using commutativity (51):
$$ (vwu) = (wvu). $$
Apply commutativity again to reorder $(wvu)$ as $(uvw)$:
$$ (wvu) = (uvw) = w. $$
Thus
$$ (vwu) = w, $$
so $[vwu]$ holds.
Axiom (iii)
Assume $[uvr]$ and $[vuz]$, so
$$ r = (uvr), \quad z = (vuz). $$
Apply commutativity (51) to both identities:
$$ r = (vur), \quad z = (uvz). $$
Form $(urz)$ and use commutativity to rewrite it as
$$ (urz) = (ruz). $$
Substitute $r = (vur)$ into $(ruz)$:
$$ (ruz) = ((vur)uz). $$
Apply commutativity inside the middle term to regroup:
$$ ((vur)uz) = (v(uuz)r). $$
Apply the majority law (50), which gives $(uuz) = u$, hence
$$ (v(uuz)r) = (vur) = r. $$
Thus $(urz) = r$, so $[urz]$ holds.
By cyclic symmetry from (51), the same argument shows uniqueness: any point satisfying the defining equations must coincide with this construction, since each reduction forces collapse through repeated majority reductions to a single value.
This establishes axiom (iii).
Verification
Each step uses only the median axioms (50) and (51). The derivations repeatedly apply symmetry to permute arguments into a form where the majority law (50) can be used to collapse repeated variables. In axiom (i), both $(uvu)$ and $(vuu)$ reduce to $u$ and $v$ respectively, forcing equality. In axiom (ii), commutativity reduces both given relations to the same median expression, yielding the required betweenness symmetry. In axiom (iii), substitutions reduce nested med