14  Order

Throughout mathematics, and, in particular, for the generalization to infinite sets of the counting process appropriate to finite sets, the theory of order plays an important role. The basic definitions are simple. The only thing to remember is that the primary motivation comes from the familiar properties of “less than or equal to” and not “less than.” There is no profound reason for this; it just happens that the generalization of “less than or equal to” occurs more frequently and is more amenable to algebraic treatment.

A relation \(R\) in a set \(X\) is called antisymmetric if, for every \(x\) and \(y\) in \(X\), the simultaneous validity of \(xRy\) and \(yRx\) implies that \(x = y\). A partial order (or sometimes simply an order) in a set \(X\) is a reflexive, antisymmetric, and transitive relation in \(X\). It is customary to use only one symbol (or some typographically close relative of it) for most partial orders in most sets; the symbol in common use is the familiar inequality sign. Thus a partial order in \(X\) may be defined as a relation \(\le\) in \(X\) such that, for all \(x\), \(y\), and \(z\) in \(X\), we have (i) \(x \le x\), (ii) if \(x \le y\) and \(y \le x\), then \(x = y\), and (iii) if \(x \le y\) and \(y \le z\), then \(x \le z\). The reason for the qualifying “partial” is that some questions about order may be left unanswered. If for every \(x\) and \(y\) in \(X\) either \(x \le y\) or \(y \le x\), then \(\le\) is called a total (sometimes also simple or linear) order. A totally ordered set is frequently called a chain.

Exercise 14.1 Express the conditions of antisymmetry and totality for a relation \(R\) by means of equations involving \(R\) and its inverse.

The most natural example of a partial (and not total) order is inclusion. Explicitly: for each set \(X\), the relation \(\subset\) is a partial order in the power set \(\mathcal{P}(X)\); it is a total order if and only if \(X\) is empty or \(X\) is a singleton. A well known example of a total order is the relation “less than or equal to” in the set of natural numbers. An interesting and frequently seen partial order is the relation of extension for functions. Explicitly: for given sets \(X\) and \(Y\), let \(F\) be the set of all those functions whose domain is included in \(X\) and whose range is included in \(Y\). Define a relation \(R\) in \(F\) by writing \(fRg\) in case \(\text{dom }f \subset \text{dom }g\) and \(f(x) = g(x)\) for all \(x\) in \(\text{dom }f\); in other words, \(fRg\) means that \(f\) is a restriction of \(g\), or, equivalently, that \(g\) is an extension of \(f\). If we recall that the functions in \(F\) are, after all, certain subsets of the Cartesian product \(X \times Y\), we recognize that \(fRg\) means the same as \(f \subset g\); extension is a special case of inclusion.

A partially ordered set is a set together with a partial order in it. A precise formulation of this “togetherness” goes as follows: a partially ordered set is an ordered pair \((X, \le )\), where \(X\) is a set and \(\le\) is a partial order in \(X\). This kind of definition is very common in mathematics; a mathematical structure is almost always a set “together” with some specified other sets, functions, and relations. The accepted way of making such definitions precise is by reference to ordered pairs, triples, or whatever is appropriate. That is not the only way. Observe, for instance, that knowledge of a partial order implies knowledge of its domain. If, therefore, we describe a partially ordered set as an ordered pair, we are being quite redundant; the second coordinate alone would have conveyed the same amount of information. In matters of language and notation, however, tradition always conquers pure reason. The accepted mathematical behavior (for structures in general, illustrated here for partially ordered sets) is to admit that ordered pairs are the right approach, to forget that the second coordinate is the important one, and to speak as if the first coordinate were all that mattered. Following custom, we shall often say something like “let \(X\) be a partially ordered set,” when what we really mean is “let \(X\) be the domain of a partial order.” The same linguistic conventions apply to totally ordered sets, i.e., to partially ordered sets whose order is in fact total.

The theory of partially ordered sets uses many words whose technical meaning is so near to their everyday connotation that they are almost self-explanatory. Suppose, to be specific, that \(X\) is a partially ordered set and that \(x\) and \(y\) are elements of \(X\). We write \(y \ge x\) in case \(x \le y\); in other words, \(\ge\) is the inverse of the relation \(\le\). If \(x \le y\) and \(x \neq y\), we write \(x < y\) and we say that \(x\) is less than or smaller than \(y\), or that \(x\) is a predecessor of \(y\). Alternatively, under the same circumstances, we write \(y > x\) and we say that \(y\) is greater or larger than \(x\), or \(y\) is a successor of \(x\). The relation \(<\) is such that (i) for no elements \(x\) and \(y\) do \(x < y\) and \(y < x\) hold simultaneously, and (ii) if \(x < y\) and \(y < z\) then \(x < z\) (i.e., \(<\) is transitive). If, conversely, \(<\) is a relation in \(X\) satisfying (i) and (ii), and if \(x \le y\) is defined to mean that either \(x < y\) or \(x = y\), then \(\le\) is a partial order in \(X\).

The connection between \(\le\) and \(<\) can be generalized to arbitrary relations. That is, given any relation \(R\) in a set \(X\), we can define a relation \(S\) in \(X\) by writing \(xSy\) in case \(xRy\) but \(x \neq y\), and, vice versa, given any relation \(S\) in \(X\), we can define a relation \(R\) in \(X\) by writing \(xRy\) in case either \(xSy\) or \(x = y\). To have an abbreviated way of referring to the passage from \(R\) to \(S\) and back we shall say that \(S\) is the strict relation corresponding to \(R\), and \(R\) is the weak relation corresponding to \(S\). We shall say of a relation in a set \(X\) that it “partially orders \(X\)” in case either it is a partial order in \(X\) or else the corresponding weak relation is one.

