Product order

Hasse diagram of the product order on ${\displaystyle \mathbb {N} }$ ×${\displaystyle \mathbb {N} }$

In mathematics, given partial orders ${\displaystyle \preceq }$ and ${\displaystyle \sqsubseteq }$ on sets ${\displaystyle A}$ and ${\displaystyle B}$ , respectively, the product order^[1][2][3][4] (also called the coordinatewise order^[5][3][6] or componentwise order^[2][7]) is a partial order ${\displaystyle \leq }$ on the Cartesian product ${\displaystyle A\times B.}$ Given two pairs ${\displaystyle \left(a_{1},b_{1}\right)}$ and ${\displaystyle \left(a_{2},b_{2}\right)}$ in ${\displaystyle A\times B,}$ declare that ${\displaystyle \left(a_{1},b_{1}\right)\leq \left(a_{2},b_{2}\right)}$ if ${\displaystyle a_{1}\preceq a_{2}}$ and ${\displaystyle b_{1}\sqsubseteq b_{2}.}$

Another possible order on ${\displaystyle A\times B}$ is the lexicographical order. It is a total order if both ${\displaystyle A}$ and ${\displaystyle B}$ are totally ordered. However the product order of two total orders is not in general total; for example, the pairs ${\displaystyle (0,1)}$ and ${\displaystyle (1,0)}$ are incomparable in the product order of the order ${\displaystyle 0<1}$ with itself. The lexicographic combination of two total orders is a linear extension of their product order, and thus the product order is a subrelation of the lexicographic order.^[3]

The Cartesian product with the product order is the categorical product in the category of partially ordered sets with monotone functions.^[7]

The product order generalizes to arbitrary (possibly infinitary) Cartesian products. Suppose ${\displaystyle A\neq \varnothing }$ is a set and for every ${\displaystyle a\in A,}$ ${\displaystyle \left(I_{a},\leq \right)}$ is a preordered set. Then the product preorder on ${\displaystyle \prod _{a\in A}I_{a}}$ is defined by declaring for any ${\displaystyle i_{\bullet }=\left(i_{a}\right)_{a\in A}}$ and ${\displaystyle j_{\bullet }=\left(j_{a}\right)_{a\in A}}$ in ${\displaystyle \prod _{a\in A}I_{a},}$ that

${\displaystyle i_{\bullet }\leq j_{\bullet }}$ if and only if ${\displaystyle i_{a}\leq j_{a}}$ for every ${\displaystyle a\in A.}$

If every ${\displaystyle \left(I_{a},\leq \right)}$ is a partial order then so is the product preorder.

Furthermore, given a set ${\displaystyle A,}$ the product order over the Cartesian product ${\displaystyle \prod _{a\in A}\{0,1\}}$ can be identified with the inclusion order of subsets of ${\displaystyle A.}$ ^[4]

The notion applies equally well to preorders. The product order is also the categorical product in a number of richer categories, including lattices and Boolean algebras.^[7]

See also

• Direct product of binary relations
• Examples of partial orders
• Star product, a different way of combining partial orders
• Orders on the Cartesian product of totally ordered sets
• Ordinal sum of partial orders
• Ordered vector space – Vector space with a partial order

References

1. Neggers, J.; Kim, Hee Sik (1998), "4.2 Product Order and Lexicographic Order", Basic Posets, World Scientific, pp. 64–78, ISBN 9789810235895
2. Sudhir R. Ghorpade; Balmohan V. Limaye (2010). A Course in Multivariable Calculus and Analysis. Springer. p. 5. ISBN 978-1-4419-1621-1.
3. Egbert Harzheim (2006). Ordered Sets. Springer. pp. 86–88. ISBN 978-0-387-24222-4.
4. Victor W. Marek (2009). Introduction to Mathematics of Satisfiability. CRC Press. p. 17. ISBN 978-1-4398-0174-1.
5. Davey & Priestley, Introduction to Lattices and Order (Second Edition), 2002, p. 18
6. Alexander Shen; Nikolai Konstantinovich Vereshchagin (2002). Basic Set Theory. American Mathematical Soc. p. 43. ISBN 978-0-8218-2731-4.
7. Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. pp. 144–145 and 216. ISBN 978-0-521-63107-5.