GATE CSE 2017 Set 2 | Question: 21

Question

Consider the set  $X=\{a, b, c, d, e\}$  under partial ordering  $R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) \}$

The Hasse diagram of the partial order $(X, R)$ is shown below.

The minimum number of ordered pairs that need to be added to $R$ to make $(X, R)$ a lattice is ______

Comments

https://www.geeksforgeeks.org/gate-gate-cs-2017-set-2-question-33/

---

Already a lattice, in Hasse diagram we just omit directional arrows. And here they have included them.

---

but there are two pairs which are missing (a,d) and (c,d) what about them?

Answer 1

A Hasse Diagram is called a Lattice if, for every pair of elements, there exists a LUB and GLB.

In the above Hasse Diagram, LUB and GLB exist for every two elements taken from $\left \{ a,b,c,d,e \right \}$. So, it is already a Lattice.

Hence, the Minimum number of ordered pairs that need to be added $ = 0$

Comments

No need to check anything.The given Hasse diagram is well-known non-distributive lattice $N_5$

So, direct answer-0

https://en.wikipedia.org/wiki/Distributive_lattice

---

Here the edge is directed.  Does that make a difference in finding GLB?

---

@neel19 that won’t make any difference. Here $a → b$ only depicts ordered pair $(a,b)$

Answer 2

A bit faster method to answer such kind of questions.

A poset is a lattice, if for every pair of elements we have a GLB and LUB.

Okay, having said that, we also know if two elements a and b are related(aRb) this means a≤b and this means we would have a path from a to b in the corresponding hasse diagram.

So, for such elements, we would always have LUB and GLB, so no need to check for them.

Okay, now in the hasse diagram, while checking for lattice, look only for incomparable elements(elements which don't have a path in the hasse diagram) and check whether for those elements LUB and GLB exists.

 

Incomparable element pairs are (b,d) and (c,d)

LUB{b,d}=e

GLB{b,d}=a

LUB{c,d}=e

GLB{c,d}=a

Infact this lattice is also not a distributive lattice as this lattice is pentagonal lattice which is well-known non-distributive lattice.

Since, for all elements in our hasse diagram, LUB and GLB exists, nothing needs to be added.

SHORTCUT

The given Hasse Diagram is that of $N_5$, well known non-distributive lattice.Just remove the directions of edges and you'll see that lattice.

Directly Answer-0

Ans-0.

Comments

@Ayush Upadhyaya The directions given in Hasse Diagram dont have any significance?

Can we remove them and directly calculate lub and glb?

---

Loved this answer .

---

Great explanation👍

Answer 3

hope it might help.......

Comments

I think GLB of (d,e) is d.

---

 Mostafize Mondal

Actually, it was d but looks like a because of my handwriting but anyway i have corrected it..

Answer 4

GLB of b and d is 'a'. There is nothing to do with the directed edge here.

GLB is defined as suppose you have two elements x and y so if there exist  an element say g such that gRx and gRy, there will be an element z such that zRx and zRy then zRg, then g is the greatest lower bound.

If you see Hasse diagram here b and d are x and y and there exist an element  a here such that aRb and aRd (defined in R), now there is an element here 'a' itself such that aRb and aRd then aRa(defined in R), hence a is the greatest lower bound of b and d