# Least upper bound for subsets of a partially-ordered set

Given the definition of least upper bound as:

Definition A: Let S be a set of real numbers, then

1. a is an upper bound for S if $x \leq a \space \forall x \in S$, and
2. b is a least upper bound for S if b is an upper bound, and $b \leq a$ whenever a is an upper bound for S.

We can prove that this is equivalent to the following definition:

Definition B: Let $S \neq \emptyset$. Then b is a least upper bound for S iff

1. $x \leq b \space \forall x \in S$, and
2. $\forall \epsilon > 0 \space \exists x \in S \space | \space x > b - \epsilon$

Proof: Let b be a l.u.b. Then (1) holds. Suppose (2) is not true. Then $\exists \space \epsilon > 0 \space \forall \space x \in S, \space x \leq b - \epsilon$. This contradicts that b is the l.u.b. Next, assume (1) and (2). Then b is an upper bound from (1). If for some b', $b' < b$ then from (2) b' is not an upper bound for S. Hence b is the least upper bound.

Now, let $S = [0,1) \cup \{ a \} \cup \{ b \}$, with the usual ordering for real numbers on $[0,1)$, and $a \geq x \space \forall x \in [0,1)$ and $b \geq x \space \forall x \in [0,1)$. Let $X = [0,1) \subset S$. We can see that both a and b are upper bounds for X. Using definition B we can see that for every $\epsilon > 0, a - \epsilon \in X$ and also $\epsilon > 0, b - \epsilon \in X$. Therefore a and b are both least upper bounds for X.

I was told this by my analysis lecturer a while ago as proof that, while partially ordered sets have a unique least upper bound, subsets of partially ordered sets can have more than one least upper bound, but I never fully understood how it could be true since by definition A, either $a \leq b$ or $b \leq a$.

My question is: why does it seem as if the two equivalent definitions give opposite results?

-
What "two definitions", and what "opposite results"? The second definition does not make sense for arbitrary partially ordered sets, because "$a-\epsilon$" and "$b-\epsilon$" has no meaning unless $a$ and $b$ are real numbers and $\lt$ refers to the usual ordering of real numbers. So you cannot really use Definition B with your example, since definition B assumes you are dealing with $\mathbb{R}$ with its usually ordering. As to your lecturer, he may have said that in partially ordered set, a set may have more than one minimal upper bound (which is true). –  Arturo Magidin Nov 20 '11 at 4:18

Definition A explicitly talks about subsets of real numbers, but in fact is perfectly applicable to any partially ordered set. By contrast, your Definition B does not explicitly say it is about real numbers, but in fact is only about subsets of the entire real numbers with the usual ordering.

In fact, we don't just talk about "least upper bound" when dealing with partially ordered sets, we talk about "least upper bound in $X$".

Your argument for equivalence assumes in fact that you are dealing with all of $\mathbb{R}$: to see how it can fail, consider the totally ordered subset of the real numbers given by $X=[0,1)\cup\{2\}$. Let $S=[0,1)$. Then $\{2\}$ is a least upper for $S$ in $X$, but your argument breaks down, since for $\epsilon=\frac{1}{2}$ we have that every $s\in S$ satisfies $s\leq 2-\frac{1}{2}$; yet $2$ is the least upper bound of the set $S$ in $X$, even though it does not satisfy Definition 2. The reason is that although, within the set of real numbers, $2-\epsilon$ "works" as an upper bound for $S$, this element is not in $X$; not being a member of the club of elements of $X$, it does not qualify to be a least upper bound in $X$, let alone the least upper bound.

So, definition A is valid in arbitrary partially ordered sets. Definition B is only equivalent to Definition A in some contexts, e.g., when dealing with the set of all real numbers in their usual ordering.

As far as what your lecturer said, it's hard to go by second-hand reports. It is possible that he said that in a partially ordered set $X$, a subset $S$ may have more than one minimal upper bound: an element $b\in X$ is a minimal upper bound for $S$ if and only if $s\leq b$ for all $s\in S$, and if $a$ is an upper bound for $S$ and $a\leq b$, then $a=b$.

As to your example, it does not really work because "$a-\epsilon$" has no inherent meaning; it can only mean something if you have an operation defined that allows you to subtract $\epsilon$ from $a$; since your $a$ and $b$ are not actually a real numbers (at least, not under the usual ordering) you cannot talk about $a-\epsilon$ directly; you have to explain what that means. And I would say that $a$ and $b$ are minimal upper bounds rather than "least upper bounds", since they both fail Definition A (which is the one that is applicable in generality).

I also want to note that your argument that Definition A and B are equivalent is badly phrased (possibly because you are talking about (1) and (2) and don't specify if you are talking about definition A or definition B). You should assume that $b$ satisfies (A) and prove that it satisfies (B) (you essentially do this, but you are assuming that your set is all of $\mathbb{R}$, or at least dense), and then assume that $b$ satisfies (B) and prove it satisfies (A).

-
Yes you're right. He didn't use my "proof" (which I contrived out of mental gymnastics to make it work). Now I remember that the confusion arose because he called least upper bounds what the text called minimal upper bounds and vice versa. Thankyou for your answer. –  anonymous Nov 20 '11 at 5:07