Order Relations

Learn about order relations, the usual order, and the dual order.

Order relation

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

  • For any aAa\in A, there is aRaaRa. This means that RR is reflexive.

  • For any a,bAa,b \in A, if aRbaRb and bRabRa, then a=ba=b. This means thatRR is antisymmetric.

  • For any a,b,cAa,b,c \in A, if aRbaRb and bRcbRc, then aRcaRc. This means that RR is transitive.

The relation RR is called a partial order, and the set AA is said to be partially ordered under this relation. An ordered set is the term used to describe a set AA 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 SS, we call an order relation RR a partial order because some of the elements of SS are not related to each other under RR. For some a,bSa,b \in S, aRba R b is read as aa precedes bb. It can also be read as bb succeeds aa.

Examples

The subset relation is a partial order for any set of the sets. Let C\cal C be a collection of sets. For some A,BCA, B \in \cal C, we write ABA\subseteq Bif AA is a subset of BB.

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

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

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

Get hands-on with 1200+ tech skills courses.