Wednesday, May 22, 2013

Ordering ordering relations

Every partial ordering relation falls between two weak orders: a child weak order and a parent weak order. These two weak orders form an order interval. Of course weak orders themselves have a trivial component interval since their child and parent intervals are both equal.

The divisibility relation on the natural numbers $(\mathbb{N},|)$ is a suborder of the weak ordering relation induced by the big omega function which outputs the number of prime factors of a number counting multiplicity.

The width of a partial ordering relation is the size of its largest child total order and topologically sorting produces the parent total orders of the partial order.

No comments:

Post a Comment