Question

Show thatevery finite lattice has a least element and a greatest element.

Short answer

Every finite lattice has a least element and a greatest element is proved.

Step-by-step solution

Given data

Lattice is finite.

Concept used of partially ordered set and mathematical induction

A relation\(R\)is a poset if and only if,\((x,x)\)is in\({\rm{R}}\)for all x (reflexivity)

\((x,y)\)and\((y,x)\)in R implies\(x = y\)(anti-symmetry),\((x,y)\)and\((y,z)\)in Rimplies\((x,z)\)is in\({\rm{R}}\)(transitivity).

Mathematical Inductionis a mathematical proof method that is used to prove a given statement about any well-organized set.

Evaluate poset

We.recall that a poset in which every pair of element has both a least upper

bound and a greatest lower bound is called a lattice.

Suppose \((L, \le )\) is a lattice and \(A\) is a non-empty finite subset of \(L\). If \(A\) contains one or two elements, then by definition \({\rm{A}}\) has a least upper bound and a greatest lower bound.

Assume that any finite subset of \(L\) containing \(n\), where \(n\) is a positive integer and \(n \ge 2\), elements have a least upper bound and a greatest lower bound.

Now, suppose \(A = \left\{ {{a_1},{a_2}, \ldots \ldots ..,{a_n},{a_{n + 1}}} \right\} \subseteq L\)

Then \(A = {A_0} \cup \left\{ {{a_{n + 1}}} \right\}\) where \({A_0} = \left\{ {{a_1},{a_2}, \ldots \ldots \ldots \ldots \ldots ..,{a_n}} \right\}\) observe that

\(l\).u.b(A)=l.u.\(b\left\{ {l.u.b({A_0}),{a_{n + 1}}} \right\}\),

g.\(l\).b(A) =g.l.b { g.\(l\).\(\left. {b({A_0}),{a_{n + 1}}} \right\}\).

Prove by induction principle

By the induction hypothesis, \(l\).u.b(A), g.\(l\).b(A) exists in \(L\) and because \(L\) is a lattice,

It follows that\(l\).u.b(A), g.\(l\).b(A)exists.

Hence, by the principle of mathematical induction, it follows that every non empty finite

subset of \(L\) has a least upper bound and a greatest lower bound.

Now, suppose \((L, \le )\) is a finite lattice. Since, \(L\) is a finite non empty subset \(L\), by the

above observation; \(L\) has a least upper bound and a greatest lower bound.

Since \(a \le l.u.b(L)\) for all \(a \in L\)

\(l\).u.b(L) is the greatest element and \(g.l.b(L)\) is the least element of \(L\)

Hence, every finite lattice has a least element and a greatest element is proved.