# Poset: Examples

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.

comment: dot source (doctored in GIMP)

digraph 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$$ 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 $$\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$$.

Parents: