# Any non-empty finite subset $\{x_1,x_2,...,x_k\}$ of $B$ has a g.l.b and l.u.b in $B$

Prove that any non-empty finite subset $$\{x_1,x_2,...,x_k\}$$ of $$B$$ has a g.l.b and l.u.b in $$B$$ where $$(B,\leq)$$ forms a lattice, i.e.

• $$(B, \leq)$$ is a partially ordered set
• Any two elements $$x, y\in B$$ have a g.l.b(greatest lower bound) $$x \land y$$ and an l.u.b(least upper bound) $$x \lor y$$

I've been thinking of induction, but I'm not sure that it'd work since we only have a partial order on $$B$$. Nevertheless,

1. Base case: Only one element, which is the g.l.b and l.u.b both
2. Induction hypothesis: Let's say the statement holds for sets of size $$n-1$$ and less
3. Consider a set of size $$n$$, namely $$\{x_1, x_2,...,x_n\}$$. $$\{x_1, x_2,...,x_{n-1}\} \subset \{x_1, x_2,...,x_n\}$$ has a g.l.b (say $$x_g$$) and an l.u.b (say $$x_l$$) in $$\{x_1, x_2,...,x_{n-1}\}$$. All that remains to be shown is that g.l.b($$x_1,...,x_n$$) = g.l.b($$x_g,x_n$$). Similarly for l.u.b.

I'm not sure how to proceed from here!

• You're on the right path! The last step is the use the definitions for GLB and LUB to show that $\mathrm{GLB}(x_g,x_n)$ satisfies that definition, and the same on the LUB. Commented Oct 28, 2020 at 15:13
• The approach that you have taken, coupled with Steven Stadnicki's comment seems best. A less desirable, but still do-able approach is to provide an algorithm for sorting the set, and demonstrate that after the algorithm completes, the first element in the set is the GLB and the last element in the set is the LUB. A typical single step in the algorithm would be something like, start with the set in any order (i.e. $\{x_1, x_2, \cdots, x_n\}$) and then start comparing elements. If (for example), $x_2 \leq x_1$, then have $x_2$ and $x_1$ "swap places". Commented Oct 28, 2020 at 18:29

We proceed by induction on $$k$$.
1. Base case: $$k=1$$. $$|X| = 1$$, and $$x_1$$ is its g.l.b and l.u.b both, since $$x_1 \leq x_1$$.
2. Induction Hypothesis: Let the statement hold for $$|X| \leq k-1$$.
3. Induction Step: Consider $$X = \{x_1,x_2,...,x_k\}$$ = $$\{x_1,...,x_{k-1}\} \cup {x_k}$$. $$\{x_1,...,x_{k-1}\}$$ has a g.l.b, say $$x_g \in B$$ (by the induction hypothesis). Moreover, $$x_g$$ and $$x_k$$ have a g.l.b, say $$x'_g$$. It remains to show that $$x'_g$$ is in fact the g.l.b of $$X$$. We have that $$x'_g \leq x_g,x_k$$, and if $$z\leq x_g,x_k$$ then $$z\leq x'_g$$. In addition, $$x_g \leq x_1,...,x_{k-1}$$ and if $$z \leq x_1,...,x_{k-1}$$ then $$z\leq x_g$$. Combining the above two statements, $$x'_g\leq x_1,...,x_k$$ and if $$z\leq x_1,...,x_k$$ then $$z\leq x'_g$$.