# Partial order relation

• April 16th 2006, 06:45 AM
OReilly
Partial order relation
I need to show that relation R is partial order relation.
$R = \{ (a,a),(b,b),(c,c),(a,b),(a,c),(b,c)\}$

I see that it is reflexive and transitive, but I don't see that is antisymmetric.

In the book stands that it is antisymmetric because
$(a,b) \in R \wedge (b,a) \notin R$, $(a,c) \in R \wedge (c,a) \notin R,(b,c) \in R \wedge (c,b) \notin R$

Can someone explain me this?
• April 16th 2006, 11:00 AM
ThePerfectHacker
Quote:

Originally Posted by OReilly
I need to show that relation R is partial order relation.
$R = \{ (a,a),(b,b),(c,c),(a,b),(a,c),(b,c)\}$

I see that it is reflexive and transitive, but I don't see that is antisymmetric.

In the book stands that it is antisymmetric because
$(a,b) \in R \wedge (b,a) \notin R$, $(a,c) \in R \wedge (c,a) \notin R,(b,c) \in R \wedge (c,b) \notin R$

Can someone explain me this?

Since there are no elemets such as,
$x\leq y$ and $y\leq x$ thus, $x\not =y$
The anti-symettric property is never violated.

By the anti-symettric property we do not mean to say you can find such elements but rather if they exist then they are equal.
• April 16th 2006, 02:42 PM
OReilly
Quote:

Originally Posted by ThePerfectHacker
Since there are no elemets such as,
$x\leq y$ and $y\leq x$ thus, $x\not =y$
The anti-symettric property is never violated.

By the anti-symettric property we do not mean to say you can find such elements but rather if they exist then they are equal.

I don't understand. Can explain it a little bit more?
• April 16th 2006, 02:59 PM
ThePerfectHacker
Quote:

Originally Posted by OReilly
I don't understand. Can explain it a little bit more?

By $x\leq y$ I mean $xRy$.

Thus by antisymettry we have that if, for all
$x\leq y$ and $y\leq x$ then, $x=y$.
The antisymettric property would be violated if, there exists
$x\leq y$ and $y\leq x$ the, $x\not = y$
But notice that the latter never happens because the, pairs,
$(b,a), (c,a), (c,b)$ are not elements of $\leq$.
Thus, the antisymmetric propetry is never violated and thus this ordering relation is antisymettric.
• April 17th 2006, 06:20 AM
OReilly
Quote:

Originally Posted by ThePerfectHacker
By $x\leq y$ I mean $xRy$.

Thus by antisymettry we have that if, for all
$x\leq y$ and $y\leq x$ then, $x=y$.
The antisymettric property would be violated if, there exists
$x\leq y$ and $y\leq x$ the, $x\not = y$
But notice that the latter never happens because the, pairs,
$(b,a), (c,a), (c,b)$ are not elements of $\leq$.
Thus, the antisymmetric propetry is never violated and thus this ordering relation is antisymettric.

Well, I still don't understand anti-symmetric property.

For example: relation $R = \{ (a,a),(b,b),(c,c)\}$ is reflexive, symmetric and transitive.

Is it anti-symmetric?
• April 17th 2006, 08:57 AM
rgep
Yes. To violate the anti-symmetry property you have to have x and y such that $x \not= y$ and $(x,y) \in R$ and $(y,x) \in R$. The relation $R = \{ (a,a), (b,b), (c,c) \}$ has no such pair.

You may find it easier to work in terms of a strict partial order, which has the properties of being transitive, never reflexive (contains no (x,x)) and antisymmetric (never contains both (x,y) and (y,x)). The difference is that a weak order contains all pairs (a,a), a strict order contains none of them.
• April 17th 2006, 09:04 AM
ThePerfectHacker
I have a feeling OReilly is gonna learn Zorn's Lemma soon.
• April 17th 2006, 09:08 AM
ThePerfectHacker
Another way to look at it is in logic a conditional statement is only fasle when the "if" part is true and "then" part is false. Otherwise it is always true. Thus when the "if" part is always "false" it does not matter what the "then" part is, it must be true. Thus, over here no matter what two ordered pairs you take the "if" part for the anti-symettric property is always false because there are no such paris in opposites. Thus, the anti-symettric property is always true here.
• April 17th 2006, 10:58 AM
OReilly
Well, I think I understood it, but still don't feel it! :rolleyes:

Let me show another example of relation:
$
R = \{ (a,a),(b,b),(c,c),(a,b)\}
$

This relation is reflexive and transitive.

It is not symmetric since there is no pair (b,a).
But it is anti-symmetric because pair (a,b) doesn't have pair (b,a) to which could be compared for anti-symmetric property (if it would have it would be actually symmetric) and since all other pairs are anti-symmetric then whole R is anti-symmetric.

I think I understand whole concept, but I am not comfortable with it.

By the way, what is Zorn's Lemma? :confused:
• April 17th 2006, 12:24 PM
ThePerfectHacker
Quote:

Originally Posted by OReilly
Well, I think I understood it, but still don't feel it! :rolleyes:

Let me show another example of relation:
$
R = \{ (a,a),(b,b),(c,c),(a,b)\}
$

This relation is reflexive and transitive.

It is not symmetric since there is no pair (b,a).
But it is anti-symmetric because pair (a,b) doesn't have pair (b,a) to which could be compared for anti-symmetric property (if it would have it would be actually symmetric) and since all other pairs are anti-symmetric then whole R is anti-symmetric.

Good

Quote:

Originally Posted by OReilly
I think I understand whole concept, but I am not comfortable with it.

Many people are not because it is pure math :)

Quote:

Originally Posted by OReilly
By the way, what is Zorn's Lemma? :confused:

One of the most useful tools in mathematics.

In a partially ordered set no need be that two elements are always comparable. Meaning not related to each other. A chain is a subset of the partially ordered set such as any two elements are comparable to eachother. Another was of looking at the chain as a subset of the ordering relation because everything in an ordering relation is comparable and only those elements can be related to its other elements.

A upper bound of a chain $x\in R$ is an element such as $aRx$ for all elements in the chain.

Zorn's Lemma states that in a partially ordered set such as every chain has an upper bound there exists a maximal element $x$. Meaning If $xRs$ then $x=s$.
---------
Why is it useful?
For example, without it we would never have Analysis. Because in analysis the fundamental property of real numbers is that if there exists a increasing sequence having an upper bound then it must have a minimal upper bound. This is almost the very definition of Zorn's Lemma.
• April 17th 2006, 02:34 PM
OReilly
Quote:

Originally Posted by ThePerfectHacker
One of the most useful tools in mathematics.

In a partially ordered set no need be that two elements are always comparable. Meaning not related to each other. A chain is a subset of the partially ordered set such as any two elements are comparable to eachother. Another was of looking at the chain as a subset of the ordering relation because everything in an ordering relation is comparable and only those elements can be related to its other elements.

A upper bound of a chain $x\in R$ is an element such as $aRx$ for all elements in the chain.

Zorn's Lemma states that in a partially ordered set such as every chain has an upper bound there exists a maximal element $x$. Meaning If $xRs$ then $x=s$.
---------
Why is it useful?
For example, without it we would never have Analysis. Because in analysis the fundamental property of real numbers is that if there exists a increasing sequence having an upper bound then it must have a minimal upper bound. This is almost the very definition of Zorn's Lemma.

You have killed me now! :eek:

I am still far, far away of understanding that...
Hopefully, I will get there (I know i will)!