]>
A relation on that is reflexive, anti-symmetric, and transitive is said to be a partial order on . As the name and notation suggest, a partial order is a type of ordering of the elements of . Partial orders occur naturally in many areas of mathematics, including probability.
A partial order on a set naturally gives rise to several other relations on : , , , , and :
Show that the inverse of a partial order is also a partial order.
Show that if is a partial order on and is a subset of , then the restriction of to is a partial order on .
A partial order on is a total order or linear order if it satisfies the additional property that for every and , either or . Of course, the ordinary order is a total order on the set of real numbers .
Suppose that is a set. Show that the subset relation is a partial order on , the power set of .
The following exercise characterizes relations that correspond to strict order.
Let be a set. Show that is a partial order on if and only if is transitive and irreflexive.
Suppose that and are partial orders on a nonempty set . Then is an sub-order of , or equivalently is an extension of if and only if
Thus, as sets of ordered pairs, is a subset of .
Let denote the division relation on the set of positive integers . That is, if and only if there exists such that . Show that is a partial order on , and is a sub-order of the ordinary order .
Suppose that is a partial order on a set . For and , is said to cover if but no element satisfies . If is finite, the covering relation completely determines the partial order. Moreover, the covering graph or Hasse graph is the directed graph with vertes set and directed edge set , where if and only if covers . Thus, if and only if there is a directed path in the graph from to . Hasse graphs are named for the German mathematician Helmut Hasse. The graphs are often drawn with the edges directed upward. In this way, the directions can be inferred without having to actually draw arrows.
Let .
Suppose that and are sets with partial orders and respectively. Define the relation on by if and only if and
The picture below shows a point . Suppose that is given the product order associated with the ordinary order on . Then the region shaded red is the set of points larger than The region shaded blue is the set of points smaller than . The region shaded white is the set of points that are not comparable with .
Suppose again that and are sets with partial orders and respectively. Define the relation on by if and only if either , or and
The picture below shows a point . Suppose that is given the lexicographic order associated with the ordinary order on . Then the region shaded red is the set of points larger than The region shaded blue is the set of points smaller than .
Lexicographic orders are not as obscure as you might think. Many standard partially ordered sets can be expressed as lexicographic products.
A real number can be uniquely expressed in terms of its integer part and remainder:
where and . In this way, can be associated with the product space . Show that corresponds to the lexicographic product of with , where of course is the ordinary order for real numbers.
Partial orders form a natural setting for increasing and decreasing sets and functions. Suppose first that is a partial order on a set and that . Then
Suppose now is a set with partial order and that is another set with partial order . Finally suppose that . Then
Suppose that is a partial order on a set and that . Recall the definition of the indicator function associated with . Show that
In a sense, the subset partial order is universal--every partially ordered set is isomorphic to for some collection of sets
Suppose that is a partial order on a set . For each , let , and then let , so that . Show that the function is one-to-one (and of course onto) and satisfies
Suppose again that is a partial order on a set and that . Various types of extremal elements of play important roles.
In general, a set can have several maximal and minimal elements (or none).
Show that the minimum and maximum elements of , if they exist, are unique. They are denoted and , respectively.
Minimal, maximal, minimum, and maximum elements of a set must belong to that set. The following definitions relate to upper and lower bounds of a set, which do not have to belong to the set.
By the Exercise 10, the greatest lower bound of is unique, if it exists. It is denoted or . Similarly, the least upper bound of is unique, if it exists, and is denoted or .
Consider the ordinary order ≤ on the set of real numbers , and let where . Find each of the following that exist:
Consider the division partial order on the set of positive integers and let be a non-empty subset of .
Again consider the division partial order on the set of positive integers and let . Find each of the following that exist:
Let be a set and consider the subset partial order on , the power set of . Let be a non-empty subset of , that is, a non-empty collection of subsets of . Show that
Suppose that is a set and that . An element is said to be a fixed point of if . The following exercise explores a basic fixed point theorem for a partially ordered set. The theorem is important in the study of cardinality.
Suppose that is a partial order on a set with the property that exists for every . If is an increasing function from into , then has a fixed point. The following steps outline the proof:
Suppose that is a sequence of real numbers.
Show that is increasing in
The limit of the sequence in the last exercise is the limit inferior of the original sequence:
Show that is decreasing in
The limit of the sequence in the last exercise is the limit superior of the original sequence:
Note that and equality holds if and only if exists (and is the common value).