Introduction to Lattice Theory with Computer Science Applications

Chapter 12Interval Orders

12.1 Introduction

This chapter covers weak orders (ranking), semiorders, and interval orders. All of these partial orders are “close” to a total order. The relationship between these orders is as follows. Every weak order is also a semiorder, and every semiorder is also an interval order.

12.2 Weak Order

A weak order, also called ranking, is a slight generalization of a total order.

Definition 12.1 (Weak Order)

A poset is a weak order or a ranking if there exists a function such that .

The term “weak order” is somewhat of a misnomer because a weak order has a lot of order. To allow for easy visualization of such orders, we will use the term “ranking” instead of the more accepted term “weak order.” The set of elements in a ranking which have the same value is called a rank. For example, the poset shown in Figure 12.1 is a ranking because we can assign , and . Here, and are in the same rank. The difference between a chain and a ranking is that a ...