Distributive lattice/Proofs

From Wikipedia, the free encyclopedia

Main article: Distributive lattice

Contents

[edit] Lemma 1

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

[edit] Proof

We will show:

x \vee (y \wedge z) = (x \vee y)\wedge(x \vee z)

We may suppose y\le z (If not, z\le y and we may switch y and z.)


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

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

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 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.