If \(X\) is a partially ordered set, and if \(a \in X\), the set \(\{ x \in X:x < a \}\) is the initial segment determined by \(a\); we shall usually denote it by \(s(a)\). The set \(\{ x \in X: x \le a \}\) is the weak initial segment determined by \(a\), and will be denoted by \(\bar{s}(a)\). When it is important to emphasize the distinction between initial segments and weak initial segments, the former will be called strict initial segments. In general the words “strict” and “weak” refer to \(<\) and \(\le\) respectively. Thus, for instance, the initial segment determined by \(a\) may be described as the set of all predecessors of \(a\), or, for emphasis, as the set of all strict predecessors of \(a\); similarly the weak initial segment determined by \(a\) consists of all weak predecessors of \(a\). If \(x \le y\) and \(y \le z\), we may say that \(y\) is between \(x\) and \(z\); if \(x < y\) and \(y < z\), then \(y\) is strictly between \(x\) and \(z\). If \(x < y\) and if there is no element strictly between \(x\) and \(y\), we say that \(x\) is an immediate predecessor of \(y\), or \(y\) is an immediate successor of \(x\).

If \(X\) is a partially ordered set (which may in particular be totally ordered), then it could happen that \(X\) has an element \(a\) such that \(a \le x\) for every \(x\) in \(X\). In that case we say that \(a\) is the least (smallest, first) element of \(X\). The antisymmetry of an order implies that if \(X\) has a least element, then it has only one. If, similarly, \(X\) has an element \(a\) such that \(x \le a\) for every \(x\) in \(X\), then \(a\) is the greatest (largest, last) element of \(X\); it too is unique (if it exists at all). The set \(\omega\) of all natural numbers (with its customary ordering by magnitude) is an example of a partially ordered set with a first element (namely \(0\)) but no last. The same set, but this time with the inverse ordering, has a last element but no first.

In partially ordered sets there is an important distinction between least elements and minimal ones. If, as before, \(X\) is a partially ordered set, an element \(a\) of \(X\) is called a minimal element of \(X\) in case there is no element in \(X\) strictly smaller than \(a\). Equivalently, \(a\) is minimal if \(x \le a\) implies that \(x = a\). For an example, consider the collection \(\mathcal{C}\) of non-empty subsets of a non-empty set \(X\), with ordering by inclusion. Each singleton is a minimal element of \(\mathcal{C}\), but clearly \(\mathcal{C}\) has no least element (unless \(X\) itself is a singleton). We distinguish similarly between greatest and maximal elements; a maximal element of \(X\) is an element \(a\) such that \(X\) contains nothing strictly greater than \(a\). Equivalently, \(a\) is maximal if \(a \le x\) implies that \(x = a\).

An element \(a\) of a partially ordered set is said to be a lower bound of a subset \(E\) of \(X\) in case \(a \le x\) for every \(x\) in \(E\); similarly \(a\) is an upper bound of \(E\) in case \(x \le a\) for every \(x\) in \(E\). A set \(E\) may have no lower bounds or upper bounds at all, or it may have many; in the latter case it could happen that none of them belongs to \(E\). (Examples?) Let \(E_{*}\) be the set of all lower bounds of \(E\) in \(X\) and let \(E^{*}\) be the set of all upper bounds of \(E\) in \(X\). What was just said is that \(E_{*}\) may be empty, or \(E_{*} \cap E\) may be empty. If \(E_{*} \cap E\) is not empty, then it is a singleton consisting of the unique least element of \(E\). Similar remarks apply, of course, to \(E^{*}\). If it happens that the set \(E_{*}\) contains a greatest element \(a\) (necessarily unique), then \(a\) is called the greatest lower bound or infimum of \(E\). The abbreviations g.l.b. and inf are in common use. Because of the difficulties in pronouncing the former, and even in remembering whether g.l.b. is up (greatest) or down (lower), we shall use the latter notation only. Thus \(\text{inf } E\) is the unique element in \(X\) (possibly not in \(E\)) that is lower bound of \(E\) and that dominates (i.e., is greater than) every other lower bound of \(E\). The definitions at the other end are completely parallel. If \(E^{*}\) has a least element \(a\) (necessarily unique), then \(a\) is called the least upper bound (l.u.b.) or supremum (sup) of \(E\).

The ideas connected with partially ordered sets are easy to express but they take some time to assimilate. The reader is advised to manufacture many examples to illustrate the various possibilities in the behavior of partially ordered sets and their subsets. To aid him in this enterprise, we proceed to describe three partially ordered sets with some amusing properties. (i) The set is \(\omega \times \omega\). To avoid any possible confusion, we shall denote the order we are about to introduce by the neutral symbol \(R\). If \((a,b)\) and \((x,y)\) are ordered pairs of natural numbers, then \((a,b)R(x,y)\) means, by definition, that \((2a + 1) \cdot 2^{y} \le (2x + 1) \cdot 2^{b}\). (Here the inequality sign refers to the customary ordering of natural numbers.) The reader who is not willing to pretend ignorance of fractions will recognize that, except for notation, what we just defined is the usual order for \(\frac{2a + 1}{2^{b}}\) and \(\frac{2x + 1}{2^{y}}\). (ii) The set is \(\omega \times \omega\) again. Once more we use a neutral symbol for the order; say \(S\). If \((a,b)\) and \((x,y)\) are ordered pairs of natural numbers, then \((a,b)S(x,y)\) means, by definition, that either \(a\) is strictly less than \(x\) (in the customary sense), or else \(a = x\) and \(b \le y\). Because of its resemblance to the way words are arranged in a dictionary, this is called the lexicographical order of \(\omega \times \omega\). (iii) Once more the set is \(\omega \times \omega\). The present order relation, say \(T\), is such that \((a,b)T(x,y)\) means, by definition, that \(a \le x\) and \(b \le y\).