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.
PLEASE HELP!!!!
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 to is sometimes denoted to remind that the size of this set is .) 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.
(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.
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?
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?
Thanks in advance.
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?