GATE CSE 1999 | Question: 2.3

Question

Let $L$ be a set with a relation $R$ which is transitive, anti-symmetric and reflexive and for any two elements $a, b \in  L$, let the least upper bound $lub (a, b)$ and the greatest lower bound $glb (a, b)$ exist. Which of the following is/are true?

• A. $L$ is a poset

• B. $L$ is a Boolean algebra

• C. $L$ is a lattice

• D. None of the above

Comments

@ASNR1010

how? explain.

if poset then its not necessary to be a lattice but 

if its a lattice then its a poset also .

why toset?

---

@Pranavpurkar yes toset with every element is comparable then it is toset but we are not sure about comparability in this case so it may or may not be toset

---

A Boolean algebra needs more structure: it must be a complemented, distributive lattice with least and greatest elements. 

 

Answer 1

Which of the following is/are true? This is question with Multiple answers.

As our Relation $R$ on Set $L$ is Reflexive , anti symmetric & Transitive it is poset.

Since $\text{LUB}$ & $\text{GLB}$ exists for any two elements it is lattice.

Answer: $A$ & $C$.

$B$ is not guaranteed to be true.

Ref: http://uosis.mif.vu.lt/~valdas/PhD/Kursinis2/Sasao99/Chapter2.pdf

Comments

Amitabh Tiwari 1

if LUB/GLB exists then it implies it's unique, if there exist more than one lower bound or upper bound, we say LUB/GLB doesn't exist.

---

Anyone has the referred link in the answer?

Edit: possibly this → http://www.cectl.ac.in/images/pdf_docs/studymaterial/cse/s3/dcs4.pdf

---

The question says “The least upper bound” although “The” can be used with both singular and plural nouns but here we have a single LUB, because it’s not “The least upper bound(s)”.
 

Answer 2

it is given that set with a relation Relation R which is transitive, antisymmetric and reflexive so it is already a poset .Additionally, it is guaranteeing about the existence  of LUB and GLB too.so now it is  : Poset + Having lub and Glb both , That is Lattice . so option A and C both r true .

For being option B true it needs some extra information that is :

A lattice can be Boolean Algebra only  when It is distributed lattice , complimented lattice and bounded lattice along with it will have to satisfy the properties of Boolean algebra . and we dont have any such info about this lattice .

counter of B is :

  it is poset, lattice but not B.A

Answer 3

As it is Reflexive , anti-symmetric , transitive , it is poset.

Since lub and gub exist for any pair of elements, the poset becomes a lattice. So, C is the answer.

Comments

this question has multiple answers ? right ?

---

@Akash Kanase sir , I agree with the point that this problem has multiple answers , but telling that the set is a lattice automatically implies that the set is also a poset , in multiple answer problems why are we choosing the implied option?

---

prashant jha 1

That’s what the purpose of MSQ’s.

Answer 4

The answer is a and c. because in the question it is given that LUB and GLB exists and by definition LUB and GLB are always unique. If it is not unique that we can say that LUB and GLB does not exist. It is not required to mention explicitly the word unique.