Poset: Examples

https://arbital.com/p/poset_examples

by Kevin Clancy Jun 8 2016 updated Dec 6 2016


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

Integer Comparison

The set Z of integers, ordered by the standard "less than or equal to" operator forms a poset Z,. 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

%%%comment:
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 forms a poset P(X),. is clearly reflexive, since any set is a subset of itself. For A,BP(X), AB and BA combine to give xAxB which means A=B. Thus, is antisymmetric. Finally, for A,B,CP(X), AB and BC give xAxB and xBxC, and so the transitivity of follows from the transitivity of .

Note that the strict subset relation is the strict ordering derived from the poset P(X),.

Divisibility on the natural numbers

Let [45h 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 N,| 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 k1 and k2 such that a=k1b and b=k2a. By substitution, we have a=k1k2a. Thus, if either k is 0, then both a and b must be 0. Otherwise, both k's must equal 1 so that a=k1k2a 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 k1 and k2 such that a=k1b and b=k2c. Since by substitution a=k1k2c, we have a|c.