I need to show that relation R is partial order relation.

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

,

Can someone explain me this?

Printable View

- Apr 16th 2006, 05:45 AMOReillyPartial order relation
I need to show that relation R is partial order relation.

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

,

Can someone explain me this? - Apr 16th 2006, 10:00 AMThePerfectHackerQuote:

Originally Posted by**OReilly**

and thus,

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. - Apr 16th 2006, 01:42 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

- Apr 16th 2006, 01:59 PMThePerfectHackerQuote:

Originally Posted by**OReilly**

Thus by antisymettry we have that if, for all

and then, .

The antisymettric property would be violated if, there exists

and the,

But notice that the latter never happens because the, pairs,

are not elements of .

Thus, the antisymmetric propetry is never violated and thus this ordering relation is antisymettric. - Apr 17th 2006, 05:20 AMOReillyQuote:

Originally Posted by**ThePerfectHacker**

For example: relation is reflexive, symmetric and transitive.

Is it anti-symmetric? - Apr 17th 2006, 07:57 AMrgep
Yes. To violate the anti-symmetry property you have to have x and y such that and and . The relation 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. - Apr 17th 2006, 08:04 AMThePerfectHacker
I have a feeling OReilly is gonna learn Zorn's Lemma soon.

- Apr 17th 2006, 08:08 AMThePerfectHacker
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.

- Apr 17th 2006, 09:58 AMOReilly
Well, I think I understood it, but still don't feel it! :rolleyes:

Let me show another example of relation:

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: - Apr 17th 2006, 11:24 AMThePerfectHackerQuote:

Originally Posted by**OReilly**

Quote:

Originally Posted by**OReilly**

Quote:

Originally Posted by**OReilly**

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 is an element such as 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 . Meaning If then .

---------

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. - Apr 17th 2006, 01:34 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

I am still far, far away of understanding that...

Hopefully, I will get there (I know i will)!