Partially Ordered Sets

A partially ordered set is 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 \) are comparable, 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 \) is totally 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.