0
$\begingroup$

Added later: Proof now in progress.


Let $(L, \leq)$ be a lattice, $x, y, z \in L$. Prove that $x ≤ y$ and $x ≤ z \iff x ≤ y ∧ z$.

I proceed to prove as follows:

The statement can be split into two implications :

(i) $x ≤ y$ and $x ≤ z \implies x ≤ y ∧ z$

(ii) $x ≤ y ∧ z \implies x ≤ y$ and $x ≤ z$

(i) Approach 1 : Proceeding by use of definitions:

$x ≤ y$ and $x ≤ z \implies x$ is a LB in $L$

Let $w = y ∧ z$

Since w is the GLB, by defn. $x ≤ w$, i.e. $x ≤ y ∧ z$

Approach 2 : Proof by contradiction:

Let $x ≤ y$ and $x ≤ z \implies x$ not $≤ y ∧ z$

$x ≤ y$ and $x ≤ z \implies x$ is a LB in $L$

Let $w = y ∧ z$

Since w is the GLB, by defn. $x ≤ w$, i.e. $x ≤ y ∧ z$.

As a contradiction has been reached, the original assertion is true.

(ii) Approach 1 : Proceeding by use of definitions:

$x ≤ y ∧ z \implies x$ is a LB in $L$

By definition of LB, $x ≤$ for all $w ∈ L$, i.e. $x ≤ y$ and $x ≤ z$

Approach 2 : Proof by contradiction:

Let $x ≤ y ∧ z \implies$ not $x ≤ y$ or not $x ≤ z$.

$x ≤ y ∧ z \implies x$ is a LB in $L$

By definition of LB, $x ≤$ for all $w ∈ L$, i.e. $x ≤ y$ and $x ≤ z$.

As a contradiction has been reached, the original assertion is true.

  • 0
    @Mariano: He deleted all the infor$m$atio$n$; I've restored it.2010-11-23

1 Answers 1

5

With the identity, $ x \leq y \Leftrightarrow x = x \wedge y$, the implication is straightforward to prove. That is,

$\begin{align} x \leq y \text{ and } x \leq z & \Leftrightarrow x = x \wedge y \text{ and } x = x \wedge z \\ & \Leftrightarrow x \wedge x = (x\wedge y) \wedge (x\wedge z)\\ & \Leftrightarrow x = x \wedge (y \wedge z)\\ & \Leftrightarrow x \leq y \wedge z. \end{align}$

  • 0
    I am afraid that the second <=> is not clear to me. => direction is obvious, but the other direction...2012-04-27