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

draw the hasse diag. for above lattice and you can easily figure out the missing key in the puzzle is {1}

Answer 2

Actually, this qs is about to make COMPLETE Lattice.

If we add {a} then it becomes a complete lattice.

First of all draw the Poset diagram with {a}.And plz don't use the Shortcut for LUB of A and B = A U B and GLB of A and B =A∩B

Just see the Poset diagram and find out the LUB and GLB for every pair of elements.

Let  eg1. subset A= {{1,2},{1,3,5}}  then LUB of {1,2},{1,3,5} = {1,2,3,4,5} ∈ S and GLB of {1,2},{1,3,5} ={1} ∈ S

Let eg2.subset B={{1,2,3},{1,3,5}} then LUB of {1,2,3},{1,3,5} = {1,2,3,4,5} ∈ S and GLB of {1,2,3},{1,3,5} = {1} 

The correct answer is ,(A) {1}

Answer 3

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

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

We are given a set containment relation.

So,  supremum element is the union of all the subsets and the infinum element is the intersection of all the subsets. Set S is not a complete lattice because although it has a supremum for every subset, some subsets have no infinum.

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

thus, option (A) is correct.

 

alternative method

 

======================================

hope my answer helps u a lot