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.
Both partially ordered and strictly ordered sets are said to be totally ordered if every two members of the set are comparable. The usual “less than or equal to” order (≤) is a total order on the real numbers since any two real numbers x, y satisfy x ≤ y or y ≤ x. On the other hand, the set inclusion relation (⊆) is a partial order on the power set P(A) of A = {a, b, c}, but does not totally order the power set since not all sets in the power set are comparable, an example being the sets {a, c} and {b}.
Although, we have seen that “≤” and “⊆” are partial orders on ℝ and P(A), respectively, there is an important difference. The partial order “≤” on the real numbers is also a total order, inasmuch as any two real numbers x and y are comparable as in x ≤ y or y ≤ x. On the other hand, “⊆” is not a total order on the power set of {a, b, c} since it is not true that
We say a relation R on a set A is symmetric if xRy ⇔ yRx for all x, y ∈ R. One might think offhand that antisymmetry is the negation of being symmetric, but this is not true. The equal relation “=” is both symmetric and antisymmetric. However, the relation “is married to” is a symmetric relation but is not antisymmetric, whereas the relation ≤ on the real line is antisymmetric but not symmetric.
Although a partially ordered set can contain an infinite number of elements, many important examples are finite. A useful way to represent finite partially ordered sets is a Hasse Diagram,1 where each element of the ordered set is denoted by a dot (node) and a line segment that goes upward from node x to node y means that x ≤ y.
A Hasse diagram for a partial order on A = {a, b, c, d, e, f, g} is drawn in Figure 3.11, where a few orderings are e ≤ d, f ≤ d, g ≤ d. Also e ≤ c by transitivity since one can move upwards from e to c moving through the nodes d and b. On the other hand, and , so the order is not a total order since some elements are not comparable.
Table 3.2 lists some common relations and their properties. The set over which the relation is defined is given in parenthesis next to the relation.
Table 3.2 Properties of common relations.
Reflexive | Antisymmetric | Transitive | Symmetric | |
Relations | xRx | xRy ∧ yRx ⇒ x = y | xRy ∧ yRz ⇒ xRz | xRy ⇒ xRx |
≤ (ℝ) | Yes | Yes | Yes | No |
< (ℝ) | No | No | Yes | No |
≡ (mod n) | Yes | No | Yes | Yes |
≈ (sets) | Yes | No | Yes | Yes |
⊆ (sets) | Yes | Yes | Yes | No |
⊥ (lines) | No | No | No | Yes |
∥ (lines) | Yes | No | Yes | Yes |
∣ on ℤ | Yes | No | Yes | No |
∣ on ℕ | Yes | Yes | Yes | No |
= (ℝ) | Yes | Yes | Yes | Yes |
Tell whether the following relations on A = {1, 2, 3} are reflexive, antisymmetric, and transitive. Plot the points of the relation in the Cartesian product A × A and denote the members of R ⊆ A × A. If the relation is an order relation, draw a Hasse diagram and directed graph for the relation.
Find a relation on A = {1, 2, 3, 4} with the following properties.
Let C[0, 1] be the set of continuous functions defined on [0, 1]. For f, g ∈ C[0, 1], define the ordering
Show that “≤” defines a partial order on C[0, 1].
The Hasse diagram for the power set P(A) of A = {a, b, c, d} is drawn in Example 6 with order relation ⊆. Use the Hasse diagram to find an upper bound, a least upper bound, a lower bound, and the greatest lower bound of the following subsets of P(A)
If they exist, find the sup, inf, max, and min of the following sets.
Jane is getting a degree in mathematics and has several courses to take. Some of the courses have prerequisites as shown below.
Course needed | Prerequisites |
|
|
|
Calculus I |
|
Calculus II |
|
Calculus III |
|
Calculus III |
|
Linear Algebra, Calculus II |
|
Linear Algebra, pure math |
|
Calculus III, pure math |
Draw a Hasse diagram that illustrates the order which Jane must take courses.
Let M be the order relation “a is a multiple of b” defined on the positive divisors of 15. Draw a Hasse diagram for M.
There are various ways to construct new orders from existing orders. A partial order can be constructed on the Cartesian product of two partially ordered sets by defining
State the contrapositive form of the antisymmetry condition
Suppose we try to order the complex numbers z = a + bi according to magnitudes
where is the magnitude of the complex number. Is this a partial order on the complex numbers?
The complex numbers can be totally ordered as follows. Given two complex numbers in polar form
order the complex numbers by
Compare the following complex numbers.
There are a total of three partial orders on A = {1, 2}. Can you find them?
Given the subset S ⊆ U represented by “stars” in the Hasse diagram in Figure 3.17 which describes a partial ordering of the set:
find the following quantities of S:
A Hasse diagram representation of a partial order is shown in Figure 3.18. If they exist, find the sup and inf of the following sets. A partially ordered set is called a lattice if every pair of elements in the set has a sup and inf. Is the set under this partial order a lattice?
If it exists, find the maximum value of the set
If it does not exist, find the least upper bound of S.
A lattice L is a partially ordered set in which every two members a, b ∈ L has a supremum and infimum in L. The supremum is called the join of aand b and denoted by a ∨ b, and the infimum is called the meet of a and b, and denoted by a ∧ b. Determine which of the partially ordered sets in Figure 3.19 represented by Hasse diagrams, are lattices.
A lattice is a partially ordered set in which every two elements has a unique least upper bound (called their join) and a unique greatest lower bound (called their meet.) Figure 3.20 shows a Hasse diagram for the set of all partitions of {1.2.3.4} into disjoint subsets, partially ordered by “increasing merging of sets.” The slashes between numbers represent different partitions. For instance 1/2/3/4 means the partition {1}, {2}, {3}, {4} and 14/23 denotes the partition {1, 4}, {2, 3}. Draw the lattice for the set of partitions of the set {a, b, c}.
Assuming the usual partial ordering ≤ for the rational and real numbers, tell which of the following are true or false.
A partial order R on a set A is said to be dense in A if
Which of the following partial orders are dense on the given set?
If R is a partial order on a set A, then show the inverse R−1 relation is a partial order on A.
Show that the set
is bounded above but has no least upper bound.
Let R be the usual “less than or equal to” ordering and S be the usual “greater than or equal to” ordering on the set A = {1, 2, 3}. Find the composition R ∘ S = ≤ ∘ ≥ of the two orders.
A partition of a positive integer is a way of writing the number as a sum of positive integers where the order is not important and numbers can be repeated. The five partitions of the number 4 are shown in Figure 3.21.
The function that gives the number of partitions of a natural number n is called the partition function p(n), and in this case p(4) = 5. A convenient way to organize the partitions on a number is a Ferrers diagram, where the number of rows in the diagram represent the number of terms in the partition and the number of squares in the row is the size of the term. The Ferrers diagram for the partitions of numbers 1–5 is shown in Figure 3.22. Find the partitions of 6 and draw the Ferrers diagram.
An asymptotic estimate for p(n) was found in 1918 by G.H. Hardy and Ramanujan to be
Use this formula to estimate p(100), p(200), p(1000).
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward ordered structures in math, ordered sets.
3.129.39.55