3.1k views

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?

1. $\{1\}$
2. $\{1\}, \{2, 3\}$
3. $\{1\}, \{1, 3\}$
4. $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$
| 3.1k views
+1
why C is not answer intersection of {1,2,3} and {1,3,5} is {1,3} please clear this point
+5

The relationship of one set being a subset of another is called containment or inclusion.

GLB of 2 sets- A and B, need not be their intersection.
Similarly, LUB of A and B need not be their union.
It just required that A is related to B only when $A \subseteq B.$

The key here is -
They asked about the inclusion of set which is necessary and sufficient to make S complete lattice.
So {1} is necessary and sufficient.
C is incorrect because inclusion of {1},{1,3} is sufficient but not necessary to make S complete lattice.
With similar reasoning, D is not correct.

+1

Remember though C can be also correct ans but we need to include the minimum length string to make it our best case. So inclusion of {1} will be sufficient as well as necessary to make the Lattice complete whereas inclusion of {1,3} though sufficient but not necessary actually as the job can be done by a smaller set {1} itself. So the ans will be option a.

P.S--> The question is good. Even at first I too had the same dilemma..

+1

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

We aren't getting complete lattice as we have multiple buttom. (for buttom pair no infimum exist).

{1,2} and {1.3.5}

To make single buttom we have to place a element which is related to (contained in both).

{1,2} $\bigcap$ {1.3.5} = {1}

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},{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.

by Boss (33.9k points)
edited
0
@Jon intersection of {1,2,3} and {1,3,5} is {1,3} it is also not present in the set, why we are not considering {1,3} ??
0
Actually i hav the same doubt that why not {1,3} is considered  ?? Including this set ,the answer should be C .   Can anyone give a better explanation ?
0
In that case ...how will you satisfy that union of { 1,2} and {1,3,5} is {12345}?

In the way of going up we are adding elements..

1,2 is subset of 1,2,3 now 1,2,3 is gone and we are taking intersection of 1,2 and 1,3,5.

Correct ne if I am wrong
+6
Relation between lattice and complete lattice :

Every finite lattice is definitely a complete lattice ... but an infinite lattice neednot be a complete lattice ... Here they have given a finite lattice as the set S contains finite number of elements ... so checking whether this is a complete lattice or not is as same as checking whether this is a lattice or not ....

Example for an infinite lattice which is not complete :

Assume the poset is [R , <=] ...where R is set of all real numbers .....

this is clearly a lattice as every totally ordered set is a lattice ...this is also an infinite lattice .... is this a complete lattice ??? No

A complete lattice is a lattice in which every subset of partial ordered set has a LUB and GLB ...

Let me define a subset K = { a /   -5 < a < 5 }

Now I can't tell the LUB or GLB of this subset because an element which is less than 5 is uncountably infinte 4.9 ,4.99,4.99999 ... similiarly we cannot tell the GLB of this subset .... so since a subset does not have LUB (or GLB) we can say that it is not a complete lattice ....
0
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.
0
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.

See the below diagram only {1} is enough to be Lattice. Hence Option A is Ans. by Boss (23.9k points)
0
here" necessary and sufficient to make s" what is significant of this
+1
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..
0
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.
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..
by Veteran (60.9k points)
0
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?
• 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
by Loyal (5.8k points)
draw the hasse diag. for above lattice and you can easily figure out the missing key in the puzzle is {1}
by Active (2.8k points)

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}

by Loyal (8k points)
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
by Active (1.2k points)