Go backward to 7.1 Equivalence Relations and PartitionsGo up to 7 More on RelationsGo forward to 7.3 Graphs |

Ris antisymmetric onS: <=>forallxinS,yinS: (<x,y> inR/\ <y,x> inR) =>x=y.

In the graph representation of an antisymmetric relation, the only loops are
from a node to itself, i.e., the following relation is *not* antisymmetric:

Ris partial order onS: <=>RsubsetSxS/\Ris reflexive onS/\Ris antisymmetric onS/\Ris transitive onS.

- <= is a partial order on
**N**. - subset is a partial order on
**P**(`S`), for every set`S`. - | (divides) is a partial order on
**N**.

**Quasi Orders**
Frequently, a partial order is denoted as infix **<=** (or simply as
<= ); a corresponding relation **<** is then defined as

While

x<y: <=>x<=y/\x!=y.

Ris irreflexive onS: <=>forallxinS: <x,x> not inR.

The graph representation of an irreflexive relation does not contain direct
loops from a node to itself, i.e., the following relation is
*not* irreflexive:

Ris quasi order onS: <=>RsubsetSxS/\Ris irreflexive onS/\Ris antisymmetric onS/\Ris transitive onS.

The graph representation of an quasi order does not contain any (direct or
indirect) loops, i.e., the following is *not* a quasi-order:

forallS,<:<is quasi order onS=><is antisymmetric onS.

Consequently, the only difference between partial orders and quasi orders is reflexivity versus irreflexivity. Furthermore, the following holds.

forallS,<=:<=is partial order onS=><is quasi order onS.

Therefore adding equality to a quasi order makes it a partial order and removing equality from a partial order makes it a quasi order.

- < is a quasi-order on
**R**. - proper subset (proper subset) is a quasi-order on
**P**(`S`), for every set`S`.

In a partial order or quasi order, not all elements are necessarily
comparable, e.g., in **P**({0, 1, 2}) neither {0, 1} subset {1,
2} nor {1, 2} subset {0, 1}.

xandyare incomparable w.r.t.<=: <=>xnot<=y/\ynot<=x.

**Total Orders**
Some partial orders do not have incomparable elements.

Ris total order onS: <=>Ris partial order onS/\~ existsxinS,yinS:xandyare incomparable w.r.t.R.

- <= is a total order on
**R**. - The
*lexicographic order (lexikographische Ordnung)*

is a total order on`x`**<=**`y`: <=>`x`_{0}<`y`_{0}\/ (`x`_{0}=`y`_{0}/\`x`_{1}<=`y`_{1})**N**x**N**. In this order, we have

i.e., tuples are ordered first by their first component and then by their second component.<0, 0> **<**<0, 1>**<**<0, 2>**<**...**<**<1, 0>**<**<1, 1>**<**<1, 2>**<**... - Let
**<=**be a total order on an alphabet`A`, let`W`_{n}:=**N**_{n}->`A`be the set of all words with`n`letters, and let

be the function that removes the first letter from word:=`w`**such**`u`in`W`_{n-1}:**forall**`i`in**N**_{n-1}:`u`_{i}=`w`_{i+1}`w`. The lexicographic order**<=**_{n}subset`W`_{n}x`W`_{n}defined as

is a total order. If`w`**<=**_{n}`u`: <=>`n`= 0 \/`w`_{0}**<**`u`_{0}\/ (`w`_{0}=`u`_{0}/\<=`w`_{n-1})`u``A`is the set of Roman letters, we have"back"

**<**_{4}"bare"**<**_{4}"base"**<**_{4}"bear"**<**_{4}"bend"**<**_{4}"care"

**Hasse Diagrams**
Like any binary relation, a partial order can be represented by a directed
graph, e.g.

A more economical visualization that utilizes the properties of partial order
is provided by a *Hasse diagram (Hasse Diagramm)*. Such a diagram is an
undirected graph were all edges are considered as arrows from bottom to top,
i.e., smaller elements are placed lower:

The graph for the corresponding partial order is constructed by directing the
edges from bottom to top, by adding loops to all nodes (because of
reflexivity) and by adding direct arrows between all nodes that are indirectly
connected by two or more arrows (because of transitivity). E.g., the
relationship `a` **<=** `d` is not denoted by an extra edge but
can be deduced from the relationship `a` **<=** `b` and
`b` **<=** `d` in the diagram.

- This Hasse diagram illustrates the total order <= on
**N**_{5}. - This Hasse diagram illustrates the partial order
subset on
**P**({1, 2, 3}): - This Hasse diagram illustrates the partial order subset on
{{0}, {1}, {2}, {0, 1}, {1, 2}, {0, 1, 2}}: - Let
`F`_{n}:= {`m`in**N**:`m`|`n`} (the factors of`n`). The following Hasse diagram illustrates the partial order | on`F`_{12}:

**Logic Evaluator**
Above definitions can be implemented as
shown below (see Appendix * order.txt*):

**More Notions**
Various notions that we have introduced for the total ordering <= on
**R** can be generalized to partial orders.

Correspondingly, if

xis least element ofSw.r.t.<=: <=>xinS/\forallyinS:x<=y.

xis greatest element ofSw.r.t.<=: <=>xinS/\forallyinS:y<=x.

We can show that a least respectively greatest element is unique, if such an element exists.

**0**is the least element of**P**({1, 2, 3}) with respect to subset , {1, 2, 3} is the greatest element:- The following Hasse diagram denotes a partial order with greatest
element
`a`but without a least element:

Correspondingly, if

xis minimal element ofSw.r.t.<=: <=>xinS/\forallyinS:y<=x=>y=x.

xis maximal element ofSw.r.t.<=: <=>xinS/\forallyinS:x<=y=>x=y.

Minimal and maximal elements are not necessarily unique: distinct incomparable minimal respectively maximal elements may exist.

Correspondingly, a value

xis lower bound ofSw.r.t.<=: <=>forallyinS:x<=y.

xis upper bound ofSw.r.t.<=: <=>forallyinS:y<=x.

Please note that an lower (respectively upper bound) of a set `S` need
not be an element of `S`:

Correspondingly, a value

xis infimum ofSw.r.t.<=: <=>xis lower bound ofSw.r.t.<=/\forally:yis lower bound ofSw.r.t.<==>y<=x.

xis supremum ofSw.r.t.<=: <=>xis upper bound ofSw.r.t.<=/\forally:yis upper bound ofSw.r.t.<==>x<=y.

Even the supremum respectively infimum of a set need not be an element of this set. However, we have the following relationships between the concepts defined above.

xis least (greatest) element ofSw.r.t.<==>xis minimal (maximal) element ofSw.r.t.<=,xis least (greatest) element ofSw.r.t.<==>xis infimum (supremum) ofSw.r.t.<=,xis lower (upper) bound ofSw.r.t.<=/\xinS=>xis least (greatest) element ofSw.r.t.<=.

**Logic Evaluator**
Some of above definitions can be implemented as shown below, see Appendix * order.txt*.

Author: Wolfgang Schreiner

Last Modification: October 4, 1999