moral medians

The thesis of this blog post will be that a lattice (in the sense of order theory) has a unique concept of a $3$-arity "median" operation if and only if it is distributive. I am recording this observation on my blog because I have nowhere better to put it. So don't expect a well-written explanatory blog post because this is just quick and dirty.

standard definitions

A lattice is a set equipped with $\land$ (read: meet) and $\lor$ (read: join) operations that act as "greatest lower bound" and "least upper bound" operations, respectively. You can find a precise definition on the internet easily, but it won't be necessary for this blog post anyway, so I won't bother writing it out here. The important part is that all lattices have an induced partial order $\leq$ and are often pictographically represented with Hasse diagrams, which I will use in this post. A lattice is distributive iff $x \land (y \lor z) = (x \land y) \lor (x \land z)$ iff $x \lor (y \land z) = (x \lor y) \land (x \lor z)$ iff it is isomorphic to a subset of a power set with $\cap$ and $\cup$ as its $\land$ and $\lor$ iff it has no sublattices isomorphic to the $M_3$ or $N_5$ lattice. As you can see, they have a lot of different characterizations, the latter of which will be particular relevant for this post.

nonstandard definitions

Define

$M(x, y, z) := (x \land y) \lor (x \land z) \lor (y \land z)$
$M'(x, y, z) := (x \lor y) \land (x \lor z) \land (y \lor z)$

big claim

$M(x, y, z) = M'(x, y, z)$ in $(L, \land, \lor)$ if and only if $L$ is distributive.

distributive implies $M = M'$

The easiest way to see this is to use that distributive lattices have the same equational theory as $(\{0, 1\}, \land, \lor)$ and verify by hand (i.e. use a truth table) that these define the same boolean operations. Intuitively, if we view $x, y, z$ as sets, $M(x, y, z)$ is the set of elements in at least two of $x, y, z$, and $M'(x, y, z)$ is a really weird way of saying the same thing. (Note that if $L$ is linearly ordered, both $M$ and $M'$ are the $3$-arity "median" operation, as I promised in the title of this post. This is not part of the proof, but I should mention it somewhere.) ($\land$ is minimum and $\lor$ is maximum in this specific case.)

not distributive implies $M \neq M'$

Sublattices preserve lattice operations, so we just need to show that this is true of $M_3$ and $N_5$. $M_3$ first:

We have that $M(x, y, z) = 0$ but $M'(x, y, z) = 1$. $N_5$ next:

We have that $M(x, y, z) = x$ but $M'(x, y, z) = y$.

gg keith, so what

Honestly, I don't really have a moral of the story here. I just think this is a cool fact, so I wanted to write it up. Bye!!


sike! i have another proof to share

If $t$ is a lattice term, define $t^\circ$ to be the lattice term replacing every instance of $\land$ with $\lor$ in $t$ and vice-versa. Also, for brevity, for two lattice terms $t, t'$, let $t \approx t'$ denote that $t = t'$ in all lattices.

another big claim

$t \approx t^\circ$ if and only if $t \approx x$ for some atomic term $x$.

proof

Let $t$ be a lattice term such that $t \approx t^\circ$, $t \not \approx x$ for all atomic terms $x$, and $t$ is the least complex term with this property. (By complexity, I mean the count of the number of $\land$'s and $\lor$'s used.) WLOG let $t = t_1 \land t_2$. It turns out there is a nice description of the word problem for lattices. Because we know $t_1 \land t_2 \leq t_1^\circ \lor t_2^\circ$, the solution to the lattice word problem tells us this implies one of four possibilities:
But we also know $t_1^\circ \lor t_2^\circ \leq t_1 \land t_2$, from which we have:
From this, we know that one of the following must be true:
But all of these violate our assumption of least complexity on $t$, as desired.

lmao

I guess the variety of distributive lattices is unlike the variety of lattices in this way.