GATE CSE 2005 | Question: 9

Question

The following is the Hasse diagram of the poset $\left[\{a,b,c,d,e\},≺\right]$

The poset is :

• A. not a lattice
• B. a lattice but not a distributive lattice
• C. a distributive lattice but not a Boolean algebra
• D. a Boolean algebra

Comments

right Jashan Arora

---

A lattice is not distributive if it has KITE or PENTAGONAL structure as sub-lattice or lattice itself is Kite/Pentagonal.

 

 

 

---

Is it a Lattice? 

→ Yes. LUB and GLB exist for every pair of elements.

Is it a Bounded lattice?

→ Yes. Every finite lattice is bounded.

Is it a Complemented lattice?

→ Yes. for every element complement is there.

Is it a Distributive lattice?

→ No. Because for some elements more than one complement exists.

Is it a Boolean Algebra lattice?

→ No. Because it is not distributive.

---

Complement of a  = e.

Complement of e  = a.

Complement of b  = c, d.

Complement of c  = b, d.

Complement of d  = c, b.

Answer 1

Option B.

A lattice has a least upper bound (lub) and a greatest upper bound (glb), but to be distributive every element of the lattice should have at most one complement.Here, elements $b,c,d$ are complements of each other and hence the given lattice is not distributive.

Ref: https://math.stackexchange.com/questions/2814774/example-of-a-lattice-which-has-at-most-1-complement-for-its-every-element-but-it

Comments

It is a well known non-distributive lattice-The "Kite" lattice.

---

I think this statement is wrong.

A lattice has lub and glb but to be distributive it should also have a unique complement.

It is also possible for some elements of a lattice to not a complement but still  it is  distributive lattice.

Ex. All tosets with number of elements > 2

 

A distributive lattice ==> at most one complement for each element

More than one complement for atleast one element ==> not distributive lattice.

In the question b has c, d as complements so not distributive.

 

---

Yes, that sentence was not right. Corrected now.

Answer 2

Option B is appropriate for it.

It is lattice bcz both LUB and GLB exist for each pair of the vertex in the above Hasse diagram.

But It is not Distributed bcz there exist more than a complement of element. So it ever be Boolean algebra.

Comments

@Paras Nath given Hasse diagram is totally different from poset  i think given reation is not '<' (less than ) it is other relation defined according to hasse diagram 

---

yes, it may be any relation. because nothing is mentioned about it. But, this can be answered by looking at hasse diagram only.

Answer 3

A lattice is a distributive lattice if each element has at most one complement.

Complements of b are c and d.

So, not distributive.

 

It sure is a lattice, though. So, Option B

---

 

Why is it not a Boolean algebra?

• If every element of the lattice has at least one complement => Complemented lattice.
   
• If every element of the lattice has strictly either 0 or 1 complement => Distributive lattice.
   
• A complemented distributed lattice is a necessary condition for being Boolean algebra. (So Option D is False)

Comments

A Distributive Complemented lattice is Boolean Algebra. Its definition of Boolean Algebra, so both necessary and sufficient condition(bi-implication).

Boolean Algebra ↔ (Distributive & Complemented & Lattice)

Property of bi-implication says for true,  F ↔ F or T ↔ T .

Using Contrapositive , Not Distributive → Not Boolean Algebra

Answer 4

.