1. ## Partially ordered set.

Let X be a set with a binary operation p: X x X -->X,
abbreviated to p(x,y)=xy. Suppose p satisfies

1) x(yz)=(xy)z
2) xy=yx
3) xx=x

for all x, y, z in X. Define < on X by

x<y iff xy=y.

Prove that

a) (X,<) is a partially ordered set.

b) Each pair of elements has a least upper bound. That is, given x, y in X, there is a z in X, such that x<z, y<z, and if w in X is such that x<w, y<w, then z<w.

2. Originally Posted by Cairo
Let X be a set with a binary operation p: X x X -->X,
abbreviated to p(x,y)=xy. Suppose p satisfies

1) x(yz)=(xy)z
2) xy=yx
3) xx=x

for all x, y, z in X. Define < on X by

x<y iff xy=y.

Prove that

a) (X,<) is a partially ordered set.

b) Each pair of elements has a least upper bound. That is, given x, y in X, there is a z in X, such that x<z, y<z, and if w in X is such that x<w, y<w, then z<w.

Does it satisfy the three conditions (reflexive, antisymmetric, and transitive)? For example 2) tells you something about symmetry...

3. I'm not sure what you mean here.

This is all that is stated in the question.

4. Originally Posted by Cairo
I'm not sure what you mean here.

This is all that is stated in the question.
Do you know what a partial ordering is?

5. A partial ordering is reflexive, transitive and antisymmetric.

Is (1) showing transitivity, (2) showing antisymmetric and (3) showing reflexivity?

I'm not sure how to proceed from here!

6. What you need is to take the definition of reflexivity and substitute the definition of < there. You will get an equation. See if you can derive that equation from the three given equations. If you are able, then < is reflexive.

By the way, it seems to me that (X, <) is indeed a non-strict (or reflexive, or weak) partial order. While in mathematics one can use any notation as long as one explains what exactly it means, it is better to use suggestive notations. (E.g., the set of functions from $\displaystyle A$ to $\displaystyle B$ is sometimes denoted $\displaystyle B^A$ to remind that the size of this set is $\displaystyle |B|^{|A|}$.) Here, it is better to denote the relation with <= because in regular use, < means strict, or irreflexive, order.

If you need an intuitive illustration, you can think of X as a family of sets, the binary operation as intersection and the order as the subset relation.

7. (1) showing transitivity:
you need to show that if x<y,y<z,then x<z.
(2) showing antisymmetric:
you need to show that if x<y, and y<x, then x and y are the same elements.
(3) showing reflexivity:
you need to show that: x<x for all x in X.
for (b), the existence of upper bound: take z=xy.
Actually, xy is the least upper bound of x and y. I leave it to you to prove this statement.
Hint: you need to prove If x<w, y<w, then xy<w.

8. Ok...

So my proof starts

Since xx=x (by 3), x<x for each x in X and so is reflexive.

Since xy=y=yx (by 2), then x=y and is antisymmetric.

I'm lost when it comes to transitivity....

I thought

If x<y and y<z, then xy=y and yz=z, so x<z is xyyz=xyz (by 3) but then get in a mess!

Is any of this right?

9. Originally Posted by Cairo
Ok...

So my proof starts

Since xx=x (by 3), x<x for each x in X and so is reflexive.

Since xy=y=yx (by 2), then x=y and is antisymmetric.

I'm lost when it comes to transitivity....

I thought

If x<y and y<z, then xy=y and yz=z, so x<z is xyyz=xyz=xz (by 3)
Is any of this right?
You are done.

10. Sometimes it is difficult to see the wood through the trees!

Thanks for this Plato.

Now that I have the bones of the proof, can anybody offer a way to make it look more elegant?

11. My proof

A partial order on a set X is a reflexive, antisymmetric and transitive relation.
For all x in X, we have xx=x (by 3), and so x<x. Therefore < is reflexive.
If x<y and y<x, then by definition xy=yx=y (by 2). That is x=y and so < is antisymmetric.
If x<y and y<z, then by definition of < we have xy=y and yz=z.
Now, xyyz=x(yy)z=xyz=xz (by 1 and 3). Hence, x<z, and < is transitive.
Since < is reflexive, antisymmetric and transitive, < is a partial order on X.
That is (X,<) is a partially ordered set.

I'not entirely convinced the proof is correct. Firstly, the domain is the Cartesian product, so should my proof start with
for all (x,x) in X x X, we have xx=x (by 3), and so x<x ?
I'm also not comfortable with transitivity. I have shown that xyyz=xz, but surely x<z should be xz=z. have I missed something here?
Finally, what do people think of the way the proof is set out? Could it be tidied up in any way?

12. If $\displaystyle x<y~\&~y<z$ we know that $\displaystyle xy=y~\&~yz=z$.
It follows that $\displaystyle xz=x(yz)=(xy)z=yz=z$.

13. Thanks Plato.

Does the rest follow OK? I ask, because this year we have been told that full credit will only be awarded if both the soultion is correct, aswell as being carefully and logically presented.

14. To prove the second part of the question.

Let z=xy in X, for x,y in X.

Then, x<z implies x(xy)=xy implies (xx)y=xy implies xy=xy.

Also, y<z implies y(xy)=xy implies (yx)y=xy implies (xy)y=xy implies x(yy)=xy implies xy=xy.

Now, if w in X, and x<w implies xw=w, and y<w implies yw=w, then z<w implies (xy)w=w implies x(yw)=w implies xw=w implies w=w.

Hence, each pair of elements has a least upper bound.

Is this even remotely correct?