Subsets $Y$ of a partially ordered set $L$ need not have least upper bounds nor greatest lower bounds

464 Views Asked by At

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Appendix A Partially Ordered Sets says the following:

Partially ordered set. A partial ordering is a relation $\sqsubseteq : L \times L \rightarrow \{ \text{true}, \text{false} \}$ that is reflexive (i.e. $\forall l : l \sqsubseteq l$), transitive (i.e. $\forall l_1, l_2, l_3 : l_1 \sqsubseteq l_2 \land l_2 \sqsubseteq l_3 \Rightarrow l_1 \sqsubseteq l_3$), and anti-symmetric (i.e. $\forall l_1, l_2 : l_1 \sqsubseteq l_2 \land l_2 \sqsubseteq l_1 \Rightarrow l_1 = l_2$). A partially ordered set $(L, \sqsubseteq)$ is a set $L$ equipped with a partial ordering $\sqsubseteq$ (sometimes written $\sqsubseteq_L$). We shall write $l_2 \sqsupseteq l_1$ for $l_1 \sqsubseteq l_2$ and $l_1 \sqsubset l_2$ for $l_1 \sqsubseteq l_2 \land l_1 \not= l_2$.

A subset $Y$ of $L$ has $l \in L$ as an upper bound if $\forall l^\prime \in Y : l^\prime \sqsubseteq l$ and as a lower bound if $\forall l^\prime \in Y : l^\prime \sqsupseteq l$. A least upper bound $l$ of $Y$ is an upper bound of $Y$ that satisfies $l \sqsubseteq l_0$ whenever $l_0$ is another upper bound of $Y$; similarly, a greatest lower bound $l$ of $Y$ is a lower bound of $Y$ that satisfies $l_0 \sqsubseteq l$ whenever $l_0$ is another lower bound of $Y$. Note that subsets $Y$ of a partially ordered set $L$ need not have least upper bounds nor greatest lower bounds but when they exist they are unique (since $\sqsubseteq$ is anti-symmetric) and they are denoted $\bigsqcup Y$ and $\sqcap Y$, respectively.

It is this part that I am unsure about:

Note that subsets $Y$ of a partially ordered set $L$ need not have least upper bounds nor greatest lower bounds but when they exist they are unique (since $\sqsubseteq$ is anti-symmetric) and they are denoted $\bigsqcup Y$ and $\sqcap Y$, respectively.

This isn't obvious to me. Would someone please explain/clarify this?

1

There are 1 best solutions below

7
On

To see that there are posets without least upper bounds nor greatest lower bounds consider $L = [-1,0) \cup (0,1) \cup (1,2]$ and $Y = (0,1)$. Let your partial order be the usual total order on $\mathbb{R}$. Then there is no least upper bound or greatest lower bound of $Y$ in $L$.

To prove this explicitly for the least upper bound case: suppose some $l \in L$ were a least upper bound of $Y$. Then we can select any $l_0 \in (1,l)$ and $l_0 < l$ is another upper bound for $Y$, but it's less than $l$. This is a contradiction, so no least upper bound can exist.

A similar argument works for the greatest lower bound.

For the uniqueness aspect, given existence, suppose both $l$ and $l^\prime$ were a least upper bound for $Y$ in $L$. Then this means in particular that they are both an upper bound. So $l \sqsubseteq l^\prime$ because $l$ is a least upper bound. But, $l^\prime \sqsubseteq l$ since $l'$ is also a least upper bound. By anti-symmetry this means we must have $l = l^\prime$.

A similar argument works for uniqueness of a greatest lower bound given its existence.