1
$\begingroup$

This is one of the problem I have been solving from Velleman's How to prove book;

Suppose $R$ is a partial order on $A$ and $B \subseteq A$. Let $U$ be the set of all upper bounds for B. Prove that if $x$ is the greatest lower bound of $U$, then $x$ is the least upper bound of $B$.

Even though I have worked out the proof with an concrete example, I'm not able to prove it. This is one of my attempt:

Suppose $x$ is the greatest lower bound of $U$. Let $a$ be an arbitrary element in $A$. $a$ will be in $U$ if $\forall b \in B(bRa)$. $a$ will be in the lower bound of $U$ if $\forall u \in U (aRu)$. Since $x$ is the greatest lower bound of $U$ it follows that $aRx$. Suppose $b$ be an arbitrary element in $B$. From $\forall b \in B(bRa)$, it follows that $bRa$. From $bRa$ and $aRx$, it follows that $bRx$.

I'm stuck in this position. Can somebody point me out what I'm doing wrong ?

$\endgroup$
2
$\begingroup$

You need to show two things:

  • that $x$ is an upper bound for $B$, i.e., that $b\mathrel{R}x$ for each $b\in B$, and
  • that $x$ is the least upper bound for $B$, i.e., that if $y\in A$ and $b\mathrel{R}y$ for all $b\in B$, then $x\mathrel{R}y$.

You’ve tried to do the first, but your argument is a bit confused. For one thing, it starts in the wrong place: you want to show that $x$ is an upper bound for $B$, so you should be starting with an arbitrary $b\in B$ and trying to show that $b\mathrel{R}x$. This isn’t too hard: if $b\in B$, then $b\mathrel{R}u$ for each $u\in U$, so $b$ is a lower bound for $U$, and therefore $b\mathrel{R}x$. Thus, $x$ is an upper bound for $B$, and it only remains to show that $x$ is the least upper bound for $B$.

Suppose that $y$ is any upper bound for $B$. Then $b\mathrel{R}y$ for each $b\in B$, so $y\in U$. But then ... ?

$\endgroup$
  • $\begingroup$ Why are you concluding $u R x$ ? Shouldn't it be $b R x$ ? $\endgroup$ – Sibi Apr 12 '15 at 20:38
  • $\begingroup$ @Sibi: It should indeed; that was a typo. $\endgroup$ – Brian M. Scott Apr 12 '15 at 20:58
  • $\begingroup$ Any ideas for the second part ? All I can come up with is $y R x$ from the assumption that $x$ is the greatest lower bound of $U$. Unfortunately, that is not leading me anywhere. I can apply transitive property, but it just gives me $bRx$ which is proved already. $\endgroup$ – Sibi Apr 12 '15 at 21:24
  • $\begingroup$ @Sibi: The fact that $x$ is a lower bound for $U$, together with the fact that $y\in U$, tells you that $x\le y$, which is exactly what you want. $\endgroup$ – Brian M. Scott Apr 12 '15 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.