Poset: Examples


by Kevin Clancy Jun 8 2016 updated Dec 6 2016

The standard $~$\leq$~$ relation on integers, the $~$\subseteq$~$ relation on sets, and the $~$|$~$ (divisibility) relation on natural numbers are all examples of poset orders.

Integer Comparison

The set $~$\mathbb Z$~$ of integers, ordered by the standard "less than or equal to" operator $~$\leq$~$ forms a poset $~$\langle \mathbb Z, \leq \rangle$~$. This poset is somewhat boring however, because all pairs of elements are comparable; such posets are called chains or totally ordered sets. Here is its Hasse diagram.

Truncated Hasse diagram

dot source (doctored in GIMP)

digraph G {
  node [width = 0.1, height = 0.1]
  edge [arrowhead = "none"]
  a [label = "-3"]
  b [label = "-2"]
  c [label = "-1"]
  d [label = "0"]
  e [label = "1"]
  f [label = "2"]
  g [label = "3"]
  rankdir = BT;
  a -> b
  b -> c
  c -> d
  d -> e
  e -> f
  f -> g

Power sets

For any set $~$X$~$, the power set of $~$X$~$ ordered by the set inclusion relation $~$\subseteq$~$ forms a poset $~$\langle \mathcal{P}(X), \subseteq \rangle$~$. $~$\subseteq$~$ is clearly reflexive, since any set is a subset of itself. For $~$A,B \in \mathcal{P}(X)$~$, $~$A \subseteq B$~$ and $~$B \subseteq A$~$ combine to give $~$x \in A \Leftrightarrow x \in B$~$ which means $~$A = B$~$. Thus, $~$\subseteq$~$ is antisymmetric. Finally, for $~$A, B, C \in \mathcal{P}(X)$~$, $~$A \subseteq B$~$ and $~$B \subseteq C$~$ give $~$x \in A \Rightarrow x \in B$~$ and $~$x \in B \Rightarrow x \in C$~$, and so the transitivity of $~$\subseteq$~$ follows from the transitivity of $~$\Rightarrow$~$.

Note that the strict subset relation $~$\subset$~$ is the strict ordering derived from the poset $~$\langle \mathcal{P}(X), \subseteq \rangle$~$.

Divisibility on the natural numbers

Let [45h $~$\mathbb N$~$] be the set of natural numbers including zero, and let $~$|$~$ be the divides relation, where $~$a|b$~$ whenever there exists an integer $~$k$~$ such that $~$ak=b$~$. Then $~$\langle \mathbb{N}, | \rangle$~$ is a poset. $~$|$~$ is reflexive because, letting k=1, any natural number divides itself. To see that $~$|$~$ is anti-symmetric, suppose $~$a|b$~$ and $~$b|a$~$. Then there exist integers $~$k_1$~$ and $~$k_2$~$ such that $~$a = k_1b$~$ and $~$b = k_2a$~$. By substitution, we have $~$a = k_1k_2a$~$. Thus, if either $~$k$~$ is $~$0$~$, then both $~$a$~$ and $~$b$~$ must be $~$0$~$. Otherwise, both $~$k$~$'s must equal $~$1$~$ so that $~$a = k_1k_2a$~$ holds. Either way, $~$a = b$~$, and so $~$|$~$ is anti-symmetric. To see that $~$|$~$ is transitive, suppose that $~$a|b$~$ and $~$b|c$~$. This implies the existence of integers $~$k_1$~$ and $~$k_2$~$ such that $~$a = k_1b$~$ and $~$b = k_2c$~$. Since by substitution $~$a = k_1k_2c$~$, we have $~$a|c$~$.