# Order Relation

1. May 3, 2005

### laminatedevildoll

How do I verify that R={(1,1). (2,2), (3,3) (3,2) (3,1), (2,1)} is an order relation on {1,2,3}.

So far, I have that an ordered set is a pair (X, <) where X is a set tand where < in a binary relation on X so that the following three properties are fulfilled:

1. reflexive prop
2. anti-symmetric prop
3. transitive prop

Do I have to prove each property for R?

2. May 3, 2005

### HallsofIvy

Staff Emeritus
Yes, and the simplest way to check is just go through the pairs.

Reflexive: Are (1,1), (2,2), (3,3) in the set?

Anti-symmetric: (2, 1) is in the set. If this relation is anti-symmetric, (1, 2) must not be in the set. Is that true? What other pairs do you have to look at?

Transitive: I see (3,2) and (2,1) in the set. If this relation is transitive, what pair must be in the set? Is it?

3. May 3, 2005

### laminatedevildoll

Reflexive: (1,1), (2,2), (3,3) are in the set.

Anti-symmetric: (2, 1) is in the set. If this relation is anti-symmetric, (1, 2) must not be in the set. Yes this is true. So, this property is true.

Transitive: (3,2) and (2,1) are in the set. If this relation is transitive, then (3,1) must be in the set.

Let x,y be in R.

If y precedes x if and only if y less than or equal to x, the, do I verify that this statement is an order relation like before using the three properties? If I use the three properties, then how can I prove that y precedes x.

This is how I started off:

Reflexive Property:
If x in an element in R, then x < x for all x in R. Therefore, x precedes x.

Anti-symmetric:
For all x,y in R if x<y y< x then, x=y, where y precedes x.

Last edited: May 3, 2005
4. May 4, 2005

### HallsofIvy

Staff Emeritus
I was giving an example! (2,1) is not the only pair you need to check.

You mean x<= x (or [itex]x\le x[/tex]), of course.

5. May 4, 2005

### honestrosewater

I can't really follow what you're saying. You have two order relations here: R and <. And you've defined R to be <. So you really have nothing to prove- just check your definition of < - is it an order relation?
Did you want to prove something else? You haven't said on what set the relations are defined, but assume they're defined on {1, 2, 3}. Using the usual definition of <, "y precedes x if and only if y less than or equal to x" means "if y precedes x, then y < x" and "if y < x, then y precedes x". So R = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)}. Is this what you meant to say?
I think you only meant "For all x and y in R, if (y, x) is in R, then y < x." That also means if y > x, then (y, x) is not in R. Is that what you wanted?

6. May 4, 2005

### laminatedevildoll

This is actually unrelated to the previous problem. But, I think that I have to go through the three properties of an order relation to prove this.

The problem:

Let x,y is an element in R, real number. We define a relation <= (precedes symbol) on R. Verify that <= (precedes symbol) defined by

x<= (precedes) y if and only if y<= x (less than or equal to)

Verify that <= (precedes symbol) is an order relation.

Last edited: May 4, 2005
7. May 4, 2005

### laminatedevildoll

Similarly, (3,2) and (3,1) are also anti-symmetric since (2,3) and (1,3) are not on the set, right?

8. May 5, 2005

### honestrosewater

Okay, you said before that y precedes x iff y < x. Let P denote the relation "precedes" and L denote the relation "less than or equal to". So now instead of P = L, you have that (x, y) is in P iff (y, x) is in L. In other words,
P = {(x, y) : (y, x) is in L and x and y are in R}.
What else does P equal (what is the relationship between P and L)?

9. May 5, 2005

### laminatedevildoll

Do you mean this relationship?

P={(x,y): x P y if y L x}

or do I have to jump into the reflexive property?

10. May 5, 2005

### honestrosewater

I mean that P and L are inverses. Remember that binary relations are sets of pairs. You're told that if (x, y) is in L, then (y, x) is in P, and if (y, x) is in P, then (x, y) is in L. In other words, L and P contain the same pairs- just reversed. If (x, x) is in L, then (x, x) is in P. If (x, y) and (y, z) are in L, then (y, x) and (z, y) are in P.
In order to prove that P is an order relation, you need to know that L is an order relation. Otherwise, you could only prove that if L is an order relation, then P is an order relation. But assume you already know L is an order relation. Then the following holds:
For all x, y, and z in R
1) (x, x) is in L.
2) If (x, y) and (y, x) are in L, then x = y.
3) If (x, y) and (y, z) are in L, then (x, z) is in L.
L and P have the same pairs- just reversed, so:
For all x, y, and z in R
4) (x, x) is in P.
Can you see the rest now? To see the rest, highlight:
5) If (y, x) and (x, y) are in P, then y = x.
6) If (y, x) and (z, y) are in P, then (z, x) is in P.
To make it even clearer, (6) can be rewritten as
7) If (z, y) and (y, x) are in P, then (z, x) is in P.
So (4), (5), and (7) show that P is an order relation. Notice that P is usually called "greater than or equal to" :)

Does that make sense?

11. May 5, 2005

### laminatedevildoll

Yes, it makes sense. I got confused with the "precedes" symbol, when in reality it somewhat refers closely to the "less than or equal to" sign. Thank you.