Definitions

# Distributive lattice/Proofs

## Lemma 1

Every totally ordered set is a distributive lattice with max as join and min as meet.

### Proof

We will show:

$x vee \left(y wedge z\right) = \left(x vee y\right)wedge\left(x vee z\right)$

We may suppose $yle z$ (If not, $zle y$ and we may switch $y$ and $z$.)

Recall that $yle z$ is equivalent to $yvee z = z$. Hence $y le z$ implies $\left(xvee y\right) vee \left(xvee z\right) = x vee z$, i.e., $xvee y le xvee z$, so the right hand side of the equation is equal to $\left(x vee y\right)wedge\left(x vee z\right) = x vee y$. On the left hand side we have $y wedge z = y$, so equality is established.

Note that the relation $x vee \left(y wedge z\right) le \left(x vee y\right)wedge\left(x vee z\right)$ is true in all lattices, as both $x$ and $ywedge z$ are bounded above by $\left(x vee y\right)wedge\left(x vee z\right)$.

## Lemma 2

Let L be a lattice, and let x be an element of L. If x is meet-prime, then it is meet-irreducible.

### Proof

Suppose x = a v b. Then x ≤ a v b. x being meet-prime, x ≤ a or x ≤ b. Without loss of generality suppose x ≤ a. Then a v b ≤ a. By definition of v, a v b ≥ a. Therefore a v b = a and x = a.

## Lemma 3

Let L be a distributive lattice, and let x be an element of L. If x is join-irreducible, then it is join-prime.

### Proof

Recall that in a lattice x ≤ y ⇔ x ^ y = x.
Suppose x ≤ a v b. This is equivalent to x ^ (a v b) = x which by distributivity is in turn equivalent to (x ^ a) v (x ^ b) = x. x being meet-irreducible, x = x ^ a or x = x ^ b. This is equivalent to x ≤ a or ≤ b.

Search another word or see Distributive lattice/Proofson Dictionary | Thesaurus |Spanish