Skip to main content
Mathematics LibreTexts

2.2: Orderings

  • Page ID
    99057
    • Bob Dumas and John E. McCarthy
    • University of Washington and Washington University in St. Louis
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    A relation on a set may be thought of as part of the structure imposed on the set. Among the most important relations on a set are order relations.

    Definition: Partial ordering

    Let \(X\) be a set and \(R\) a relation on \(X\). We say that \(R\) is a partial ordering if:
    (1) \(R\) is reflexive
    (2) \(R\) is antisymmetric
    (3) \(R\) is transitive.

    Example 2.5

    Let \(X\) be a family of sets. The relation \(\subseteq\) is a partial ordering on \(X\). Every set is a subset of itself, so the relation is reflexive. If \(Y \subseteq Z\) and \(Z \subseteq Y\), then \(Y=Z\), so the relation is antisymmetric. Finally, if \(Y \subseteq Z\) and \(Z \subseteq W\) then \(Y \subseteq W\), so the relation is transitive.

    Example 2.6

    Let \(R\) be the relation on \(\mathbb{N}^{+}\)defined by \(x R y\) if and only if there is \(z \in \mathbb{N}^{+}\)such that \[x z=y .\] Then \(R\) is a partial ordering of \(\mathbb{N}^{+}\). (Prove this: Exercise 2.2).

    Definition: Linear ording

    Let \(X\) be a set and \(R\) be a partial ordering of \(X\). We say that \(R\) is a linear ordering, also called a total ordering, provided that, for any \(x, y \in X\), either \(x R y\) or \(y R x\).

    Note that since a linear ordering is antisymmetric, for any distinct \(x\) and \(y\), exactly one of \(x R y\) and \(y R x\) holds.

    Example 2.7

    The ordering \(\leq\) on \(\mathbb{N}\) (or \(\mathbb{R}\) ) is a linear ordering. So is the relation \(\geq\). The relation \(<\) is not (why?).

    Example 2.8

    Let \(X=\mathbb{R}^{n}\). We can define a reflexive relation on \(X\) as follows. Let \(x=\left(a_{1}, \ldots, a_{n}\right)\) and \(y=\left(b_{1}, \ldots, b_{n}\right)\) be distinct members of \(X\). Let \(k \in \mathbb{N}^{+}\)be the least number such that \(a_{k} \neq b_{k}\). Then we define \[x R y \text { if and only if } a_{k}<b_{k} .\] Then \(R\) is a linear ordering of \(X\). It is called the dictionary ordering.

    The notion of a linear ordering is probably natural for you, and you have used it intuitively since you began studying arithmetic. The relation \(\leq\) helps you to visualize the set as a line in which the relative location of two elements of the set is determined by the linear ordering. If you are considering a set with operations, this in turn can help in visualizing how operations behave. For instance, think of using a number line to visualize addition, subtraction and multiplication of integers.

    Partial orderings are generalizations of linear orderings, and \(\leq\) is the most obvious example of a linear ordering. Because of this, the normal symbol for a partial ordering is \(\preceq\) (it is also reminiscent of the symbol \(\subseteq\), which is the example most mathematicians keep in mind when thinking about a partial ordering).

    Example 2.9

    Let \(X\) be the set of all collections of apples and oranges. If \(x, y\) are in \(X\), then say \(x \preceq y\) if the number of apples in \(x\) is less than or equal to the number of apples in \(y\), and the number of oranges in \(x\) is less than or equal to the number of oranges in \(y\). This is a partial ordering. You may not be able to compare apples to oranges, but you can say that 2 apples and 5 oranges is inferior to 4 apples and 6 oranges!

    One way to visualize a partial order \(\preceq\) on a finite set \(X\) is to imagine arrows connecting distinct elements of \(X, x\) and \(y\), if \(x \preceq y\) and there is no third distinct point \(z\) satisfying \(x \preceq z \preceq y\). Then two elements \(a\) and \(b\) in \(X\) will satisfy \(a \preceq b\) if and only if you can get from \(a\) to \(b\) by following a path of arrows.

    Example \(\PageIndex{1}\)

    Consider the graph on the set \(X=\{a, b, c, d, e, f\}\) give in Figure 2.11.

    2.11.jpg
    FIGURE 2.11. Picture of a partial order

    It illustrates the partial order that could be described as the smallest reflexive, transitive relation \(\preceq\) on \(X\) that satisfies \(a \preceq b, a \preceq c, b \preceq\) \(d, b \preceq e, c \preceq e, e \preceq f .\)


    This page titled 2.2: Orderings is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Bob Dumas and John E. McCarthy via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?