Feedback | Hist | India | Other Sites | Math | Theol | Th Phys | Time | Translit

Catend Study pointer

Two Definitions of Partially Ordered Sets

There are two definitions of a partially ordered set (abbreviated to 'poset'), each having its own advantages and disadvantages.

DEFINITION I. Let R be a binary relation on the set A such that for any elements a, b, c of A,

                  1. aRa  
                  2. aRb & bRa ==> a=b
                  3. aRb & bRc ==> aRc

DEFINITION II. Let < be a relation on the set A such that for any elements a, b, c of A,

                  i.  not a<a
                  ii. a<b & b<c ==> a<c

LEMMA 1. Definitions I, II agree if R is '< or ='.

Proof. We first show that Defn. II implies Defn. I if R is interpreted as '< or ='. Clearly 1 holds because a=a. For 3, if aRb & bRc, then either a=b=c (so a=c), or a=b<c, or a<b=c (both giving a<c), or a<b<c (so a<c by ii). Finally, 2 holds because its left hand side tells us that either a<b & b<a (giving a<a by ii; which contradicts i), or a=b & b<a, or a<b & b=a (both giving a<a again), or a=b=a as desired.

Now we show that Defn. I implies Defn. II. Given the relation R, we define the relation < on A by

(1)               a<b iff aRb & a=/=b.

Hence             aRb iff a<b or a=b.

To prove i: the negative of (1) gives

           (not aRb or a=b) ==> not a<b.

Putting b=a enables us to argue:

        a=a ==> (not aRa or a=a) ==> not a<a.

For ii:

        a<b & b<c ==>  a<b & b<c & (a=c or a=/=c)
                  ==> (aRb & bRc & b=/=a,c & a=c) 
                            or (aRb & bRc & b=/=a,c & a=/=c)
                  ==> (aRb & bRa & b=/=c & a=c) or (aRc & a=/=c)
                  ==> (b=a & b=/=c & a=c) or a<c
                  ==>  a<c.
Up to Mathematics page.

Copyright (C) Anthony P. Stone 1996. This material may be freely used, provided the author is acknowledged.

Last updated: 04 January 2005