Order Relations

Order relation

A relation $R$ on a set $A$ is called an order relation if $R$ has the following three properties:

• For any $a\in A$, there is $aRa$. This means that $R$ is reflexive.

• For any $a,b \in A$, if $aRb$ and $bRa$, then $a=b$. This means that$R$ is antisymmetric.

• For any $a,b,c \in A$, if $aRb$ and $bRc$, then $aRc$. This means that $R$ is transitive.

The relation $R$ is called a partial order, and the set $A$ is said to be partially ordered under this relation. An ordered set is the term used to describe a set $A$ that is partially ordered. Additionally, poset is commonly used as an abbreviation for a partially ordered set.

Note: We will interchangeably use both terms, i.e., order relation and partial order, to become comfortable with using both terms.

For a set $S$, we call an order relation $R$ a partial order because some of the elements of $S$ are not related to each other under $R$. For some $a,b \in S$, $a R b$ is read as $a$ precedes $b$. It can also be read as $b$ succeeds $a$.

Examples

The subset relation is a partial order for any set of the sets. Let $\cal C$ be a collection of sets. For some $A, B \in \cal C$ ...