# Partially Ordered Sets

A

partially ordered setis a set \( S \) with a relation \( \le \) on \( S \) satisfying:

(1) \( a \le a \) for all \( a \in S\) (reflexivity)

(2) if \( a\le b \) and \( b\le a \), then \( a=b \) (antisymmetry)

(3) if \( a \le b \) and \( b \le c \), then \( a \le c \) (transitivity)

Note that for two given elements \( a \) and \( b\), it may not be the case that \( a \) and \( b \) arecomparable, that is, \( a \le b \) or \( b \le a \). If this is true for all pairs \( a \) and \( b \) in \( S \), we say that \( S \) istotally ordered.

The set \(S\) of people in the world, with \( \le \) defined by "is a direct descendant of," is a partially ordered set. The set \( T \) of positive integers, with \( \le \) defined by "divides," is a partially ordered set.

Note that neither of these sets are totally ordered. A brother and sister are not comparable in \( S\), since they are not direct descendants of each other; and \( 2 \) and \( 3 \) are not comparable in \( T \), since neither divides the other.

**Cite as:**Partially Ordered Sets.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/partially-ordered-set/