GATE IT 2008 | Question: 28

Question

Consider the following Hasse diagrams.

1. 
2. 
3. 
4. 

 

Which all of the above represent a lattice?

• A. (i) and (iv) only
• B. (ii) and (iii) only
• C. (iii) only
• D. (i), (ii) and (iv) only

Comments

i think for (ii) since it has more than one minimal element so it cannot be a lattice

---

no need to check 3rd eliminated from the option cuz 1 st one was correct.

---

normally check whether glb lub exists for all the elements or not.

Answer 1

Answer is (A)
Hasse diagram is lattice when every pair of elements have a least upper bound and a greatest lower bound. In figures (ii) and (iii), every element is not having a least upper bound and a greatest lower bound (these if exist will be unique as per their definitions). So, they are not lattices.

Comments

In (3) which pair is causing the problem?

---

In fig (3): pair (c,e) will not have least upper bound and pair (b,f) will not have greatest lower bound.

---

Is f not the LUB of (c,e) and c not the GLB  of (b,f) in fig(3)

---

No. Because LUB and GLB must be unique.

---

got it. Thanks

---

Hi @Arjun sir , 

Please correct me if I am wrong. 

In option (ii) , LUB of (a,b) is b and LUB of (b,d) is b.

So , the pair (a,b) and (b,d) does not have unique LUB.

Similarly the pair (a,c) and (d,c) does not have unique LUB.

So, it is not lattice.

Am I wrong ?

---

Every pair means- "every individual pair", not combination of pairs.

Here consider for (a, d), we have two possible LUB - b and c.

---

@coolcoder001 (a,d) also doesn't have GLB. so its not a lattice .

---

b and c doesnt have a glb too.

---

d is glb of b  and c or not @ sushmita

---

No its not because b and c have two glb here d and a. So not unique and glb and lub must be unique in a lattice. If d and a were also connected in the lattice, then d would have been the glb of b and c.

---

yaa,,, you are right my mistake , thanks

b and c doesn't have unique glb.

---

In 3rd option why f is not lub(c,e)

---

bcz lub must be unique lub(c,e) gives f ,b both.

---

LUB of (a,d) are also two b or c right?

---

 jatin khachane 1 yes

---

Arjun Sir, I have a doubt here in figure 3... can't we take a as the unique LUB/join of c and e?

---

@Subhajit Majumder 1 The upper bound elements of c and e are a,b,f. Out of these, the least must be unique but among b and f we can't identify unique(least) element therefore there doesn't exist any LUB for c and e.

---

Sir I want to ask one question here that

While checking for lattice do we also check for pairs like - (b,d)?

And glb of (b,d) will be b?

---

So, LUB & GLB of any pair is unique, but for every pair there need not be an unique GLB & LUB.

Is it correct ???

---

@MRINMOY_HALDER Can we say that  the given figure is not lattice  ,as  d and a does not have a GLB? 

---

yes I think so,

(d,a) have no lower bound

---

@Mari Ganesh Kumar, See it is like this:-

f and e are upper bounds of (c,e). Now to say there exists a least upper bound of (c,e), you should be able to say one of the upper bounds of (c,e) as least. Can you say which of {f,e} is least? No. Because f and e are not comparable. So, upper bound of (c,e) exists but there is no least upper bound of (c,e). Lattice should have GLB and LUB for every pair of elements. So this is not a alttice. 

---

Any source to learn this concept?

---

Opt (b) and (c) is incorrect because, For two incomparable element, there are multiple joining or meeting point.

Answer 2

Ans is A

Explanation :---

A Hasse diagram is called Lattice if all the pairs of nodes have only one LUB and only one GLB.

Comments

You have put forward wrong definition of the lattice. You are saying of bounded lattice.

---

Posted Incorrect Definition.
Correct: Each Element should have a LUB and GLB.

---

Lattice ---> hasse diagram has only one lub and glb
hasse diagram has only one lub and glb ----> may or may not be a lattice.

 

Answer 3

Option A is only right answer.

Plz find out LUB as well as GLB.Then u automatically find out clue.

Answer 4

 We can visualize (ii) as shown in image. 2 minimal elements so directly we can say it is not a lattice. Check image for other details.

And fig. 2 and 3 neither meet nor join semiLattice. So, answer is A)

Also Thanks other members for good discussion.

Answer 5

See in diagram (ii) for non-comparable elements there is no first "unique" meeting point i.e. no unique GLB. So it is not a lattice. Similarly in diagram (iii) for the upper side  non- comparable elements there is no first unique meeting point i.e. GLB and for the lower side non-comparable elements there is no first "unique " joining point i.e. LUB. That's why Option A is the correct answer.

Answer 6

For element b, d

GLB (b, d) = (c. e) but GLB must be unique i.e. only 1 element present in GLB. Hence not lattice.

So, (ii) and (iii) are not lattice