Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It all depends on the definition of the meet. In my definition, the meet of $x,y$ is an element smaller than both but bigger than any (other) element smaller than both. So for this definition, this property is "by definition". –  Yuval Filmus Nov 21 '10 at 6:26
    
@Yuval: that's if you define the lattice structure in terms of a given partial order; I suspect he has a lattice structure and is defining the partial order in terms of the lattice operations. –  Arturo Magidin Nov 21 '10 at 6:31
    
@user3740: is the order defined in terms of $\wedge$ and $\vee$, or are $\wedge$ and $\vee$ defined in terms of the order? –  Arturo Magidin Nov 21 '10 at 6:35
    
@Arturo : Thank you for asking the clarification. I am not sure of that myself. I am defining L to be a lattice after it is a poset and it has the inf and sup, so I guess the answer to your question would be "∧ and ∨ defined in terms of the order" –  user3740 Nov 21 '10 at 6:43
    
@user3740: then the proof is immediate: $x\wedge y$ is defined to be a particular kind of lower bound: what is the definition of lower bound? Mind you, this is not a hard problem either way: the absorption laws give you the answer in the other case also essentially immediately. Either way, your attempt at proof is flawed from the very first line in both cases. The assertion about $x\wedge y$ being (or not being) in $\{x,y\}$ is invalid (in both cases). –  Arturo Magidin Nov 21 '10 at 6:45
show 2 more comments

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
I am defining the "lattice" in terms of the partial order; i.e. L is a poset on ≤. This question however made me think - how do I define a partial order in terms of the lattice operations ∨ and ∧? –  user3740 Nov 21 '10 at 6:46
1  
@user3740: Gee... I don't know. Maybe in exactly the way I describe in the answer to which you are commenting? If $\wedge$ and $\vee$ are binary operations that are idempotent, commutative, associative, and that satisfy the absorption laws, then you define the partial order $a\leq b$ if and only if $a\wedge b=a$, or equivalently, if and only if $a\vee b= b$. –  Arturo Magidin Nov 21 '10 at 6:47
    
@Arturo : Thanks for the detailed answer. I also assume you corrected a few notation errors in my original posting - thanks for those as well. I am just learning this, and it helps me having my conjectures broken down by experts! –  user3740 Nov 21 '10 at 7:11
1  
@user3740: You're welcome; but actually I did not make any changes to your post with. I only changed the tags. You can see the changes made by clicking on the "edited xx [time unit] ago" in the post. –  Arturo Magidin Nov 21 '10 at 7:14
    
I have one clarification though : If we define set intersection to be the partial order, then using this definition : "A poset L is a lattice iff for every x, y ∈ L : x ∧ y and x V y exist in L, and are unique", the set intersection and set union does not exist in L, but in the power set of L - right? This would mean that this definition is not universal? –  user3740 Nov 21 '10 at 7:31
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.