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$, we write $A\subseteq B$if $A$ is a subset of $B$.

• As every set is a subset of itself, this means that $\subseteq$ is a reflexive relation.

• For any sets $A, B \in \cal C$, if $A\subseteq B$ and $B\subseteq A$, then $A=B$. This means that $\subseteq$ is an antisymmetric relation.

• For any sets $A, B, C \in \cal C$, if $A\subseteq B$ and $B\subseteq C$ , then $A\subseteq C$. This means that $\subseteq$ is a transitive relation.