Let $a\in L$, where $L$ is a graded (if needed) distributive lattice. Let $x_1, \ldots, x_k$ – the set of elements which cover $a$ ($x$ covers $a$ if $a < x$ and there is no element $t$ such that $a < t < x$). Denote least upper bound of $x_1, \ldots, x_k$ as $b$. Consider sublattice $[a, b]$. Is it true (and if it is, how to prove it?) that greatest lower bound of elements covered by $b$ is $a$ (in sublattice $[a,b]$)?
Upper and lower bound in distributive lattice
lattice-ordersorder-theory
Related Solutions
"Least upper bound" property is that every nonempty set that is bounded above has a least upper bound; dually for "greatest lower bound", so it is only required that nonempty sets have the property.
(For example, the real numbers have the least upper bound property; if you also required the empty set to have a least upper bound, this would require the reals to have a least element).
Yes, Dedekind completeness is the same thing as the least upper bound property.
For 2: If $S$ is a nonempty set that is bounded below, let $B$ be the set of lower bounds of $S$. Show that $B$ is (i) nonempty; and (ii) bounded above. Conclude that $B$ has a least upper bound. Show that the least upper bound of $B$ is also the greatest lower bound of $S$. The converse is proven dually: the least upper bound of a nonempty set that is bounded above is equal to the greatest lower bound of the set of upper bounds.
First: the "least upper bound" and "greatest lower bound" principles are not at all about ordered fields, they are about partially ordered sets; an ordered field is necessarily a partially ordered set, but there are plenty of partially ordered sets that satisfy the least upper bound and greatest lower bound properties without being fields.
Second: You are trying to prove the least upper bound principle, assuming the greatest lower bound principle holds. Let's be clear about what these principles are:
We say a partially ordered set $(X,\leq)$ satisfies the Greatest Lower Bound Principle if and only if every nonempty subset $P$ of $X$ that has a lower bound has a greatest lower bound; that is, if there exists $x\in X$ such that $x\leq p$ for all $p\in P$, then there exists $g \in X$ such that:
- $g\leq p$ for all $p\in P$; and
- if $x\in X$ is such that $x\leq p$ for all $p\in P$, then $x\leq g$.
As for the Least Upper Bound Principle, we have the dual definition:
We say a partially ordered set $(X,\leq)$ satisfies the Least Upper Bound Principle if and only if every nonempty subset $P$ of $X$ that has an upper bound has a least upper bound; that is, if there exists $x\in X$ such that $p\leq x$ for all $p\in P$, then there exists $\ell\in X$ such that:
- $p\leq \ell$ for all $p\in P$; and
- if $x\in X$ is such that $p\leq x$ for all $p\in P$, then $\ell\leq x$.
Now, let's look at your argument. You are assuming that your field $F$ satisfies the Greatest Lower Bound Principle, and you take a subset $P$ of $F$. You assume it is nonempty, and that there is an element $k$ that is an upper bound. You incorrectly assert that this element $k$ will be in $P$: you don't know that, and you don't need that.
Then you consider the set $-P=\{-p \mid p\in P\}$, and note that $-k$ is a lower bound for $-P$ (you incorrectly assert it is a greatest lower bound; you don't know that). You then deduce that $-P$ has a greatest lower bound (correct). And you stop there. But you need to show that $P$ has a least upper bound, and you have not done so. (Of course, you probably meant to take the greatest lower bound $\ell$ of $-P$, and then show that $-\ell$ is a least upper bound for $P$; but you have not done so). So your argument is incomplete.
Now, there is nothing wrong with the idea behind your argument (provided you fix the errors and fill in the gaps). The reason you may not want to do this is that the fact that the Least Upper Bound Principle and the Greatest Lower Bound Principles are equivalent is true for any partially ordered set. In a partially ordered set, the argument that relies on "multiplying by $-1$" will not in general work, because that operation will not make sense. So rather than use a proof that only works for a certain kind of partially ordered set, we can use a proof which is not any more complicated, but which works in general. And moreover, a proof that highlights that the least upper bound of a set is in fact a greatest lower bound of a different set (and likewise for greatest lower bounds).
Namely:
Suppose $X$ satisfies the greatest lower bound principle, and we want to prove it satisfies the least upper bound principle. Let $P$ be a nonempty set that has at least one upper bound. We need to show it has a least upper bound. Let $B=\{b\in X\mid b\text{ is an upper bound for }P\}$. By assumption, $B$ is not empty. Moreover, since $P$ is not empty, there is a $p\in P$, and so $p\leq b$ for all $b\in B$. That means that $B$ is a nonempty set that is bounded below. By the Greatest Lower Bound Principle, $B$ has a Greatest Lower Bound; call it $g$. We claim that $g$ is also a least upper bound for $P$.
First, note that if $p\in P$ we have $p\leq b$ for all $b\in B$. By the second property of the greatest lower bound, we conclude that $p\leq g$. Therefore, for every $p\in P$ we have $p\leq g$, so $g$ satisfies the first property necessary to be the least upper bound of $P$. To verify it satisfies the second property, if $x\in X$ is such that $p\leq x$ for all $p\in P$, then $x\in B$ by definition. And since $g$ is the greatest lower bound of $B$, then the first property of the greatest lower bound tells us that $g\leq b$ for all $b\in B$, and in particular that $g\leq x$. Thus, if $x$ is an upper bound for $P$, then $g\leq x$. This verifies that $g$ satisfies the second property of the least upper bound for $P$. We conclude that $g$ is indeed the least upper bound for $P$.
So we have shown that if $X$ satisfies the greatest lower bound principle, then any nonempty subset that is bounded above has a least upper bound; that is, $X$ also satisfies the least upper bound principle.
A symmetric argument (or applying the above argument to the partially ordered set $(X,\leq^{\rm op})$) shows that if $X$ satisfies the least upper bound principle, then it satisfies the greatest lower bound principle. $\Box$
Once you fill in all the details into your argument, you'll see that it is no shorter and no less difficult than the above one. But the above one has the virtue of not needing any of the field properties that you use (that $a\leq b$ if and only if $-b\leq -a$, for example), only the properties of order, of upper and lower bounds, and the corresponding principle. So it is a nicer proofs, because it assumes less, concludes the same, and is not any harder or longer than the proof you suggest.
Related Question
- [Math] If each subset of $L$ with an upper bound has a least upper bound, then each subset with a lower bound a a greatest lower bound
- Why wouldn’t the distributive laws hold for a lattice
- “In a bounded lattice the join is the least element and meet is the greatest element”… yet a join is the least upper bound I don’t understand.
Best Answer
Let $\rho : L \to \mathbb N$ be the rank function of $L$.
Then the interval $[a,b]$ has finite length, given by $\rho(b) - \rho(a)$.
Since $[a,b]$ is a sublattice of $L$, it is distributive.
A distributive lattice is finite iff it has finite length.
Notice that the elements which cover $a$, in $L$, are the atoms of $[a,b]$;
analogously the elements covered by $b$ which are above $a$ are co-atoms of $[a,b]$.
So we're left with the task of proving that in a finite distributive lattice, if the join of the atoms is $1$, then the meet of the co-atoms is $0$.
That just follows from the fact that if the join of the atoms is $1$, then those are the only join-irreducible elements of the lattice, which is then Boolean, and it is clear that in a Boolean lattice the meet of the co-atoms is $0$.