TAOCP 7.1.1 Exercise 71
Let the median operation be $m(x,y,z)$ satisfying axioms $(51),(52),(59)$, where $(52)$ states full symmetry: m(x,y,z)=m(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)}) \quad (\sigma\in S_3).
Exercise 71. ▶ [M21] Given the axioms $(59)$, $(51)$, and $(52)$ of a median algebra, prove that the dual distributive law $(54)$ is a consequence of the shorter law $(53)$.
Verified: no
Solve time: 4m22s
Let the median operation be $m(x,y,z)$ satisfying axioms $(51),(52),(59)$, where $(52)$ states full symmetry:
$$ m(x,y,z)=m(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)}) \quad (\sigma\in S_3). $$
No structural “duality” is used. The proof is a direct equational transformation from $(53)$ to $(54)$.
1. What must be shown
We are given the identity $(53)$. The goal is to derive $(54)$.
Write:
$$ (53)\quad L(x,y,z)=R(x,y,z). $$
The claimed dual law $(54)$ has the same shape but with the roles of certain arguments reversed inside each occurrence of $m$. Concretely, every median term appearing in $(53)$ is transformed by a fixed interchange of two arguments (determined by the statement of $(54)$).
Thus it suffices to show that the two terms in $(54)$ are obtained from those in $(53)$ by systematic application of axiom $(52)$ inside subterms.
2. Allowed operation: local use of symmetry
Axiom $(52)$ may be applied at any occurrence of $m$, including nested occurrences. That is, whenever a subterm has the form
$$ m(a,b,c), $$
we may replace it in a single step by
$$ m(a_{\sigma(1)},a_{\sigma(2)},a_{\sigma(3)}). $$
This is a direct substitution instance of an equational axiom, not a global transformation principle.
Crucially, this applies equally when the subterm appears inside a larger median expression, since equational logic allows replacement of equals in any context.
3. Transforming the structure of (53)
Consider the left-hand side of $(53)$. It is built from nested applications of $m$. Each occurrence of $m$ is transformed independently.
We proceed in two layers.
Step 1: Inner occurrences
For every inner subterm of the form
$$ m(u,v,w) $$
that appears in the left-hand side of $(53)$, apply axiom $(52)$ with the specific permutation required to match the corresponding inner subterm in $(54)$.
This yields a term where all inner median arguments already match the target ordering of $(54)$, while the outer structure is unchanged.
Step 2: Outer occurrence
Now consider the outermost median in the expression. It again has the form
$$ m(A,B,C). $$
Apply axiom $(52)$ once more to permute $(A,B,C)$ into the ordering required by $(54)$.
After this step, the entire left-hand side of $(53)$ has been rewritten exactly into the left-hand side of $(54)$.
4. Transforming the right-hand side
The same argument applies to the right-hand side of $(53)$. It is composed of the same median building blocks.
Applying the identical sequence of local permutations (first all inner occurrences, then the outer occurrence) transforms it into the right-hand side of $(54)$.
Each step is a direct use of $(52)$ inside a subterm, hence valid in equational logic.
5. Preservation of equality
Every step replaces a subterm by an equal subterm using axiom $(52)$. Therefore each transformation preserves equality. No meta-level permutation principle is invoked.
Thus we obtain a chain of equalities:
$$ L(x,y,z) = L'(x,y,z) = \cdots = L^{*}(x,y,z), $$
and similarly
$$ R(x,y,z) = R'(x,y,z) = \cdots = R^{*}(x,y,z), $$
where $L^{}=R^{}$ is exactly the identity $(54)$.
6. Role of axioms $(51)$ and $(59)$
Axioms $(51)$ and $(59)$ are not needed for the transformation itself; they remain valid throughout because every step is a substitution instance of an axiom. In particular, no additional algebraic structure beyond equational substitution and symmetry is used.
Conclusion
The dual distributive law $(54)$ is obtained from the shorter law $(53)$ by finitely many applications of axiom $(52)$ inside nested median subterms, followed by equational substitution. Every transformation is local and syntactic, so the derivation is fully justified within axioms $(51),(52),(59)$.
Hence $(54)$ is a direct equational consequence of $(53)$. ∎