Re: about nonreflexivity of order relation

Some definitions.

A relation R is
reflexive iff and x R x for all x;
irreflexive iff not (x R x) for all x;
symmetric iff x R y implies y R x for all x and y;
asymmetric if x R y implies not (y R x) for all x and y;
antisymmetric iff x R y and y R x implies x = y for all x and y;
transitive iff x R y and y R z implies x R z for all x, y, and z;
total iff x R y or y R x (or both) for all x and y, and
dichotomous iff exactly one of x R y, y R x, or x = y holds for all x and y.

(See, for example, http://en.wikipedia.org/wiki/Binary_relation#Relations_over_a_set .)

A weak partial order is a relation that is reflexive, antisymmetric, and transitive.
Examples: <= on the reals, set inclusion on a collection of sets, divisibility on the positive integers.

A strict partial order is a relation that is irreflexive and transitive.
Examples; < on the reals, strict inclusion on a collection of sets, (x | y but x != y) on the positive integers.

A weak total order is a total weak partial order.
Example: <= on the reals.

A strict total order is a dichotomous strict partial order.
Example: < on the reals.

As far as the word "order" by itself is concerned, there is inconsistency of the literature. You need to check what the author means. For Munkres, an "order relation" is a strict total order.

Exercises

Show:
Totality implies reflexivity.
Dichotomy implies irreflexivity and asymmetry.
No dichotomous relation is reflexive
No dichotomous relation is total.
A strict partial order is asymmetric.
A strict total order is not a total relation.
If R is a strict partial order, then (x R y or x = y) is a weak partial order.
If R is a strict total order, then (x R y or x = y) is a weak total order.
If R is a weak partial order, then (x R y and x != y) is a strict partial order.
If R is a weak total order, then (x R y and x != y) is a strict total order.

Come up with an antisymmetric, transitive relation (on some some set) that is not a weak partial order.

For N^2 (i.e., the set of ordered pairs of natural numbers), come up with orders which are
a) weak partial but not total;
b) strict partial but not total;
c) weak total, and
d) strict total.

--
Stephen J. Herschkorn sjherschko@xxxxxxxxxxxx
Math Tutor on the Internet and in Central New Jersey

.

Relevant Pages

  • Re: Data structures for checking consistency of a partial order?
    ... datastructure for checking the consistency of a partial order. ... A multi-dimensional array would be one possibility. ... equivalent to computing the transitive closure, ... that is inconsistent with the total order, ...
    (comp.programming)
  • Re: Data structures for checking consistency of a partial order?
    ... datastructure for checking the consistency of a partial order. ... thereby forming a "temporary" total ordering: ... that is inconsistent with the total order, ... find dogs that are bigger than horses), ...
    (comp.programming)
  • Re: Details about pythons set implementation
    ... isn't this the normal definition? ... Mathematically speaking, it is an order, and a very useful one. ... it's a partial order, which means that if a!= b then they are not ... What you need is a total order, where any two distinct elements are ...
    (comp.lang.python)
  • Re: Efficient Vector Comparison
    ... Yeah, I do not have a total order, but I do not need such total order. ... They are in a partial order, ... if this vector set is partial ordered? ...
    (comp.programming)