Advanced Mathematics

3.2Order Relations

Purpose of Section

To introduce some important types of orderings, such as a partial order and strict order as well as what it means for a set to be totally ordered. Using the order relation, we introduce the concept of upper and lower bounds of a set, the least upper bound, and greatest lower bound of a set. We also show how order relations can be illustrated graphically by means of Hasse diagrams.

3.2.1 Let There Be Order

The British philosopher Edmund Burke once said, “Order is the foundation of all that is good,” and although he probably was not referring to inequalities of numbers, nevertheless, order is as important in mathematics as it is anywhere else. The reader is familiar with the inequality relations ≤ and < that impose an ordering of real numbers, and the relation ⊆, which imposes an “order” on sets. Other objects can be “ordered” as well, such as functions, matrices, and points in the plane. Ordering objects according to given rules brings structure to an area that might otherwise be difficult to analyze. In computer science, order not only brings understanding, but efficiency. Imagine trying to find information on the Internet if search engines did not have clever “ordering” strategies for searching for information.

Definition Simple, Partial, and Strict Order

1. A partial order on a set A, denoted by ≤, is a binary relation on A such that for all x, y, z in A, the following RAT conditions hold.

   When a partial order is defined on ...