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

Basically, for any subset there exists LUB and GLB (BUT IT MAY or MAY not BELONG to THE SUBSET that we choose!, LUB and GLB will exist in the LATTICE.)

Finite lattice -> Complete lattice
Infinite lattices may or may not be complete.

---

Detailed Video Solution, with ALL Complete Analysis: https://www.youtube.com/watch?v=3chjsP_NNnY&t=3351s

---

@Deepak Poonia

sir i have doubt in the video solution of this question is that

In lecture you told two defintions 

1).for LUB just look for unique first joining point in upward direction 

if we use this we will get the answer right away but while discussing standard lattice you told that 

2) join (LUB) in (P(S),SUBSET) is union and meet(GLB) in (P(S),SUBSET)  intersection but here LUB OF {1,2,4} AND {1,2,3} = {1,2,4} U {1,2,3} = {1,2,3,4} but it does not give {1,2,3,4,5} i know we didn't assumed anything by our own as it is already given in the question so it won't affect answer but this must be satisfied right.

Am i mixing up the concepts or it is a valid thinking Kindly look into it sir.

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

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

 

Look my diagram, Do you really think its lattice?

 

---

@Abhijit Sen 4 Bhaiya, here POSET relation is set containment right?!

---

the join of {1,2,3} and {1,3,5}={1,2,3,5} is not present
the join of {1,2,3} and {1,2,4}={1,2,3,4} is not present
the meet of {1,2,3} and {1,3,5} ={1,3} is not present
the meet of {1,2} ∩ {1,2,3} ∩ {1,3,5} ∩ {1,2,4} ∩ {1,2,3,4,5} ={1} is not present

I think option 4 should be the correct answer anyone please correct if i am wrong

Answer 2

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

Comments

@Rajinder Singh Intersection should not be used here.{1} satisfies as the glb of both {1,2,3} and {1,3,5} (as given in the question necessary and sufficient i.e minimal set required to a make S a complete lattice)

---

If I take { {1},(1,2}, {1,2,3},{1,2,4} } as subset
What is the Greatest Element here?

---

@Sidd1425 The greatest element in that case would be {1, 2, 3, 4, 5} as all the 4 elements u have given relates to it.

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

Detailed Video Solution, with ALL Complete Analysis: https://www.youtube.com/watch?v=3chjsP_NNnY&t=3351s 

Answer 4

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?

---

What I have inferred from necessary and sufficient is bare minimum, as few as possible, and considering the digram here it can be done just with {1}

Answer 5

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

Answer 6

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}