Let A be a partially ordered set called the alphabet Let B b

Let A be a partially ordered set, called “the alphabet”. Let B be the set of all “words” of length two. Define equal to or less than on W as follows: xy equal to or less than ab if and only if (i) x < a or (ii) x = a and y < b. Prove that less than or equal to is a partial ordering for W.

Solution

Solution:

So we have this alphabet that is partially ordered and we want to show that the ordering relation orders two letter words formed from letters of the alphabet.
The relation says if you have two words, A and B, then AB if the first letter of the world is less or if the first letters are the same, and the second letters are less.

So let\'s start:
We need to show that is a partial order on W.

We need to do three things, first show that any word is to itself
Reflexive:
since x=x and y=y, then any word xy meets condition (ii) and so xyxy

That one was easy, since any letter is equal to itself any string of two letters must be.

Antisymmetric
We need to show that if two words are to each other, they must be the same word.

Suppose xy ab and ab xy
Then we have four possibilities:

x<a and a=x and y b.
Well, x cannot both equal a and be less then it, so this rules out this possibility

x<a and a<x
This possibility is also ruled out

x=a and ab and a<x
This is ruled out since a cannot both equal x and be less than it.

So the last possibility is:
x=a and y b and b y.
This means that y = b since A is a partially ordered set, and since x=a and y=b, then
xy = ab so we have antisymmetry.

Lastly, we need to show transitivity (if xy ab and abwz, then xywz)
Assume that xy ab and abwz

then again four possibilities
a) x<a and a=w and b z
In this case x<w since < is transitive for letters, and so xywz

b) x<a and a<w,
then again x<w, so xywz

c) x=a and y b and a<w, then again x<w (similar to a) and so xywz
finally

d) x=a and y b and a=w and bz
Since x= a= w, then x= w and since y bz then yz, so we\'ve got condition ii) and so
xywz
Hence transitivity of on W has been established.

Since is reflexive, antisymmetric, and transitive, we know that it is a partial ordering for W.