Section 7.1.1: Boolean Basics

Exercise 86. [45] [45] If $u$, $w$, $x$, $y$, and $z$ belong to a median set $X$, does their five-element median $(uwxyz)$, computed componentwise, always belong to $X$?

Verified: yes
Solve time: 4m11s

---

Let

$$ a=(uwx),\qquad b=(uxy),\qquad c=(abz)=((uwx),(uxy),z). $$

Since $X$ is a median set, $a,b\in X$, and therefore $c\in X$. It therefore suffices to prove the Boolean identity

$$ ((uwx),(uxy),z)=(uwxyz), $$

where $(uwxyz)$ denotes the majority value of the five variables. Once this identity is established, closure of $X$ under the ternary median immediately implies closure under the five-element median.

Because the median is computed independently in each coordinate, it is enough to verify the identity for Boolean values. Thus assume

$$ u,w,x,y,z\in{0,1}, $$

where $(pqr)$ denotes the majority of the three bits.

Write

$$ A=(uwx),\qquad B=(uxy). $$

We shall prove that

$$ (A,B,z)=1 $$

if and only if at least three of $u,w,x,y,z$ are equal to $1$.

First suppose that at least three of $u,w,x,y,z$ are $1$.

If $z=1$, then at least two of $u,w,x,y$ are $1$.

If at least two of $u,w,x$ are $1$, then $A=1$, hence

$$ (A,B,z)=(1,B,1)=1. $$

Otherwise, fewer than two of $u,w,x$ are $1$. Since at least two of $u,w,x,y$ are $1$, it follows that $y=1$ and exactly one of $u,w,x$ is $1$. In particular, $u=1$ or $x=1$, so among $u,x,y$ at least two entries are $1$. Hence

$$ B=(uxy)=1, $$

and therefore

$$ (A,B,z)=(0,1,1)=1. $$

Now suppose $z=0$. Then at least three of $u,w,x,y$ are $1$.

If $A=1$, then at least two of $u,w,x$ are $1$. Since there are at least three $1$'s among $u,w,x,y$, either $u=1$ or both $x=y=1$. In either case $B=1$. Hence

$$ (A,B,z)=(1,1,0)=1. $$

If $A=0$, then at most one of $u,w,x$ is $1$. Since at least three of $u,w,x,y$ are $1$, this forces

$$ u=w=x=y=1, $$

which contradicts $A=0$. Thus this case cannot occur.

Therefore,

$$ (A,B,z)=1 $$

whenever at least three of $u,w,x,y,z$ are $1$.

Now suppose at most two of $u,w,x,y,z$ are $1$. Then at least three of the complemented variables

$$ \bar u,\bar w,\bar x,\bar y,\bar z $$

are $1$.

The ternary median commutes with complementation:

$$ (\bar p,\bar q,\bar r)=\overline{(pqr)}. $$

Hence

$$ \overline{(A,B,z)}

\bigl((\bar u,\bar w,\bar x),(\bar u,\bar x,\bar y),\bar z\bigr). $$

Applying the result already proved to the complemented variables yields

$$ \overline{(A,B,z)}=1, $$

so

$$ (A,B,z)=0. $$

Thus

$$ (A,B,z)=1 \quad\Longleftrightarrow\quad \text{at least three of }u,w,x,y,z\text{ are }1, $$

which is exactly the defining property of the five-variable majority function. Therefore

$$ ((uwx),(uxy),z)=(uwxyz) $$

for every Boolean assignment.

Since the identity holds in every coordinate,

$$ ((uwx),(uxy),z)=(uwxyz) $$

for vectors as well.

Finally,

$$ (uwx)\in X,\qquad (uxy)\in X, $$

and closure of $X$ under the ternary median gives

$$ ((uwx),(uxy),z)\in X. $$

Hence

$$ (uwxyz)\in X. $$

Therefore every median set is closed under the componentwise median of five elements.

$$ \boxed{\text{Yes. If }u,w,x,y,z\in X,\text{ then }(uwxyz)\in X.} $$