Distributive lattice/Proofs

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Main article: Distributive lattice

[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)$ .

Distributive lattice/Proofs

From Wikipedia, the free encyclopedia

[edit] Lemma 1

[edit] Proof

Views

Personal tools

Navigation

Search

Interaction

Toolbox