Distributive lattice/Proofs

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 (y wedge z) = (x vee y)wedge(x vee z)

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 (xvee y) vee (xvee z) = x vee z, i.e., xvee y le xvee 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 ywedge z are bounded above by (x vee y)wedge(x vee z).

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
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT