Partial Ordering

Another important type of ordering on a set A is a partial ordering. A relation $\Re$ on a set A is called a partial ordering or partial ordering relation if the following three properties all hold

1.

     $(a,a) \in \Re$     -     reflexive law

2.

    if $(a,b) \in \Re$ and $(b,c) \in \Re$ then $(a,c) \in \Re$     -     transitive law

3.

    if $(a,b) \in \Re$ and $(b,a) \in \Re$ then a = b    -     anti-symmetric law

The reflexive and transitive properties are the same as those for an equivalence relation. However, a partial ordering is characterised by the anti-symmetric property (3) which says that whenever $a \Re b$ and $b \Re a$, then a = b.

Such a partial order is also referred to as a weak partial order. A weak partial order is characterised by the reflexivity property, that is the statement $a \enskip \Re \enskip a$ is always true. On the other hand, a strong partial order, is characterised by the properties of irreflexivity and transitivity, that is

1.

    not $(a,a) \in \Re$ -     irreflexive property

2.

    if $(a,b) \in \Re$ and $(b,c) \in \Re$ then $(a,c) \in \Re$     -     transitive property

A set on which there is a partial ordering is called a partially ordered set or poset. Some examples should help to clarify these ideas.