Poset: Examples

The stan­dard \(\leq\) re­la­tion on in­te­gers, the \(\subseteq\) re­la­tion on sets, and the \(|\) (di­visi­bil­ity) re­la­tion on nat­u­ral num­bers are all ex­am­ples of poset or­ders.

In­te­ger Comparison

The set \(\mathbb Z\) of in­te­gers, or­dered by the stan­dard “less than or equal to” op­er­a­tor \(\leq\) forms a poset \(\langle \mathbb Z, \leq \rangle\). This poset is some­what bor­ing how­ever, be­cause all pairs of el­e­ments are com­pa­rable; such posets are called chains or to­tally or­dered sets. Here is its Hasse di­a­gram.

Truncated Hasse diagram

com­ment: dot source (doc­tored in GIMP)

di­graph G { node = 0.1, height = 0.1 edge = “none” a = “-3″ b = “-2” c = “-1″ d = “0” e = “1″ f = “2” g = “3″ rankdir = BT; a → b b → c c → d d → e e → f f → g } <div>

Power sets

For any set \(X\), the power set of \(X\) or­dered by the set in­clu­sion re­la­tion \(\subseteq\) forms a poset \(\langle \mathcal{P}(X), \subseteq \rangle\). \(\subseteq\) is clearly re­flex­ive, since any set is a sub­set of it­self. For \(A,B \in \mathcal{P}(X)\), \(A \subseteq B\) and \(B \subseteq A\) com­bine to give \(x \in A \Leftrightarrow x \in B\) which means \(A = B\). Thus, \(\subseteq\) is an­ti­sym­met­ric. Fi­nally, 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 tran­si­tivity of \(\subseteq\) fol­lows from the tran­si­tivity of \(\Rightarrow\).

Note that the strict sub­set re­la­tion \(\subset\) is the strict or­der­ing de­rived from the poset \(\langle \mathcal{P}(X), \subseteq \rangle\).

Divisi­bil­ity on the nat­u­ral numbers

Let \(\mathbb N\) be the set of nat­u­ral num­bers in­clud­ing zero, and let \(|\) be the di­vides re­la­tion, where \(a|b\) when­ever there ex­ists an in­te­ger \(k\) such that \(ak=b\). Then \(\langle \mathbb{N}, | \rangle\) is a poset.\(|\) is re­flex­ive be­cause, let­ting k=1, any nat­u­ral num­ber di­vides it­self. To see that \(|\) is anti-sym­met­ric, sup­pose \(a|b\) and \(b|a\). Then there ex­ist in­te­gers \(k_1\) and \(k_2\) such that \(a = k_1b\) and \(b = k_2a\). By sub­sti­tu­tion, we have \(a = k_1k_2a\). Thus, if ei­ther \(k\) is \(0\), then both \(a\) and \(b\) must be \(0\). Other­wise, both \(k\)’s must equal \(1\) so that \(a = k_1k_2a\) holds. Either way, \(a = b\), and so \(|\) is anti-sym­met­ric. To see that \(|\) is tran­si­tive, sup­pose that \(a|b\) and \(b|c\). This im­plies the ex­is­tence of in­te­gers \(k_1\) and \(k_2\) such that \(a = k_1b\) and \(b = k_2c\). Since by sub­sti­tu­tion \(a = k_1k_2c\), we have \(a|c\).

Parents:

  • Partially ordered set

    A set en­dowed with a re­la­tion that is re­flex­ive, tran­si­tive, and an­ti­sym­met­ric.

    • Order theory

      The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.