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

# 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