0
$\begingroup$

Let ( L, ≤ ) be a lattice, x, y, z ∈ L. Prove that : $x ∧ y ≤ x$ and $x ∧ y ≤ y$

Here is how I proceeded to solve it:

Approach 1 : Proceeding by definition:

$x ∧ y ∈$ { x, y }

Therefore, x ∧ y either x or y

If $x ∧ y = x, x ≤ x$ is true by reflexive property and $x ≤ y$ as L is a poset

If $x ∧ y = y, y ≤ y$ is true by reflexive property and $y ≤ x$ as L is a poset ( this is an assertion I am not comfortable with )

Hence true.

Approach 2 : Proof by contradiction:

$x ∧ y$ not ∈ { x, y }.

Let x ∧ y be z

Therefore, $x ≤ z, y ≤ z$, but $x ≤ x$ and $y ≤ y$ are false ( A poset L is a lattice iff for every $x, y ∈ L : x ∧ y$ and $x V y$ exist in L, and are unique )

This contradicts ( { x, y }, $≤$ ) being a lattice as the reflexive property is violated.

Hence, the original assertion is true.

I am not comfortable with the arguments myself and I might have made errors in the notation. Could you have a look and help me out?

  • 0
    Rolled back an edit that re$m$o$v$ed all content; please do not do this.2014-04-16

1 Answers 1

2

I do not see why you assert that $x\wedge y$ must be either $x$ or $y$. This is not true in an arbitrary lattice: for instance, in the lattice of subsets of a given set $X$ (with $\leq$ corresponding to inclusin, $\wedge$ corresponding to intersection, and $\vee$ corresponding to union) it is false that $x\cap y$ must be either $x$ or $y$. So you should really be feeling not comfortable about your assertions well before you actually do. But even if you got to that step, you are definitely in trouble: it does not follow that $y\leq x$ "as $L$ is a partially ordered set". That assertion has no justification whatsoever.

As to your "proof by contradiction", a proof by contradiction does not begin by negating your "definition" (as you claim earlier). A proof by contradiction begins by negating the proposed conclusion. If you wanted to do this by contradiction, you would have to being by assuming that your conclusion, "$x\wedge y \leq x$ and $x\wedge y \leq y$" is false. So you would need to assume that "$x\wedge y\not\leq x$ OR $x\wedge y \not\leq y$" is true.

And even if you get to your third line, you have it exactly backwards: it does not follow that $x\leq x\wedge y$ and $y\leq x\wedge y$. What makes you think that?

So... how do you prove this?

You say you are defining the lattince operations in terms of the partial order. That is, you "know" what $\leq$ means, and then you define $\wedge$ and $\vee$ using $\leq$. The definition would be that $x\wedge y$ is the greatest lower bound of $\{x,y\}$ (which must exist if you call the poset a lattice) and $x\vee y$ is the least upper bound of $\{x,y\}$.

Well, using that definition, $x\wedge y$ is the greatest lower bound of the set $\{x,y\}$. In particular, it is a lower bound of $\{x,y\}$. What is the definition of "lower bound"? What does that tell you?

It is also possible that it is the other way around: you "know" what $\wedge$ and $\vee$ mean, and you define a partial order in terms of them. If you define $\leq$ in terms of the lattice operations, then, explicitly, you define the partial order associated to the lattice by saying that for $a,b\in L$, $a\leq b \Longleftrightarrow a\wedge b=a,$ or else you define it by $a \leq b \Longleftrightarrow a\vee b = b.$ In fact, both definitions are equivalent, as can be shown using the properties of the two operations in a lattice.

So in this case, what you want to show is that $(x\wedge y)\vee x = x$ and that $(x\wedge y)\vee y = y$. (Or if you defined it using $\wedge$, that $(x\wedge y)\wedge x = x\wedge y$ and that $(x\wedge y)\wedge y = x\wedge y$). These will follow directly from the properties that operations that make up a lattice must satisfy (commutativity, associativity, idempotency, and the two absorption laws).

  • 0
    Ah! Yes, now I get it, and my understanding is better than what it was last night. Thank you! If you could, could you have a look at my revised "proof" below? My notation needs to be correct, at the very least.2010-11-21