# 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/