# Partial Order/Upper Bound Proof from How to Prove It

1. Sep 1, 2010

### zooxanthellae

Partial Order/Upper Bound Proof from "How to Prove It"

1. The problem statement, all variables and given/known data
Suppose R is a partial order on A and B is a subset of A. Let U be the set of all upper bounds for B. Prove that U is closed upward; that is, prove that if x E U and xRy then y E U.

2. Relevant equations

N/A

3. The attempt at a solution

This is Velleman's:

Suppose that x E U and xRy. To prove that y E U, we must show that y is an upper bound for B, so suppose that b E B. Since x E U, x is an upper bound for B, so bRx...

The proof goes on, but I am stuck at the bolded part. How do we know that the relation R is a relation such that, if x > b, then bRx? What if the relation R is defined as: {(x,y) E A x A | x >= y}? Isn't my definition of R reflexive, transitive, and antisymmetric, and therefore partially ordered, as the given states? And wouldn't my definition then mean that, if x > b, it is not true that bRx? Where am I going wrong?

2. Sep 1, 2010

### Office_Shredder

Staff Emeritus
Re: Partial Order/Upper Bound Proof from "How to Prove It"

What you wrote is a partial order, but obviously the author intended this partial order is xRy if x<y

3. Sep 1, 2010

### zooxanthellae

Re: Partial Order/Upper Bound Proof from "How to Prove It"

But, taking my literalist, unsubtle (more charitably: rigorous) approach, is my objection valid?

4. Sep 2, 2010

### HallsofIvy

Re: Partial Order/Upper Bound Proof from "How to Prove It"

No, it is not. There is no "< " defined. The author is taking "aRb" as the order relation and defining "upper bound" in terms of that relation. Saying that "x is an upper bound on set B then, by definition of "upper bound", bRx for all b in B.

You cannot object to a statement in terms of symbols or relations that have not been defined for that particular statement.

5. Sep 2, 2010

### zooxanthellae

Re: Partial Order/Upper Bound Proof from "How to Prove It"

But how is he able to say that bRx immediately follows if x >= all b in B?

6. Sep 2, 2010

### Hurkyl

Staff Emeritus
Re: Partial Order/Upper Bound Proof from "How to Prove It"

He didn't. He said that bRx follows from x being an upper bound for B.

You have thoroughly confused yourself by introducing a second partial order and mixing the two of them up.

If you're studying two orders at once, you really should qualify all order-related terms so you know which order it's related to.

7. Sep 2, 2010

### zooxanthellae

Re: Partial Order/Upper Bound Proof from "How to Prove It"

Wait, how is what I said different from what you said? Isn't an upper bound defined as an element that is greater than or equal to every element in some subset?

In other words, how is "x >= all b in B" different from "x being an upper bound for B"?

8. Sep 2, 2010

### Hurkyl

Staff Emeritus
Re: Partial Order/Upper Bound Proof from "How to Prove It"

Yes. But don't confuse the order R with the order $\leq$. "x is greater than or equal to y" literally means "yRx" in this order!

9. Sep 2, 2010

### zooxanthellae

Re: Partial Order/Upper Bound Proof from "How to Prove It"

>_< How can I not confuse R with <= when you've just said that x >= y implies yRx; in other words, x <= y implies xRy!

10. Sep 2, 2010

### Hurkyl

Staff Emeritus
Re: Partial Order/Upper Bound Proof from "How to Prove It"

I never said I am using the word "greater" relative to the ordering $\leq$!

11. Sep 2, 2010

### zooxanthellae

Re: Partial Order/Upper Bound Proof from "How to Prove It"

I think I'm going to re-read the chapter this question comes from. It's pretty clear I don't understand it very well, since I still can't understand the last post!

Topic closed, for the time being, I suppose?