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

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.