GATE CSE 2004 | Question: 73

Question

The inclusion of which of the following sets into

$S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\} $

is necessary and sufficient to make $S$ a complete lattice under the partial order defined by set containment?

• A. $\{1\}$
• B. $\{1\}, \{2, 3\}$
• C. $\{1\}, \{1, 3\}$
• D. $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$

Comments

@rajankakaniya

({1,2,3}, {1,2,4})  has a supremum in S i.e. {1,2,3,4,5}.

---

LUB and GLB in the base set not in the subset relation. 

 

src: https://home.iitk.ac.in/~arlal/book/mth202.pdf ​​​​​​​pg 173

---

@neel19 

@Yuvraj Raghuvanshi 

@Deepak Poonia Sir 

wouldn’t the answer be option (C) because the infimum of {1,3,5} and {1,2,3} is {1,3} which is present in option C.

Answer 1

Answer: A

A lattice is complete if every subset of partial order set has a supremum and infimum element.

For example, here we are given a partial order set S. Now it will be a complete lattice if whatever be the subset we choose, it has a supremum and infimum element. Here relation given is set containment, so supremum element will be just union of all sets in the subset we choose. Similarly, infimum element will be just intersection of all the sets in the subset we choose.

Now as we can see, $S$ now is not complete lattice, because although it has a supremum for every subset we choose, but some subsets have no infimum. For example: if we take subset $\{1,3,5\}$ and $\{1,2,4\}$ then intersection of sets in this is $\{1\},$ which is not present in $S.$ So clearly, if we add set $\{1\}$ in $S,$ we will solve the problem. So, adding $\{1\}$ is necessary and sufficient condition for $S$ to be complete lattice. Thus, option (A) is correct.

Comments

The term intersection for GLB should not be used here as if we take intersection {1,2,3} and {1,3,5}  , then it will give us {1,3}.

In the same way the term union for LUB is not correct as {1,2,4}+{1,2,3} gives {1,2,3,4} which is not even there in this POSet.

The operaion set containment . It's like if y(- {x,y,z,w} , then y belong or contained in this set.

so no need to discuss about LUB as (1,2,3,4,5} and every element of this Hasse diagram is present/contained in this set.

In the same way for GLB I need to check only two pairs :

Pair 1: {1,2,3) and {1,2,4} = only 1 can satisfy the GLB

Pair 2: {1,2,4} and {1,3,5} = LB are 1 and 1,3 . Here GLB is 1,3

For Pair1, definitely I need to include 1 else GLB for pair1 won't be satisfied.

For Pair2, I can include {1,3} but does it necessary because here the operation is containment.

So , 1(- {1,3,5} which , in other words 1 belongs to set {1,3,5}. Then no need to add {1,3}

So , adding 1 as GLB would be suffice to make it Lattice.

---

If we do intersection of set{1,2,3} and set {1,3,5} then {1,3} comes but between these set GLB is {1}.then  How this lattice is complete.

---

Could you please make a lattice diagram, How it will look like

 

Look my diagram, Do you really think its lattice?

 

Answer 2

See the below diagram only {1} is enough to be Lattice. Hence Option A is Ans.

Comments

here" necessary and sufficient to make s" what is significant of this

---

here  "necessary and sufficient to make S a complete lattice"  means the minimal set among given options to satisfy definition of complete lattice. Clearly {1} makes L complete and is minimal too, whereas (1) & (1,3) is also a complete lattice but not minimal. Hence (a) is correct..

---

If we do intersection of set{1,2,3} and set {1,3,5} then {1,3} comes but between these set GLB is {1}.then  How this lattice is complete.

---

@rajinder singh did your doubt get cleared if yes then please elaborate!

Answer 3

given set contains two infimum (1,2) & (1,3,5) so given set is not a lattice.
adding (1) to the given set results lattice..

Comments

Infimum of {1,2,3} and {1,3,5} should be {1,3} right? But it isn't present in the lattice. Why isn't (C) the answer?

Answer 4

• A partially ordered set L is called a complete lattice if every subset M of L has a least upper bound called as supremum and a greatest lower bound called as infimum.
• We are given a set containment relation.
• So, supremum element is union of all the subset and infimum element is intersection of all the subset.
• Set S is not complete lattice because although it has a supremum for every subset, but some subsets have no infimum.
  We take subset {{1,3,5},{1,2,4}}.Intersection of these sets is {1}, which is not present in S.
  So we have to add set {1} in S to make it a complete lattice

Comments

BEST answer!

---

In a finite lattice, there is a unique minimal element (least element) and also a unique maximal element (greatest element). So, can we say a lattice is a complete lattice if every one of its subsets is a finite lattice? @Deepak Poonia sir?

---

@Shubhamishere

Every Finite Lattice is a Complete Lattice.

If a lattice $L$ is such that every subset of $L$ is a finite lattice, then $L$ is a Total Order, also Finite lattice, also Complete lattice.