Skip to main content
Engineering LibreTexts

9.9: Product Orders

  • Page ID
    48352
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \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}}\)

    Taking the product of two relations is a useful way to construct new relations from old ones.

    Definition \(\PageIndex{1}\)

    The product, \(R_1 \times R_2\), of relations \(R_1\) and \(R_2\) is defined to be the relation with

    \[\begin{aligned} \text{domain}(R_1 \times R_2) &::= \text{domain}(R_1) \times \text{domain}(R_2), \\ \text{codomain}(R_1 \times R_2) &::= \text{codomain}(R_1) \times \text{codomain}(R_2), \\ (a_1, a_2) (R_1 \times R_2) (b_1, b_2) &\text{ iff } [a_1R_1b_1 \text{ and } a_2R_2b_2]\end{aligned}\]

    It follows directly from the definitions that products preserve the properties of transitivity, reflexivity, irreflexivity, and antisymmetry (see Problem 9.41). If \(R_1\) and \(R_2\) both have one of these properties, then so does \(R_1 \times R_2\). This implies that if \(R_1\) and \(R_2\) are both partial orders, then so is \(R_1 \times R_2\).

    Example \(\PageIndex{2}\)

    Define a relation, \(Y\), on age-height pairs of being younger and shorter. This is the relation on the set of \(\text{pair}(y, h)\) where \(y\) is a nonnegative integer \(\leq 2400\) that we interpret as an age in months, and \(h\) is a nonnegative integer \(\leq 120\) describing height in inches. We define \(Y\) by the rule

    \[\nonumber (y_1, h_1) Y (y_2, h_2) \text{ iff } y_1 < y_2 \text{ AND } h_1 \leq h_2.\]

    That is, \(Y\) is the product of the \(\leq\)-relation on ages and the \(\leq\)-relation on heights.

    Since both ages and heights are ordered numerically, the age-height relation \(Y\) is a partial order. Now suppose we have a class of 101 students. Then we can apply Dilworth’s lemma 9.5.12 to conclude that there is a chain of 11 students—that is, 11 students who get taller as they get older–or an antichain of 11 students—that is, 11 students who get taller as they get younger, which makes for an amusing in-class demo.

    On the other hand, the property of being a linear order is not preserved. For example, the age-height relation \(Y\) is the product of two linear orders, but it is not linear: the age 240 months, height 68 inches pair, (240,68), and the pair (228,72) are incomparable under \(Y\).


    This page titled 9.9: Product Orders is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .

    • Was this article helpful?