TIFR CSE 2012 | Part B | Question: 4

Question

Let $\wedge $, $\vee $ denote the meet and join operations of lattice. A lattice is called distributive if for all $x, y, z,$

$x\wedge \left ( y\vee z \right )= \left ( x\wedge y \right )\vee \left ( x\wedge z \right )$

It is called complete if meet and join exist for every subset. It is called modular if for all $x, y, z$

$z\leq x\Rightarrow x\wedge \left ( y\vee z \right )=\left ( x\wedge y \right )\vee z$

The positive integers under divisibility ordering i.e. $p\leq q$ if $p$ divides $q$ forms a.

• A. Complete lattice.
• B. Modular, but not distributive lattice.
• C. Distributive lattice.
• D. Lattice but not a complete lattice.
• E. Under the give ordering positive integers do not form a lattice.

Comments

What is the correct answer?

---

Lattice under divisibility relation

a)It may be complete or may be not. like D_n lattice always leads to a complete lattice but there may be other lattices under division relation those won't result in complete lattice like S={1,2,3}Have no element whom both 2 and 3 divide so not complete.

c) Lattice under division always leads to distributive lattice.Because in this if there complement exists for an element , it would always be unique.

b)It need not be modular , we can take any example and check. take lattice {1,2,3,4,6,24}

here 4∧(3∨2)=4∧24=4     while (4∧3)v2=1v2=2

e) set under divisibility relation always forms Lattice.

---

meaning of divisibility ordering?

---

@Rupendra Choudhary 

If explanation is for +ve integers then no issues but i i have some points to be added if its generelized.

Point a :

About given example  set {1,2,3}.

Source : K.H.Rosen 

UB or LB may or may not be in a given set.

​​​​​​Point e :  

if you consider it for unbounded set then I agree, but may not be valid for every bounded set.

e.g 

({ 1,2,3,4,5} , | ) is not a lattice.

 

point c : 

( { 1,2,3,4,6,12,24} , | ) 

Has elements with more than 1 compliment hence cant be Dist. Lattice. 

 

Please @Pragy Agarwal Sir.

---

@HeadShot even I have doubt with point c thwr you mentioned. If we consider point c of your then answer will be e right?

---

@vupadhayayx86 

If point C is stated by considering an unbounded set then Lattice wont have universal lattiLa so in that case whole argument of that comment is seems to be correct ( as per my knowledge).

And mostly it is considered to be unbounded, but i have just cleared some points so if someone read in future, can detect the difference.

For , Universal Upper Bound / Univ Lower Bound kindly read about complimented lattice.

---

@HeadShot thanks mate will look into it any reference recommended? Coz very little is given in Rosen about it only basic properties are discussed!!

---

@vupadhayayx86 

try kiran sir's lectures on YouTube on Lattice. Not sure but DM is fully discussed so may be you can find lattice to.

n yeah, welcome,., its pleasure to contribute on GO :)

---

if we will consider 6,12 and 18 forming a structure then there is no LUB , therefor it is not a lattice. so , e should be a correct option. please clear my doubt.

Answer 1

Consider the lattice with $gcd$ as meet and $lcm$ as join.

It is distributive

• $gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))$
• $lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))$

It is complete semi-meet lattice. As there is no upper bound it is not complete semi-join lattice.
ANS: C

Comments

Every distributive lattice is modular.

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

That is why option B is not possible.

Useful information:

https://en.wikipedia.org/wiki/Complete_lattice - Examples

The non-negative integers, ordered by divisibility. The least element of this lattice is the number 1, since it divides any other number. Perhaps surprisingly, the greatest element is 0, because it can be divided by any other number. The supremum of finite sets is given by the least common multiple and the infimum by the greatest common divisor. For infinite sets, the supremum will always be 0 while the infimum can well be greater than 1. 

---

as ur given link of wikipedia condition for modular is given as x<=b --->Xv(a^b)=(X v a) ^ b , but in question it has given LHS part implication as b <= x , then it this case its not modular

---

I think question hasn't specified the divisibility under N  so if we consider divisibility under 1 or factors of  1 in that case meet would exist but not join in that case it would be a semi meet lattice therefore not a complete lattice

Answer 2

It will be a complete lattice

12---------3---------1

24------------2

all these lattice are complete lattice, but not distributive or modular always

Comments

@srestha, to prove it as incomplete lattice, we can take any subset. It is not mandatory that all elements in that subset are related.

---

it will  be complete lattice as take example of divisibility of 12  in that lattice distributive property will hold as complement will be unique but it should be complete lattice i think

---

Arjun sir, for {2,3} subset the join is 6 and meet is 1 ( taking All factors of 12 as the set under divisibility and constructing the corresponding Hasse Diagram).So why should the answer not be option a?

Answer 3

as per given wikipedia https://en.wikipedia.org/wiki/Modular_lattice

lhs part of implication in question is i think is typo mistake it shold be x<=z to make it modular , i m giving solution as given in question , according to question it will not be modular , but according to wikipedia it will modular becuse every distributive lattice must be modular , and given lattice is distributive but not showing modular which is contradiction , so i think question is typo mistake 

Answer 4

it will not be distributive lattice . because for being Distributive lattice it must be complemented lattice and it is not complemented lattice .

ex- 12-------6-----3-----1

now its not complemented lattice . but it will be modular . so it will be modular but not distributive lattice .

Comments

{2,4,6,8,24 } for this , modular not exist ...

---

There are no complements for intermediate elements(3,6) in this example. Either there is no universal GLB or universal LUB for these elements.

A bounded lattice is complemented lattice if every element has a complement.

But it cannot be complete lattice.A complete lattice is a partially ordered set in which all subsets have both join and meet. Here subsets may not have upper bound.

To be distributive lattice it is not required that it should be a complemented lattice. Only requirement is if complement exists for an element that must be unique.
refer: https://gateoverflow.in/25203/discrete-math

So it is a distributive lattice.

---

 bharti 

it does need  to be complemented to be distributed for a lattice .....

Distributed:- A lattice would be distributed if for every element there is at most one complement ....

and this question is for complete not complement